3.3 Раскраска плоских графов в соответствии с теоремой о четырех красках
Прежде чем решать задачу о раскраске вершин произвольного графа, рассмотрим раскраску простейших подграфов произвольного конечного, связного плоского графа без петель икратных ребер. Слово «простейший» это не характеристика подграфа и тем более не термин, оно указывает на упрощенную структуру подграфа.
Цепи и циклы.
Простой цепью называют чередующуюся последовательность элементов графа — вершин и ребер, в которой все вершины, а, следовательно, и ребра, различны. Если крайние вершины совпадают, то такую простую цепь называют простым циклом.
Поскольку далее речь пойдет о раскраске вершин плоского графа не более, чем четырьмя красками, обозначим их четырьмя символами α, β, γ, δ, соответственно, и назовем эту проблему задачей о четырёх красках.
Вершины простой цепи и простого цикла с четным числом вершин раскрашиваются не более, чем двумя красками. Вершины цикла с нечетным числом вершин раскрашиваются не более, чем тремя красками. Действительно, двумя красками можно раскрасить чётное число вершин цикла, а оставшаяся одна нераскрашенная вершина смежна двум вершинам, раскрашенным двумя разными красками и, следовательно, эта вершина не может быть раскрашена теми цветами, которые имеют смежные с ней вершины, а должна быть раскрашена третьим цветом.
Цепи и циклы с прилегающими ребрами.
Рассмотрим конечную простую цепь с n вершинами и соединим непересекающимися ребрами некоторые или все несмежные вершины. Назовем эти ребра прилегающими ребрами. Покажем, что число т ребер в такой цепи не более, чем 2п – 3.
Если n = 2, то т = 2 · 2 – 3 = 1. Предположим, что n = k – 1 и т ≤ 2(k – 1) – 3. Покажем, что, добавляя еще одну вершину k (при этом число ребер может увеличиться только на два), число ребер не превзойдет 2k – 3.
тk= тk-1 + 2 ≤ 2(k – 1) – 3 + 2 = 2k – 2 – 3 + 2 = 2k – 3.
Поэтому по индукции заключаем, что это неравенство выполняется для любых значений k и, в частности, для k = n т. е.
т ≤ 2k – 3, (*)
при этом равенство возможно, если построено максимальное число прилегающих ребер. Все вышеизложенное справедливо и для простых циклов с внешними или внутренними прилегающими ребрами. Прилегающие ребра располагаются с одной стороны для цепи, а для цикла вне или внутри него.
Можно убедиться в том, что все вершины любой цепи, и любого цикла с прилегающими ребрами раскрашиваются не более, чем тремя цветами. Действительно, пусть дана цепь или цикл с k вершинами — v1, v2, ..., vk.
Раскрасим вершину v1 в цвет α, вершину v2 — в цвет β, вершину v3 — в цвет γ, если (v1,_v3) прилегающее ребро.
Следующую вершину v4 можно раскрасить в цвет α, если вершины v1 и v4 несмежны, если же вершины v1 и v4 смежны — то в цвет β.
Вершину 5 можно раскрасить в цвет α, если нет прилегающего ребра (v1,_v5) или в цвет β, если (v1,_v5) прилегающее ребро и т. д.
Таким образом для очередной раскрашиваемой вершины всегда найдется один из трех цветов такой вершины, которая «прикрыта» одним из прилегающих ребер, концы которых несмежны раскрашиваемой вершины. Любые две смежные вершины в плоском графе соединяются любой непрерывной жордановой линией, и потому все ребра в плоском графе пересекаются только в вершинах графа.
Циклы с вершинами внутри.
Рассмотрим произвольный конечный цикл и точку внутри него, соединенную ребрами со всеми вершинами цикла. Такой граф может быть раскрашен не более, чем тремя цветами, если окружающий внутреннюю точку цикл является многоугольником, не обязательно выпуклым, с четным числом вершин, а ребра, соединяющие внутреннюю точку с вершинами, являются какими угодно непрерывными жордановыми линиями. В этом случае одной краской раскрашивается внутренняя вершина, а двумя — вершины многоугольника. Аналогично рассуждая, для раскраски произвольного многоугольника с нечетным числом вершин и внутренней точкой, соединённой ребрами со всеми вершинами, требуется уже четыре краски.
- Курсовая работа
- 1 Понятие графов
- 2 Общие понятия теории графов. Понятия раскраски графов
- 2.1 Общие понятия теории графов
- 2.2 Понятие раскраски графов
- 2.3 Матрица смежности
- 2.4 Матрица инцидентности
- 3 Методы раскраски графов
- 3.1 Теорема об оптимальной раскраске
- 3.2 Теорема о четырех красках
- 3.3 Раскраска плоских графов в соответствии с теоремой о четырех красках
- 3.4 Сведение задачи о раскраске к задаче о наименьшем покрытии
- 3.5 Алгоритм, использующий метод Магу – Вейссмана
- 3.6 Алгоритм неявного перебора
- 3.7 Алгоритм прямого неявного перебора
- 4 Практичческое применение расскраски графов
- 4.1 Составление расписаний
- 4.2 Распределение регистров в микропроцессорах
- 4.3 Распределение частот
- 4.4 Использование водяных знаков
- 4.5 Прочие применения