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

Число независимости графа $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)$ .