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

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

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

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

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

СсылкиПравить

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