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

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

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

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

Раскраска в 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 листах (!!!).