Раскраска графов. 
Геометрическая теория графов

Раскраска граней плоского графа

Пусть задан плоский геометрический граф G (V, E. F). Говорят, что грани этого графа правильно раскрашены, если каждой грани из F присвоен определенный цвет, причем, любым двум смежным граням присвоены разные цвета. Если грани графа G правильно раскрашены, то две грани, имеющие общее ребро, будут иметь разные цвета, а грани, имеющие общую вершину, но не имеющие общего ребра, могут быть одноцветными. Ясно, что одноцветными могут быть также грани, не имеющие общих вершин (а, следовательно, и общих ребер).

Если иметь в запасе достаточно большое число цветов (например, равное количеству граней), то правильная раскраска всегда возможна. Задача состоит в том, чтобы для заданного плоского графа определить минимальное число цветов, необходимых для правильной раскраски его граней.

Эта задача тесно связана с проблемой раскраски политической контурной карты. Действительно, такую карту можно рассматривать как плоский граф, грани которого есть территории государств, ребра — границы между различными государствами, а вершины пересечения границ. Правильная раскраска граней такого графа приведет к тому, что любая пара государств, имеющих общую границу, будет иметь на географической карте разные цвета.

Очень важным результатом в теории раскраски граней плоского графа является следующая теорема.

Теорема 15. Плоский граф не может содержать пять попарно смежных граней^[1].

Доказательство. Предположим противное, что в число граней плоского графа G входят пять попарно смежных граней hi, h₂, h₃, h₄ и h₅. Рассмотрим граф G', двойственный для G. Граням hi, h₂, h$, h₄ и h; графа G соответствуют пять вершин H'_h Н'₂, Н'_}, Н'₄ и Н'₅ графа G', которые должны быть попарно смежны, так как попарно смежными являются соответствующие им грани в графе G. Следовательно, граф G' содержит частичный граф, являющийся полным графом с пятью вершинами Н', Н'₂, H’s, Н'₄ и Н'₅ (один из графов Понтрягина-Куратовского). Следовательно, по теореме Понтрягина-Куратовского, граф G' не является плоским. Мы получили противоречие, так как граф, двойственный плоскому графу, также является плоским графом.

Итак, можно достаточно просто изобразить граф, имеющий четыре попарно граничащих грани (см. рис. 113), но невозможно добавить пятую грань, которая граничила бы с четырьмя остальными. По-видимому, основываясь на этом факте, в 1879 г. на заседании английского географического общества А. Кэли высказал гипотезу о том, что любую географическую карту можно правильно раскрасить при помощи четырех цветов.

Рис. ИЗ

Необходимость четырех красок легко устанавливается на простом примере. Так граф, представленный на рисунке 113, содержит четыре попарно граничащих грани, для раскраски которых необходимо 4 цвета.

Если бы удалось привести пример графа, для раскраски которого недостаточно четырех красок, то гипотеза А. Кэли была бы опровергнута. Пока такого примера не найдено, и в то же время, до сих пор не доказано, что четырех цветов достаточно для раскраски граней любого плоского графа. Все известные на сегодняшний день попытки доказательства справедливости этой гипотезы не могут быть признаны достаточно строгими, и «проблема четырех красок» остается открытой.

Теорема 16 (теорема о пяти красках). Любой плоский граф допускает правильную окраску граней в пять цветов.

Доказательство. Предварительно покажем, что задачу о раскраске такого графа можно решать в предположении его связности. Действительно, если граф не связен и имеет, например, две компоненты связности, то одна из его компонент связности Gi целиком лежит внутри некоторой грани h другой компоненты связности G2. Если каждая из этих компонент допускает правильную раскраску граней, то, выбирая одинаковыми цвет внешней грани для G/ и цвет грани h для G2, мы получим правильную раскраску всего графа.

