Оценка хроматического числа плоского графа

Теорема о пяти красках.

Теорема 3: (Понтрягин - Куратовский). Для того чтобы граф был плоским, необходимо и достаточно, чтобы он не содержал в качестве подграфов графы или из условия теоремы 2.

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

В § 2 уже встречалась задача о раскраске графов. Напомним ее постановку. Пусть дана географическая карта страны, в которой имеется несколько областей. Требуется окрасить каждую область так, чтобы любые две области, граничащие между собой, были окрашены в различные цвета. При этом «граничащими» областями называются области, которые граничат по некоторой линии (а не в точке). Во введении было показано, что эта задача может быть сведена к задаче о раскраске плоского графа: имея некоторое число красок, раскрасить каждую вершину одной из этих красок таким образом, чтобы любые две смежные вершины имели различную окраску.

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

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

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

Теорема 1: Любой плоский граф 5-хроматичен.

Прежде чем доказывать теорему 1, докажем лемму, которая имеет чисто технический характер и будет использоваться при доказательстве теоремы.

Лемма 1: В любом простом связном плоском графе без тупиков и перешейков существует вершина степени меньшей или равной пяти.

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

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

Подставим теперь оценки: в выражение для эйлеровой характеристики графа :

.

Это противоречит тому, что (по теореме 1 §5).

Доказательство теоремы 1: Рассмотрим следующие операции над графом:

1) удаление тупика (вместе с вершиной);

2) склеивание двух ребер, инцидентных одной и той же паре вершин , ;

3) удаление перешейка.

Очевидно, что если после проведения любой из указанных операций над графом его хроматическое число стало равным , то хроматическое число исходного графа есть . Кроме того, после применения некоторого количества операций 1) - 3) получается простой граф, состоящий из конечного числа связных компонент, в каждой из которых нет тупиков и перешейков. Если хроматические числа этих компонент есть , то хроматическое число графа есть . Из этих рассуждений видно, что достаточно доказать следующее утверждение: хроматическое число любого простого связного плоского графа без тупиков и перешейков меньше или равно пяти, т. е. такой граф всегда 5-хроматичен.

Докажем это утверждение. Оно будет доказываться индукцией по числу ребер графа . При этом будет использована лемма 1.

Базис индукции. При теорема верна, так как единственным связным графом без тупиков и перешейков с является треугольник. Треугольник 3-хроматичен, а, следовательно, и 5-хроматичен.

Индукционный шаг. Пусть теорема верна для любого графа с количеством ребер . Рассмотрим (простой плоский без тупиков и перешейков) граф с . По лемме 1 в этом графе существует, по меньшей мере, одна вершина степени меньшей или равной пяти. Зафиксируем одну из таких вершин . Будем различать три случая.

Случай 1. Пусть . Рассмотрим граф , полученный из графа удалением вершины и инцидентных ей ребер. Число ребер такого графа, очевидно, меньше . Применим индукционное предположение, согласно которому этот граф 5-хроматичен. Рассмотрим какую-либо правильную раскраску с помощью пяти красок.

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

Случай 2. Пусть , и не все соседние ребра, выходящие из вершины , образуют треугольники (рис. 19).

Склеим две вершины, смежные с вершиной , инцидентные двум соседним ребрам и не соединенные между собой ребром (на рисунке и ). Применяя преобразование 2), получим из получившегося графа простой граф, в котором число ребер меньше или равно . Рассмотрим существующую по предположению индукции правильную раскраску полученного графа. Она индуцирует некоторую раскраску графа, в которой вершины, ранее склеенные (и ) имеют одинаковую окраску. Полученная раскраска будет правильной, так как эти вершины в графе непосредственно не связаны ребром, и в предположениях случая 2 индукционный шаг также завершен.

Случай 3. Если и вершина есть центр пятиугольника (рис. 20а). В этом случае обязательно должны существовать две вершины, не соединенные непосредственно ребром, из числа пяти, окружающих (на рисунке это вершины и ), так как в противном случае эти пять вершин образовывали бы второй из графов, упомянутых в теореме 1 §5, и, следовательно, граф не был бы плоским. Удалим вершину с инцидентными ей ребрами (рис. 20б) и склеим и (рис. 20в). Число ребер полученного графа меньше . Рассмотрим его правильную раскраску с помощью пяти красок. Она индуцирует правильную (так как и не соединены ребром непосредственно) раскраску графа , в которой не раскрашена вершина . Заметив, что из пяти вершин, соединенных с вершиной непосредственно, две (и ) раскрашены одинаково. Выводим отсюда, что эта раскраска может быть дополнена до правильной раскраски графа . В предположениях случая 3 индукционный шаг завершен.

Приведем теперь пример плоского графа, для правильной раскраски которого недостаточно трех красок. Такой граф изображен на рис. 21.

Доказательство того, что для его раскраски недостаточно трех красок, вполне тривиально и предоставляется читателю.

2. Необходимые и достаточные условия 1-й 2-хроматичности. Необходимые и достаточные условия даются следующей теоремой.

Теорема 2: Граф 1 -хроматичен тогда и только тогда, когда он не содержит ни одного ребра. Граф 2 -хроматичен тогда и только тогда, когда он не содержит циклов нечетной длины.

Доказательство: Первое утверждение теоремы вполне очевидно. Для доказательства второго, очевидно, можно ограничиться случаем связного графа .

Рассмотрим связный граф и рассмотрим частичное дерево этого графа, полученное удалением из него ребер . Очевидно, что оно может быть раскрашено двумя красками. Если в начальном графе был некоторый цикл нечетной длины, то концы того из ребер , которое участвует в этом цикле, окажутся раскрашенными одинаково, ибо путь по дереву, соединяющий эти две вершины, состоит из четного количества ребер. Таким образом, если бы граф мог быть правильно раскрашен двумя красками, то эта раскраска была бы правильной и для частичного дерева; но тогда концы ребра были бы раскрашены одинаково, что невозможно.

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

Дата добавления: 2014-01-04; Просмотров: 737; Нарушение авторских прав?; Мы поможем в написании вашей работы!