48. Непланарность графов k5 и k3,3. Теорема Понтрягина-Куратовского.

Определение: Граф G есть максимальный планарный (плоский) граф, если G планарный, то при прибавлении к G любого ребра, он перестает быть планарным (плоским)

Замечание: Любая грань максимального плоского (p,q) – графа, есть 3-цикл (треугольник). Подставляя в формулу следствия n=3, получим q ≤ 3*(p-2)/(3-2) = 3*p – 6, т.е. для максимального плоского (p,q) — графа G число ребер q ≤ 3p – 6. Тогда для немаксимального плоского (p,q) графа G (который получается удалением некоторых ребер из некоторого максимального графа) число ребер q ≤ 3*p – 6 тем более. Т.к. планарный граф изоморфен некоторому плоскому графу, то для планарного (p,q) графа G число ребер q ≤ 3p – 6 тоже.

Критерий Понтрягина-Куратовского

Вершину степени 2 в графе назовем проходной. Операция добавления проходной вершины в ребро e=(u,v) в графе G = (V,E), состоит в удалении ребра е из Е и добавлении к V новой вершины w и в добавлении в граф G двух ребер (u,w) и (w,v). Операция удаления проходной вершины v в графе G=(V,E) есть удаление вершины v из V и замена двух е-инцидентных в Е ребер e’ = (u,v) и e’’=(v,w) на одно ребро e = (u,w).

Операция стягивания ребра e = (u,v) в графе G=(V,E) в точку состоит в удалении ребра е из Е и в объединении (склеивании) принадлежащих е вершин в одну вершину.

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

Замечание: Если графы геоморфны, то они планарны или непланарны одновременно.

Теорема Понтрягина — Куратовского: Граф G – планарен ⇔ G не содержит подграфов гемеоморфных графам K₅ или K_3,3.

49. Цикломатическое число графа

• Цикломатическое число графа — минимальное число рёбер, которые надо удалить, чтобы граф стал ациклическим. Для связного графа существует соотношение:   где   — цикломатическое число,  — число компонент связности графа,   — число рёбер, а   — число вершин.

50. Хроматические графы. Теорема о раскраске планарных графов в пять цветов. Гипотеза четырех кра-сок. Теорема Хивуда.

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

Раскраска в 5 цветов

Теорема:

Пусть граф   - планарный. Тогда

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

u и смежные ей вершины Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной. Обозначим за   - возвращаемую вершину,   - вершину, покрашенную в   цвет. Если среди вершин, смежных  , есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим  . Иначе, уложим полученный после удаления   граф на плоскость, вернём вершину   (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке. Попробуем покрасить   в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину   в цвет 3. Если среди смежных ей вершин есть вершины  , покрасим их в цвет 1, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода: мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме 1   3, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без   был раскрашен правильно. дойдём до вершины, смежной  , исходно имевшей цвет 3, которую перекрасить в 1 нельзя (  теперь имеет цвет 1). Если этот процесс был успешно завершён, то получили правильную раскраску. Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в графе есть цикл  . Тогда попытаемся таким же образом перекрасить   в цвет 2, а смежную ей   в цвет 4 (со последующими перекрасками). Если удастся - раскраска получена. Если нет, то получили ещё один цикл  . Но граф планарный, значит два полученных цикла пересекаются помимо вершины   по крайней мере ещё в одной, что невозможно, ведь вершины   первого цикла и   второго - разных цветов. Значит такой случай наступить не мог.

Данная теорема была доказана Кеннетом Аппелем и Вольфгангом Хакеном. Их доказательство сводилось к рассмотрению порядка 2000 графов, 4-раскрашиваемость которых была проверена при помощи компьютера.

Теорема (о пяти красках, Теорема Хивуда): Всякий связный планарный граф G можно правильно раскрасить не более чем 5-ю красками.

Доказательство: Индукцией по числу p вершин графа. Базис: Для графа с числом вершин p= k ≤ 5 Теорема очевидна, ибо всякие 5 вершин раскрашиваемы 5-ю различными красками.

Предположение индукции: Допустим, что любой связный планарный граф с числом вершин k < p 5-раскрашиваем.

Шаг индукции: Покажем, что любой связный граф планарный граф с p вершинами 5-раскрашиваем. Т.к. граф G связен и планарен, то он имеет вершину v степени S ≤ 5. Удалим из G вершину V вместе с инцидентными ей ребрами. Полученный планарный граф G’=G-v имеет число вершин k < p и потому по предположении индукции все компоненты связности графа G’ можно раскрасить не более чем 5-ю цветами.

Возможны следующие случаи: 1) степень вершины v не более 4. Пусть для определенности deg(v)=4. Смежные с v вершины v₁, v₂,…,v₄ получат в G’ не более 4-х красок. Вершину v можно раскрасить любой из оставшейся красок.

2) Deg(v) = 5. Если смежные с v вершины v₁, v₂,…,v₅ имеют в совокупности r ≤ 4 красок, то вершину v можно раскрасить в оставшийся цвет. Пусть теперь вершины v₁, v₂,…,v₅ окрашены в 5 цветов C₁, C₂,…,C₅ соответственно. Натянем на вершины v₁, v₂,…,v₅ из G подграф H, соединив v₁, v₂,…,v₅ в H ребрами так, как они соединены в G. Подграф H – планарный ⇒ H не содержит K₅, значит в H среди вершин v₁, v₂,…,v₅существуют две несмежные вершины, ибо если все вершины v₁, v₂,…,v₅ смежны, то граф H содержит K₅, чего нет. Пусть для определенности вершины v₁,v₂ не смежны. Склеим v₁, v₂ с вершиной v. Полученный связный граф по предположению индукции 5-раскрашиваем. При этом 4 вершины v, v₃, v₅ получат: r ≤ 4 краски.

Расклеим назад v₁, v₂, v. Вершины v₁, v₂ оставим их прежний цвет (как у v). Тогда вершины v₁, v₂,…,v₅ [v₁, v₂ – одинаково раскрашены] имеют r ≤ 4 цвета. Вершину v перекрасим в один из оставшихся цветов. Шаг индукции установлен. Теорема доказана.

Замечание: Широко известна проблема четырех красок: любой плоский граф 4-раскрашиваем. Появилось много ошибочных доказательств. Последнее сообщение о доказательстве теоремы вышло в 1977 году на ≈ 180 листах (!!!).