Теперь заметим, что задачу о раскраске можно решать в предположении, что степень каждой вершины графа не меньше трех. Действительно, если степень некоторой вершины А связного графа равна 1, то этой вершине инцидентно ровно одно ребро а, которое примыкает к единственной грани, и удаление ребра а вместе с висячей вершиной А не изменит количества граней и не повлияет на число необходимых цветов. Если же в графе имеется вершина А степени 2, то либо связный граф состоит только из вершины А и петли в этой вершине, либо к вершине А примыкают два ребра aj и а* В первом случае граф имеет всего две грани (внутри петли и снаружи), и для его правильной раскраски хватит уже двух цветов. Во втором случае удаление вершины А и объединение инцидентных ей ребер a_f и ф в одно ребро а не изменит количества граней в графе и не увеличит количества необходимых цветов.

Итак, предположим, что имеется связный плоский граф G, степень каждой вершины которого не меньше трех. Проведем доказательство теоремы методом математической индукции по числу граней /. База индукции очевидна, так как если число граней / меньше или равно пяти, то пяти красок достаточно для правильной раскраски всех граней. Пусть задача имеет положительное решение для / < к. Рассмотрим граф с f=k+l гранями и покажем, что он также может быть правильно раскрашен.

Так как степень каждой вершины графа не меньше трех, то этот граф имеет хотя бы одну грань К ограниченную менее чем шестью ребрами, т. е. cr*(h)<5 (см. задачу 9 из пункта 2.3). Возможны пять случаев.

Случай 1 {грань И ограничена одним ребром).

В этом случае границей грани h является петля а, целиком лежащая внутри некоторой грани g (см. рис.

114). Удалив петлю а, получим граф, имеющий к граней (грани hug сольются в одну грань hcg). По предположению индукции, Рис. 114

полученный граф может быть раскрашен пятью цветами. Пусть при этом грань hUg окрашена цветом а. Восстановив петлю а, перекрасим грань h в один из четырех цветов, отличных от цвета а. Очевидно, что в результате мы получим правильную окраску графа G.

Случай 2 {грань h ограничена двумя ребрами).

Если грань h ограничена парой параллельных ребер а/ и й2 (см. рис. 115), то эта грань граничит не более чем с двумя другими гранями g и и. Удалим ребро а, а ребра Ь,

02 и с объединим в одно Рис. 115

ребро. В результате грани.

hug сольются в одну грань hUg, и полученный граф будет иметь к граней. По предположению индукции, он может быть окрашен пятью цветами. Пусть при этом грань hUg окрашена цветом а, а грань и — цветом Д Восстановив ребро a_h перекрасим грань h в один из трех цветов, отличных от а и Д Очевидно, что в результате мы получим правильную окраску графа G.

Случай 3 (грань h ограничена тремя ребрами). Если грань h ограничена тремя ребрами а/, а2 и аз, то она граничит не более чем с тремя гранями g, и и w (см. рис. 116). Удалим ребро ai. В результате грани hug сольются в одну грань hUg, и полученный граф будет иметь к граней. По предположению индукции, он может быть окрашен пятью цветами. Пусть при этом грань hUg окрашена цветом а, грань и — цветом Д, а грань и — цветом у. Восстановив ребро а/, перекрасим грань h в один из двух цветов, отличных от а, /3 и у. Очевидно, что в результате мы получим правильную окраску графа G.

Рис. 116.

Рис. 117.

Случай 4 (грань h ограничена четырьмя ребрами). Если грань h ограничена четырьмя ребрами а/, а₂, аз и а₄, то она граничит не более чем с четырьмя гранями g_h g₂, g3 и g₄ (см. рис. 117). Удалим ребро а/. В результате грани h и gj сольются в одну грань hUg, и полученный граф будет иметь к граней. По предположению индукции, он может быть окрашен пятью цветами. Пусть при этом грань hUg_t окрашена цветом а, грань g₂ - цветом Д грань g_} — цветом у, а грань g4 - цветом 8. Восстановив ребро а/, перекрасим грань h в цвет, отличный от а, Д у и 5. Очевидно, что в результате мы получим правильную окраску графа G.

