Форум Статьи Контакты
Строительство — возведение зданий и сооружений, а также их капитальный и текущий ремонт, реконструкция, реставрация и реновация.

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

Дата: 9-11-2020, 17:30 » Раздел: Статьи  » 

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


(голосов:0)

Пожожие новости
Комментарии

Ваше Имя:   Ваш E-Mail: