Изменения

Перейти к: навигация, поиск

Рёберная раскраска двудольного графа

108 байт добавлено, 15:35, 19 ноября 2017
Нет описания правки
}}
Заметим, что в теории графов доказывается более строгое неравенство<ref>http://math.uchicago.edu/~may/REU2015/REUPapers/Green.pdf</ref>, ограничивающее <tex>\chi '(G)</tex>. А именно что, <tex>\forall\ G(V, E) : \Delta (G) \leqslant \chi '(G) \leqslant \Delta (G) + 1</tex>. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.
В данной же статье мы оценим хроматический индекс двудольных графов и предъявим алгоритм их раскраски.
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Раскраска двудольного графа в два цвета]]
 
==Примечания==
<references/>
==Источники информации==
89
правок

Навигация