ничена пятью ребрами). Если грань h ограничена пятью ребрами at, 02, аз, а₄ и аз, то она граничит не более чем с пятью гранями g_h g₂, g3, g4 и gs (см. рис. 118). Так как ни в каком Случай 5 (грань h огра

плоском графе не существует пяти граней, каждая пара из которых граничит друг с другом (см. теорему 15), то _{рис /Jg}

среди пяти граней g/, g2, g3,

g₄ и g_s можно указать пару граней, которые не имеют общего ребра. Пусть, для определенности, это грани gj и g> Удалим ребра <�з_; и аз. В результате грани h, gi и gs сольются в одну грань hUgiUg₃, и полученный граф будет иметь к-1 граней. По предположению индукции, он может быть раскрашен пятью цветами. Пусть при этом грань hUg, Ug₃ окрашена цветом а, грань g2 — цветом Д грань g₄ — цветом Y, а грань g_s — цветом S. Восстановив ребра a_t и аз , перекрасим грань h в цвет, отличный от ос, Д у и 8. При этом грани gi и gs будут окрашены в одинаковый цвет а. Так как эти две грани не граничат между собой, то в результате мы получим правильную окраску графа G.

Рис. 119.

Теорема 17 (теорема о двух красках). Для того чтобы плоский граф допускал правильную раскраску граней в два цвета, необходимо и достаточно, чтобы все вершины этого графа были четными.

Доказательство.

Необходимость теоремы очевидна, так как если какая-то вершина имеет нечетную степень, то примыкающие к ней грани невозможно раскрасить двумя цветами (см. рис. 119).

Достаточность докажем методом математической индукции по количеству ребер. Пусть граф имеет только четные вершины. Если е=0, то граф имеет только одну грань и для его раскраски двух цветов более чем достаточно. Пусть граф, имеющий только четные вершины и содержащий е< к ребер, допускает правильную окраску граней в два цвета. Рассмотрим граф, содержащий к+1 ребер. Выделим в этом графе простой цикл из ребер, ограничивающих некоторую грань (см. рис. 120а) и удалим все ребра этого цикла. В результате получим граф, имеющий менее к ребер. Все вершины этого графа также будут четными, так как исходный граф имел только четные вершины. По предположению индукции, он допускает раскраску граней в два цвета (см. рис. 1206). Восстановим удаленный цикл и поменяем цвет грани, лежащей внутри этого цикла, на противоположный (см. рис. 120в). Ясно, что в результате мы получим правильную окраску граней исходного графа в два цвета.

Рис. 120.

Напомним, что граф, все вершины которого имеют третью степень, называется кубическим графом (или однородным графом третьей степени). В теории раскраски плоские кубические графы называются также нормальными картами. Задачу о раскраске граней плоского графа всегда можно свести к задаче о раскраске нормальной карты. Действительно, в доказательстве теоремы 16 отмечалось, что задачу раскраски достаточно уметь решать для графа, степень каждой вершины которого больше или равна трем. Теперь покажем, что задача о раскраске такого графа сводится к задаче о раскраске кубического графа. Пусть в графе имеется некоторая вершина, степень которой больше трех и равна п. Проведем окружность с центром в этой вершине, выбирая ее радиус настолько малым, чтобы она пересекла лишь п ребер, инцидентных этой вершине. Отмечая точки пересечения, исходную вершину степени п заменим п вершинами степени 3 (см. рис. 121). Проделывая эту операцию с каждой вершиной, степень которой больше трех, получим кубический граф, называемый нормальной картой исходного графа. Если правильно раскрасить грани этой карты, а затем стянуть в точки добавленные окружности, то получим правильную раскраску исходного графа с тем же количеством цветов.

Рис. 121.

Теорема 18 (теорема о трех красках). Для того чтобы плоский кубический граф допускал правильную раскраску граней в три цвета, необходимо и достаточно, чтобы каждая его грань была ограничена четным числом ребер.

Доказательство.

Необходимость теоремы очевидна, так как если некоторая грань ограничена нечетным количеством ребер, то правильная раскраска граней невозможна (см. рис. 122).

Доказательство достаточности проведем методом математической индукции по количеству граней. Плоский кубический граф содержит как минимум три грани. Действительно, так как 2е = 3v, то из формулы Эйлера получаем, что / = 2 + —v.Hov — четно и больше нуля,.

следовательно f>3. База индукции очевидна, так как кубический граф, содержащий три грани, допускает правильную окраску в три цвета. Заметим, что существует только один такой граф. Он имеет две вершины, три ребра, и так как каждая его грань ограничена четным количеством ребер, то он имеет вид, представленный на рисунке 123.

Предположим теперь, что кубический граф, содержащий f < к граней, каждая из которых ограничена четным числом ребер, допускает требуемую раскраску. Рассмотрим аналогичный граф с к +1 гранью. Так как степень каждой вершины равна трем, то в графе существует хотя бы одна грань И, ограниченная менее чем шестью ребрами (см. задачу 9 из пункта 2.3). Но по условию каждая грань ограничена четным количеством ребер. Следовательно, грань h ограничена либо двумя, либо четырьмя ребрами.

Случай 1 (грань h ограничена двумя ребрами). Если грань h ограничена парой параллельных ребер а/ и 02 (см. рис. 124), то эта грань граничит не более чем с двумя другими гранями g и и. Удалим ребро а/, а ребра b,.

02 и с объединим в одно ребро. В результате грани hug сольются в одну грань hUg, и полученный граф будет иметь к граней. Заметим, что усеченный граф останется кубическим, а каждая его грань по-прежнему будет ограничена четным числом ребер (число ребер грани и уменьшилось на два, а грань hUg имеет на два ребра меньше, чем имела грань g). По предположению индукции, этот граф может быть окрашен тремя цветами. Пусть при этом грань h Ug окрашена цветом ос, а грань и — цветом Д Восстановив ребро a_h перекрасим грань, А в свободный цвет, отличный от а и Д Очевидно, что в результате мы получим правильную окраску исходного графа.

Случай 2 (грань А ограничена четырьмя ребрами). Доказательство этого случая существенно основывается на следующем утверждении.

Лемма. Если плоская триангуляция G содержит частичный подграф, являющийся полным графом с четырьмя вершинами, то в графе G существуют нечетные вершины.

Доказательство леммы проведем методом математической индукции по количеству вершин. База индукции очевидна, так как при v=4 плоская триангуляция G является полным графом Н с четырьмя вершинами и все ее вершины нечетны (имеют степень три). Предположим, что в любой плоской триангуляции G, имеющей v ребер и содержащей подграф Н, существуют нечетные вершины. Рассмотрим аналогичную триангуляцию с v=k + l вершинами, и предположим противное, что все ее вершины четны.

1) Подграф Н имеет четыре треугольные грани АВС, ACD, ADB и BCD, и все остальные вершины и ребра графа G лежат внутри этих четырех треугольников (см. рис. 125). Рассмотрим три угла, окружающих некоторую вершину графа Н (пусть, для определенности, это вершина А). Так как, по предположению, все вершины графа G имеют четную степень, то к каждой вершине графа Н должно примыкать нечетное количество ребер из G, не входящих в Н (так как в Я к каждой вершине уже примыкает по три ребра). Следовательно, либо внутри каждого угла к вершине, А примыкает нечетное число ребер, либо в одном из углов — нечетное, а в двух других — четное. Грубо говоря, к каждой вершине графа Н примыкает либо три нечетных «угла», либо ровно один нечетный «угол» (см. рис. 126).

