Число независимости
|
Число независимости графа G {displaystyle G} — это размер наибольшего независимого множества вершин в нём. Поскольку задача о независимом множестве является NP-полной, то неизвестны алгоритмы определения числа независимости в произвольном графе, работающие за полиномиальное время. В любом графе G = ( V , E ) {displaystyle G=(V,E)} число независимости α ( G ) {displaystyle alpha (G)} связано с числом вершинного покрытия τ ( G ) {displaystyle au (G)} первым тождеством Галлаи: α ( G ) + τ ( G ) = | V | {displaystyle alpha (G)+ au (G)=|V|} , более того, дополнение к наибольшему независимому множеству вершин является наименьшим вершинным покрытием. Используя этот факт, в двудольном графе G {displaystyle G} можно найти α ( G ) {displaystyle alpha (G)} за полиномиальное время, поскольку задача о наименьшем вершинном покрытии в нём сводится к поиску наибольшего паросочетания. В графе G {displaystyle G} , в котором отсутствуют изолированные вершины (вершины степени 0), также справедливо неравенство α ( G ) ≤ ρ ( G ) {displaystyle alpha (G)leq ho (G)} , где ρ ( G ) {displaystyle ho (G)} — число рёберного покрытия графа G {displaystyle G} . В двудольном графе G {displaystyle G} без изолированных вершин, вследствие Теоремы Кёнига, α ( G ) = ρ ( G ) {displaystyle alpha (G)= ho (G)} . |
