Число независимости: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
м Добавлена Категория:Инварианты графов с помощью HotCat |
Нет описания правки |
||
| Строка 5: | Строка 5: | ||
В любом графе <math>G = (V, E)</math> число независимости <math>\alpha (G)</math> связано с [[Число вершинного покрытия|числом вершинного покрытия]] <math>\tau (G)</math> первым [[Тождества Галлаи|тождеством Галлаи]]: <math>\alpha (G) + \tau (G) = |V|</math>, более того, дополнение к наибольшему независимому множеству вершин является наименьшим вершинным покрытием. Используя этот факт, в двудольном графе <math>G</math> можно найти <math>\alpha (G)</math> за полиномиальное время, поскольку задача о наименьшем вершинном покрытии в нём сводится к поиску наибольшего [[Паросочетание|паросочетания]]. |
В любом графе <math>G = (V, E)</math> число независимости <math>\alpha (G)</math> связано с [[Число вершинного покрытия|числом вершинного покрытия]] <math>\tau (G)</math> первым [[Тождества Галлаи|тождеством Галлаи]]: <math>\alpha (G) + \tau (G) = |V|</math>, более того, дополнение к наибольшему независимому множеству вершин является наименьшим вершинным покрытием. Используя этот факт, в двудольном графе <math>G</math> можно найти <math>\alpha (G)</math> за полиномиальное время, поскольку задача о наименьшем вершинном покрытии в нём сводится к поиску наибольшего [[Паросочетание|паросочетания]]. |
||
В графе <math>G</math>, в котором отсутствуют изолированные вершины (вершины степени 0), также справедливо неравенство <math>\alpha (G) \le \rho (G)</math>, где <math>\rho (G)</math> — [[число рёберного покрытия]] графа <math>G</math>. В [[Двудольный граф|двудольном]] графе <math>G</math>, вследствие [[Теорема Кёнига (комбинаторика)|Теоремы Кёнига]], <math>\alpha (G) = \rho (G)</math>. |
В графе <math>G</math>, в котором отсутствуют изолированные вершины (вершины степени 0), также справедливо неравенство <math>\alpha (G) \le \rho (G)</math>, где <math>\rho (G)</math> — [[число рёберного покрытия]] графа <math>G</math>. В [[Двудольный граф|двудольном]] графе <math>G</math> без изолированных вершин, вследствие [[Теорема Кёнига (комбинаторика)|Теоремы Кёнига]], <math>\alpha (G) = \rho (G)</math>. |
||
== Ссылки == |
== Ссылки == |
||
Текущая версия от 10:58, 27 мая 2020
Число независимости графа — это размер наибольшего независимого множества вершин в нём.
Поскольку задача о независимом множестве является NP-полной, то неизвестны алгоритмы определения числа независимости в произвольном графе, работающие за полиномиальное время.
В любом графе число независимости связано с числом вершинного покрытия первым тождеством Галлаи: , более того, дополнение к наибольшему независимому множеству вершин является наименьшим вершинным покрытием. Используя этот факт, в двудольном графе можно найти за полиномиальное время, поскольку задача о наименьшем вершинном покрытии в нём сводится к поиску наибольшего паросочетания.
В графе , в котором отсутствуют изолированные вершины (вершины степени 0), также справедливо неравенство , где — число рёберного покрытия графа . В двудольном графе без изолированных вершин, вследствие Теоремы Кёнига, .
Ссылки
[править | править код]- László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.