Рис. 125 Рис. 126

2) Рассмотрим одну из треугольных граней графа Н (например, грань АВС) и предположим, что внутри нее лежат еще другие вершины и ребра графа G. Докажем, что к двум вершинам из вершин А, В и С обязательно примыкает по нечетному количеству этих ребер. Т. е. докажем, что каждая грань графа Н содержит два нечетных «угла». Действительно, если бы к каждой вершине А, В и С примыкало четное число внутренних ребер грани АВС, то, удалив в графе G все вершины и ребра, лежащие внутри цикла АВС, мы получили бы плоскую триангуляцию Gi, имеющую только четные вершины и содержащую граф Н. Но так как в графе G/ вершин меньше, чем к, то, по предположению индукции, он должен содержать нечетные вершины. Итак, к одной из трех вершин А, В и С (например А) примыкает нечетное количество ребер, лежащих внутри цикла АВС. Но тогда обязательно к одной из вершин В или С также примыкает нечетное число таких ребер. В противном случае будет существовать граф, имеющий нечетное количество нечетных вершин (этот граф получается из G удалением всех ребер, не лежащих внутри АВС). Таким образом, к двум углам треугольника АВС примыкает по нечетному количеству его внутренних ребер (см. рис. 127).

^{Рис 127} Рис. 128.

