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

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

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

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

Ссылки

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