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

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

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

В любом графе число вершинного покрытия связано с числом независимости первым тождеством Галлаи: , более того, дополнение к наименьшему вершинному покрытию является наибольшим независимым множеством вершин.

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

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

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