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

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