89
правок
Изменения
→Основные определения
== Основные определения ==
{{Определение
|id = edge_colouring
}}
{{Определение
|id = chromativ_index
}}
== Некоторое оценки хроматического индекса ==
{{Лемма
|statement= <tex>\forall\ G(V, E) : \chi '(G) \geq \Delta (G)</tex>
|proof= Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно <tex>\Delta(G)</tex> рёбер. При этом, чтобы все они имели попарно различные цвета, они все должны иметь различные цвета, иначе найдётся пара рёбер инцидентных одной вершине имеющих одинаковый цвет.
}}
Заметим, что в теории графов доказывается более строгое неравенство, ограничивающее <tex>\chi '(G)</tex>. А именно что, <tex>\forall\ G(V, E) : \Delta (G) \leq \chi '(G) \leq \Delta (G) + 1</tex>. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.
В данной же статье мы оценим [[Рёберная покраска двудольного графа#chromativ_index | хроматический индекс]] двудольных графов и предъявим алгоритм их раскраски.
