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

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

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

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

Ссылки

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