Число вершинного покрытия

Число вершинного покрытия графа [math]\displaystyle{ G }[/math] — размер наименьшего вершинного покрытия в нём.

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

В любом графе [math]\displaystyle{ G = (V, E) }[/math] число вершинного покрытия [math]\displaystyle{ \tau (G) }[/math] связано с числом независимости [math]\displaystyle{ \alpha (G) }[/math] первым тождеством Галлаи: [math]\displaystyle{ \alpha (G) + \tau (G) = |V| }[/math], более того, дополнение к наименьшему вершинному покрытию является наибольшим независимым множеством вершин.

В любом графе [math]\displaystyle{ G }[/math] также справедливо неравенство [math]\displaystyle{ \tau (G) \ge \nu (G) }[/math], где [math]\displaystyle{ \nu (G) }[/math] — число паросочетания графа [math]\displaystyle{ G }[/math]. В двудольном графе [math]\displaystyle{ G }[/math], вследствие Теоремы Кёнига, [math]\displaystyle{ \tau (G) = \nu (G) }[/math]. Поэтому в двудольных графах задача определения [math]\displaystyle{ \tau (G) }[/math] решается за полиномиальное время.

Ссылки

• László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.