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

Число вершинного покрытия графа $G$ — это размер наименьшего вершинного покрытия в нём.

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

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

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

Ссылки

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