Число независимости

Число независимости графа $G$ — это размер наибольшего независимого множества вершин в нём.

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

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

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

Ссылки

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