• 3) Итак, каждая грань в графе Я имеет по два нечетных «угла», и к каждой вершине графа Я примыкает либо один нечетный «угол», либо три нечетных «угла». Следовательно, всего в графе Я четыре четных и восемь нечетных «углов». Поэтому, с точностью до переобозначения вершин, может существовать лишь единственная комбинация четных и нечетных «углов», примыкающих к графу Я (см. рис. 128).
• 4) Удалим все вершины и ребра графа G, лежащие внутри циклов АВС и ABD (рис. 128). В результате получим подграф G] графа G, который содержит граф Я, является плоской триангуляцией и имеет только четные вершины. Но этот граф имеет вершин меньше, чем к, и, по предположению индукции, он должен содержать нечетные вершины. Полученное противоречие показывает, что в любой плоской триангуляции, содержащей полный граф с четырьмя вершинами, существуют нечетные вершины.

Лемма доказана. Вернемся к доказательству теоремы о трех красках. Если грань h ограничена четырьмя.

ребрами а/, а₂, аз и а₄, то она граничит не более чем с четырьмя гранями gi, g₂, gj и Рис. 129 g₄ (см. рис. 129).

Если все грани плоского кубического графа ограничены четным числом ребер, то в этом графе не существует четырех попарно граничащих между собой граней. Действительно, предположим противное, что все грани плоского кубического графа G ограничены четным числом ребер и что в число граней этого графа входят четыре попарно смежных грани hi, h₂, hi и h₄. Рассмотрим граф G', двойственный для G. Граф G' является плоской триангуляцией, и все его вершины имеют четную степень. Граням hi, h₂, fej и h₄ графа G соответствуют четыре вершины #'/, Н'₂, Н’з и Н'₄ графа G', которые должны быть попарно смежны, так как попарно смежными являются соответствующие им грани в графе G. Следовательно, в граф G' входит частичный граф, являющийся полным графом с четырьмя вершинами H’i, Н'₂, Н’з и Н'₄. Но тогда, в силу леммы, в графе G существуют нечетные вершины. Получили противоречие.

Итак, грань gi не может граничить с g3, а грань g₂ не может граничить с g₄. Удалим ребра а_: и аз, и избавимся от вершин второй степени. В результате грани h, gi и g3 сольются в одну грань hUg, Ug3, полученный граф останется кубическим и будет иметь к-1 грань (см. рис. 130). По предположению индукции, он может быть окрашен пятью цветами. Пусть при этом грань hUgiUg₃ окрашена цветом а, а грань g₂ - цветом р.

panvv ох^ршгшш п pvupu, ^ J

перекрасим грань h в цвет у, отличный от а и Д Очевидно, что в результате мы получим правильную окраску графа G в три цвета.

Так как первоначально грань gi была ограничена четным числом ребер, то, начиная раскраску с грани g2 и двигаясь вокруг грани h Ug, Ug_} к грани g₄, нам придется пройти через нечетное число граней. Следовательно, грань g4 будет окрашена цветом Р, так же как и грань g₂. Восстановив все удаленные ранее вершины и ребра, перекрасим грань h в цвет у, отличный от а и Д Очевидно, что в результате мы получим правильную окраску графа G в три цвета.

• [1] Этот факт был впервые установлен в 1840 г. немецким математикомА.Ф. Мебиусом.