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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Рёберная раскраска двудольного графа)
(не показано 8 промежуточных версий этого же участника)
Строка 4: Строка 4:
 
{{Определение
 
{{Определение
 
|id = edge_colouring
 
|id = edge_colouring
|definition = '''Рёберной раскраской''' (англ. ''Edge colouring'') графа <tex>G(V, E)</tex> называется отображение <tex>\varphi:E \rightarrow \{c_{1} \ldots 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</tex> из множества рёбер <tex>E</tex> во множество красок <tex>\{c_{1} \ldots c_{t}\}</tex>, что для для любых двух различных рёбер <tex>e_{i}, e_{j}</tex>, инцидентных одной вершине, верно <tex> \varphi (e_{i}) \neq \varphi (e_{j})</tex>.  
 
}}
 
}}
  
Строка 15: Строка 15:
 
{{Лемма
 
{{Лемма
 
|id = lem1
 
|id = lem1
 +
|about = о нижней оценке хроматического индекса
 
|statement= <tex>\forall\ G(V, E) : \Delta (G) \leqslant \chi '(G)</tex>, где <tex>\Delta (G)</tex> {{---}} максимальная степень вершины в графе
 
|statement= <tex>\forall\ G(V, E) : \Delta (G) \leqslant \chi '(G)</tex>, где <tex>\Delta (G)</tex> {{---}} максимальная степень вершины в графе
|proof= Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно <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>. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.  
+
Заметим, что в теории графов доказывается более строгое неравенство<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
 
|id = lem2
|statement= В [[Основные определения теории графов#defBiparateGraph | двудольном]] <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярном]] с одинаковыми по размеру долями графе существует совершенное паросочетание.
+
|about = о совершенном паросочетании
 +
|statement= В [[Основные определения теории графов#defBiparateGraph | двудольном]] <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярном]] графе с одинаковыми по размеру долями существует совершенное паросочетание.
 
|proof=  
 
|proof=  
Возьмём <tex>L</tex> {{---}} произвольное подмножество левой доли. Рассмотрим подграф образованный <tex>L</tex> и множеством всех их соседей из правой доли <tex>R</tex>. Все вершины левой доли нашего подграфа будут иметь степень <tex>k</tex>, а степени вершин правой доли '''не превосходит''' <tex>k</tex>.
+
Возьмём <tex>L</tex> {{---}} произвольное подмножество левой доли. Рассмотрим подграф образованный <tex>L</tex> и множеством всех их соседей из правой доли <tex>R</tex>. Все вершины левой доли нашего подграфа будут иметь степень <tex>k</tex>, а степени вершин правой доли '''не превосходят''' <tex>k</tex>.
  
Посчитаем количество рёбер <tex>m_{L}</tex>  в данном подграфе. В силу его двудольности это число будет равняться сумме степеней вершин одной из долей. <tex>m_{L} = \underset{{v\in L}}{\sum} deg(v) = |L|\cdot k = \underset{{u\in R}}{\sum} deg(u) \leqslant |R|\cdot k</tex>. Из этого мы получаем, что <tex>|L|\leqslant |R|</tex>.
+
Посчитаем количество рёбер <tex>m_{L}</tex>  в данном подграфе. В силу его двудольности, это число будет равняться сумме степеней вершин одной из долей. <tex>m_{L} = \underset{{v\in L}}{\sum} deg(v) = |L|\cdot k = \underset{{u\in R}}{\sum} deg(u) \leqslant |R|\cdot k</tex>. Из этого мы получаем, что <tex>|L|\leqslant |R|</tex>.
  
 
Значит в данном графе выполняется [[Теорема Холла | Теорема Холла]]. Из чего следует, что в нём есть совершенное паросочетание.
 
Значит в данном графе выполняется [[Теорема Холла | Теорема Холла]]. Из чего следует, что в нём есть совершенное паросочетание.
Строка 36: Строка 37:
  
 
{{Теорема
 
{{Теорема
|statement= Существует рёберная раскраска двудольного графа <tex>G</tex> в <tex>\Delta(G)</tex> цветов. Иными слова для двудольного графа <tex>\chi '(G) = \Delta(G)</tex>
+
|statement= Существует рёберная раскраска двудольного графа <tex>G</tex> в <tex>\Delta(G)</tex> цветов. Иными словами, для двудольного графа <tex>\chi '(G) = \Delta(G)</tex>
 
|proof=  
 
|proof=  
 
В доказательство рассмотрим следующий алгоритм поиска такой раскраски:
 
В доказательство рассмотрим следующий алгоритм поиска такой раскраски:
  
# Для начала сделаем доли графа одинаковыми по размеру, дополнив меньшую из долей необходимым количеством [[Основные определения теории графов#isolated_vertex | изолированных вершин]]
+
# Для начала сделаем доли графа одинаковыми по размеру, дополнив меньшую из долей необходимым количеством [[Основные определения теории графов#isolated_vertex | изолированных вершин]];
# Следующим жадным алгоритмом сделаем его <tex>\Delta(G)</tex>-регулярным: пока граф не регулярный возьмём вершину левой доли степени меньше <tex>\Delta(G)</tex> и аналогичную вершину правой доли. Соединим их ребром
+
# Следующим жадным алгоритмом сделаем его <tex>\Delta(G)</tex>-регулярным: пока граф не регулярный возьмём вершину левой доли степени меньше <tex>\Delta(G)</tex> и аналогичную вершину правой доли. Соединим их ребром;
# Мы получили регулярный двудольный граф с равными доля. По нашей лемме в таком графе есть совершенное паросочетание. Найдём его, например [[Алгоритм Куна для поиска максимального паросочетания | алгоритмом Куна]], и удалим из графа.
+
# Мы получили регулярный двудольный граф с равными долями. По лемме о совершенном паросочетании в таком графе есть совершенное паросочетание. Найдём его, например [[Алгоритм Куна для поиска максимального паросочетания | алгоритмом Куна]], и удалим из графа;
# Заметим что граф всё ещё остался регулярным, так как степень каждой вершины уменьшилась на 1. Будем повторять процесс, пока в графе есть рёбра.
+
# Заметим, что граф всё ещё остался регулярным, так как степень каждой вершины уменьшилась на <tex>1</tex>. Будем повторять процесс, пока в графе есть рёбра;
# По итогу мы разобьём рёбра графа на <tex>\Delta(G)</tex> совершенных паросочетаний.
+
# В итоге мы разобьём рёбра графа на <tex>\Delta(G)</tex> совершенных паросочетаний;
# В конце нам остаётся каждое паросочетание покрасить в свой цвет и удалить рёбра, которых не было в изначальном графе
+
# В конце нам остаётся каждое паросочетание покрасить в свой цвет и удалить рёбра, которых не было в изначальном графе;
  
  
Докажем, что такой жадный алгоритм из пункта 2 всегда выполняет поставленную задачу.
+
Докажем, что жадный алгоритм из пункта <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>, что приводит нас к противоречию
+
Предположим, что это не так, и, не нарушая общности, у нас остались вершины в правой доле степени меньше <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>, что приводит нас к противоречию.
  
  
Строка 70: Строка 71:
 
* [https://ru.wikipedia.org/wiki/Рёберная_раскраска Википедия {{---}} Рёберная раскраска]
 
* [https://ru.wikipedia.org/wiki/Рёберная_раскраска Википедия {{---}} Рёберная раскраска]
  
[[Категория: Двудольные графы]]
 
 
[[Категория: Раскраски графов]]
 
[[Категория: Раскраски графов]]
 +
[[Категория: Алгоритмы и структуры данных]]

Версия 16:39, 20 ноября 2017

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

Определение:
Рёберной раскраской (англ. Edge colouring) графа [math]G(V, E)[/math] называется отображение [math]\varphi[/math] из множества рёбер [math]E[/math] во множество красок [math]\{c_{1} \ldots 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) : \Delta (G) \leqslant \chi '(G)[/math], где [math]\Delta (G)[/math] — максимальная степень вершины в графе
Доказательство:
[math]\triangleright[/math]
Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно [math]\Delta(G)[/math] рёбер. При этом, чтобы все они имели попарно различные цвета, они все должны иметь различные цвета, иначе найдётся пара различных рёбер, инцидентных одной вершине и имеющих одинаковый цвет.
[math]\triangleleft[/math]

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


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

Лемма (о совершенном паросочетании):
В двудольном [math]k[/math]-регулярном графе с одинаковыми по размеру долями существует совершенное паросочетание.
Доказательство:
[math]\triangleright[/math]

Возьмём [math]L[/math] — произвольное подмножество левой доли. Рассмотрим подграф образованный [math]L[/math] и множеством всех их соседей из правой доли [math]R[/math]. Все вершины левой доли нашего подграфа будут иметь степень [math]k[/math], а степени вершин правой доли не превосходят [math]k[/math].

Посчитаем количество рёбер [math]m_{L}[/math] в данном подграфе. В силу его двудольности, это число будет равняться сумме степеней вершин одной из долей. [math]m_{L} = \underset{{v\in L}}{\sum} deg(v) = |L|\cdot k = \underset{{u\in R}}{\sum} deg(u) \leqslant |R|\cdot k[/math]. Из этого мы получаем, что [math]|L|\leqslant |R|[/math].

Значит в данном графе выполняется Теорема Холла. Из чего следует, что в нём есть совершенное паросочетание.
[math]\triangleleft[/math]
Теорема:
Существует рёберная раскраска двудольного графа [math]G[/math] в [math]\Delta(G)[/math] цветов. Иными словами, для двудольного графа [math]\chi '(G) = \Delta(G)[/math]
Доказательство:
[math]\triangleright[/math]

В доказательство рассмотрим следующий алгоритм поиска такой раскраски:

  1. Для начала сделаем доли графа одинаковыми по размеру, дополнив меньшую из долей необходимым количеством изолированных вершин;
  2. Следующим жадным алгоритмом сделаем его [math]\Delta(G)[/math]-регулярным: пока граф не регулярный возьмём вершину левой доли степени меньше [math]\Delta(G)[/math] и аналогичную вершину правой доли. Соединим их ребром;
  3. Мы получили регулярный двудольный граф с равными долями. По лемме о совершенном паросочетании в таком графе есть совершенное паросочетание. Найдём его, например алгоритмом Куна, и удалим из графа;
  4. Заметим, что граф всё ещё остался регулярным, так как степень каждой вершины уменьшилась на [math]1[/math]. Будем повторять процесс, пока в графе есть рёбра;
  5. В итоге мы разобьём рёбра графа на [math]\Delta(G)[/math] совершенных паросочетаний;
  6. В конце нам остаётся каждое паросочетание покрасить в свой цвет и удалить рёбра, которых не было в изначальном графе;


Докажем, что жадный алгоритм из пункта [math]2[/math] всегда выполняет поставленную задачу.

Предположим, что это не так, и, не нарушая общности, у нас остались вершины в правой доле степени меньше [math]\Delta(G)[/math], а в левой таких вершин нет. Давайте посчитаем количество рёбер [math]m[/math] в графе. Из левой доли исходит [math]|L| \cdot \Delta(G)[/math] рёбер. В правую же приходит не более [math]|R| \cdot \Delta(G)[/math] рёбер, но так как существует вершина степени меньше [math]\Delta(G)[/math], то неравенство строгое. Получается [math]|L| \cdot \Delta(G) = m \lt |R| \cdot \Delta(G)[/math]. Но в нашем графе [math]|L| = |R|[/math]. Следовательно [math]\Delta(G) \lt \Delta(G)[/math], что приводит нас к противоречию.


Таким образом мы нашли раскраску двудольного графа в [math]\Delta(G)[/math] цветов и предъявили алгоритм её получения. А по лемме о нижней оценки, меньше цветов использовать нельзя. Следовательно [math]\chi '(G) = \Delta(G)[/math]

Заметим, что наш жадный алгоритм может проводить кратные рёбра в графе. Однако ни лемма о совершенном паросочетании, ни Теорема Холла не используют в своём доказательстве отсутствие таковых.
[math]\triangleleft[/math]

См. также

Примечания

Источники информации