Рёберная раскраска двудольного графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения)
Строка 1: Строка 1:
  
 
== Основные определения ==
 
== Основные определения ==
 
 
  
 
{{Определение
 
{{Определение
 
|id = edge_colouring
 
|id = edge_colouring
|neat = 1
+
|definition = '''Рёберной раскраской''' (англ. ''Edge colouring'') графа <tex>G(V, E)</tex> называется отображение <tex>\varphi:E \rightarrow \{c_{1}...c_{t}\}</tex> {{---}} ''множество красок'' такое, что для для любых двух различных рёбер <tex>e_{i}, e_{j}</tex> инцидентных одной вершине верно, что <tex> \varphi (e_{i}) \neq \varphi (e_{j})</tex>.  
|definition = '''Рёберной раскраской''' (англ. ''Edge colouring'') графа <tex>G(V, E)</tex> называется отображение <tex>\varphi:E \rightarrow \{c_{1}...c_{t}\}</tex> такое, что для для любых двух различных рёбер <tex>e_{i}, e_{j}</tex> инцидентных одной вершине верно, что <tex> \varphi (e_{i}) \neq \varphi (e_{j})</tex>.  
 
 
}}
 
}}
 
  
 
{{Определение
 
{{Определение
 
|id = chromativ_index
 
|id = chromativ_index
|neat = 1
+
|definition = '''Хроматическим индексом''' (англ. ''Chromatic index'') <tex>\chi '(G)</tex> графа <tex>G(V, E)</tex> называется такое минимальное число '''t''', что существует рёберная раскраска графа в '''t''' цветов.
|definition = '''Хроматическим индексом''' (англ. ''Chromatic index'') <tex>\psi '(G)</tex> графа <tex>G(V, E)</tex> называется такое минимальное число '''t''', что существует рёберная раскраска графа в '''t''' цветов.
 
 
}}
 
}}
 +
 +
== Некоторое оценки хроматического индекса ==
 +
{{Лемма
 +
|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 | хроматический индекс]] двудольных графов и предъявим алгоритм их раскраски.

Версия 00:19, 19 ноября 2017

Основные определения

Определение:
Рёберной раскраской (англ. Edge colouring) графа [math]G(V, E)[/math] называется отображение [math]\varphi:E \rightarrow \{c_{1}...c_{t}\}[/math]множество красок такое, что для для любых двух различных рёбер [math]e_{i}, e_{j}[/math] инцидентных одной вершине верно, что [math] \varphi (e_{i}) \neq \varphi (e_{j})[/math].


Определение:
Хроматическим индексом (англ. Chromatic index) [math]\chi '(G)[/math] графа [math]G(V, E)[/math] называется такое минимальное число t, что существует рёберная раскраска графа в t цветов.


Некоторое оценки хроматического индекса

Лемма:
[math]\forall\ G(V, E) : \chi '(G) \geq \Delta (G)[/math]
Доказательство:
[math]\triangleright[/math]
Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно [math]\Delta(G)[/math] рёбер. При этом, чтобы все они имели попарно различные цвета, они все должны иметь различные цвета, иначе найдётся пара рёбер инцидентных одной вершине имеющих одинаковый цвет.
[math]\triangleleft[/math]

Заметим, что в теории графов доказывается более строгое неравенство, ограничивающее [math]\chi '(G)[/math]. А именно что, [math]\forall\ G(V, E) : \Delta (G) \leq \chi '(G) \leq \Delta (G) + 1[/math]. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.

В данной же статье мы оценим хроматический индекс двудольных графов и предъявим алгоритм их раскраски.