|
|
| (не показано 7 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | == Введение ==
| |
| | | | |
| − |
| |
| − | == Раскраска в 6 цветов ==
| |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
| |
| − | |proof=
| |
| − | Докажем по индукции.
| |
| − | * База
| |
| − | Если граф содержит не более 6 вершин, то утверждение очевидно.
| |
| − | * Переход
| |
| − | Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
| |
| − |
| |
| − | 1.Покажем что найдётся вершина, степень которой не больше 5.
| |
| − |
| |
| − | Предположим это не так. Для любой вершины <tex> u_i </tex> верно <tex> deg </tex> <tex> u_i \ge 6 </tex>. Если выписать это неравенство для всех <tex> i </tex> и сложить, получим <tex> 2E \ge 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \le 3V-6 </tex>. Пришли к противоречию.
| |
| − | 2.Теперь, удалим из графа вершину со степенью не превышающей 5. По предположению индукции получившийся граф можно раскрасить в 6 цветов.
| |
| − | 3.Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
| |
| − | }}
| |
| − |
| |
| − | == Раскраска в 5 цветов ==
| |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
| |
| − | |proof=
| |
| − | До шага 3 в индукционном переходе доказательство такое же, как в предыдущей теореме. Покажем что для случая с 5-ю цветами можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
| |
| − |
| |
| − | Обозначим за <tex> u </tex> - возвращаемую вершину, <tex> v^{(k)} </tex> - вершина, покрашенная в <tex> k </tex> цвет.
| |
| − |
| |
| − | Если среди вершин, смежных <tex> u </tex> есть две вершины одного цвета, значит остаётся один свободный цвет, в который мы и покрасим <tex> u </tex>.
| |
| − |
| |
| − | Иначе, уложим полученный после шага 2 граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
| |
| − |
| |
| − | Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим вершину цвета 1 в цвет 3. Если среди смежных ей вершин найдётся вершина цвета 3, покрасим её в цвет 1, и так далее. Если этот процесс прекратится, то требуемая раскраска получена. В противном случае мы дойдём до вершины, смежной <tex> u</tex>, исходно имеющей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> уже перекрашена в цвет 1). Если перекраска не удалась, это означает что есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} u </tex>.
| |
| − |
| |
| − | Таким же образом попытаемся перекрасить <tex> u </tex> в цвет 2, а смежную ей <tex>w_1^{(2)}</tex> в цвет 4 (со последующими перекрасками). Если удастся - раскраска получена.
| |
| − |
| |
| − | Если нет, то получили ещё один цикл <tex> u w_1^{(2)} w_2^{(4)} w_3^{(2)} ... w_{k-1}^{(2)} w_k^{(4)} u </tex>. Но граф планарный, значит два полученных цикла вершинно пересекаются, что невозможно, так как они содержат вершины разных цветов (цвет <tex> u </tex> не учитываем) - противоречие
| |
| − | }}
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Раскраска в 4 цвета ==
| |
| − |
| |
| − | == Источники ==
| |
| − | # http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov
| |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Раскраски графов]]
| |
