Задача о минимальном вершинном покрытии. Теорема Кёнига

Вершинное покрытие.

Пусть дан граф G из множества вершин V и ребер E, вершинным покрытием называется подмножество вершин V' графа, таких что каждое ребро инцидентно хотя бы одной вершине из V'.

Минимальное вершинное покрытие – это вершинное покрытие, количество вершин в котором не превосходит количество вершин в любом другом вершинном покрытии (минимально возможное число вершин)

Задача о вершинном покрытии:

В заданном графе найти минимальное вершинное покрытие. Задача принадлежит классу NP-полный в слабом смысле.

Теорема Кёнига.

В двудольном графе количество вершин в минимальном вершинном покрытии совпадает с количеством ребер в максимальном паросочетании.