89
правок
Изменения
Нет описания правки
{{Определение
|id = edge_colouring
|definition = '''Рёберной раскраской''' (англ. ''Edge colouring'') графа <tex>G(V, E)</tex> называется отображение <tex>\varphi:</tex> из множества рёбер <tex>E \rightarrow </tex> во множество красок <tex>\{c_{1} \ldots c_{t}\}</tex> {{---}} ''множество красок'' такое, что для для любых двух различных рёбер <tex>e_{i}, e_{j}</tex> , инцидентных одной вершине , верно, что <tex> \varphi (e_{i}) \neq \varphi (e_{j})</tex>.
}}
{{Лемма
|id = lem1
|about = о нижней оценке хроматического индекса|statement= <tex>\forall\ G(V, E) : \Delta (G) \leqslant \chi '(G) \geq </tex>, где <tex>\Delta (G)</tex>{{---}} максимальная степень вершины в графе|proof= Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно <tex>\Delta(G)</tex> рёбер. При этом, чтобы все они имели попарно различные цвета, они все должны иметь различные цвета, иначе найдётся пара различных рёбер , инцидентных одной вершине и имеющих одинаковый цвет.
}}
Заметим, что в теории графов доказывается более строгое неравенство<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>. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.
== Рёберная раскраска двудольного графа ==
{{Лемма
|id = lem2
|about = о совершенном паросочетании|statement= В [[Основные определения теории графов#defBiparateGraph | двудольном ]] <tex>k-</tex>-[[Основные определения теории графов#defRegularGraph |регулярном ]] графе с одинаковыми по размеру долями графе существует совершенное паросочетание.
|proof=
}}
{{Теорема
|statement= Существует рёберная раскраска двудольного графа <tex>G</tex> в <tex>\Delta(G)</tex> цветов. Иными слова словами, для двудольного графа <tex>\chi '(G) = \Delta(G)</tex>
|proof=
Докажем, что такой жадный алгоритм из пункта <tex>2</tex> всегда выполняет поставленную задачу.
Предположим, что это не так, и, не нарушая общности, у нас остались вершины в правой доле степени меньше <tex>\Delta(G)</tex>, а в левой таких вершин нет. Давайте посчитаем количество рёбер <tex>m</tex> в графе. Из левой доли исходит <tex>|L| \cdot \Delta(G)</tex> рёбер. В правую же приходит не более <tex>|R| \cdot \Delta(G)</tex> рёбер, но так как существует вершина степени меньше <tex>\Delta(G)</tex>. То , то неравенство строгое. Получается <tex>|L| \cdot \Delta(G) = m < |R| \cdot \Delta(G)</tex>. Но в нашем графе <tex>|L| = |R|</tex>. Следовательно <tex>\Delta(G) < \Delta(G)</tex>, что приводит нас к противоречию.
==Примечания==
<references/>