308
правок
Изменения
м
Перенесено из http://neerc.ifmo.ru/wiki/index.php?title=Хроматический_многочлен_планарного_графа
Иначе, уложим полученный после удаления <tex> u </tex> граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_2^{(3)} </tex>, покрасим их в цвет 1, и так далее. Рассмотрим 2 необычных вариантадве необычные ситуации, которые могут наступить во время обхода:
#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме 1 <tex>\leftrightarrow</tex> 3, и если мы получили две смежные вершины одного цвета, значит и до перекрасок в графе были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно.
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> теперь имеет цвет 1).
Тогда попытаемся таким же образом перекрасить <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> и какой-то другой, что невозможно, ведь вершины <tex> v_i </tex> первого цикла и <tex> w_j </tex> второго - разных цветов. В этом случае получаем противоречиеЗначит такой случай наступить не мог.
}}
