Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

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

В теме рассматриваются только обыкновенные графы.

§1. Хроматическое число

§2. Оценки хроматического числа

§3 Проблема четырех красок

§4. Раскраска пятью красками

Параграф посвящен доказательству утверждения о том, что любой плоский граф можно раскрасить пятью красками (теорема 5.5). Предварительно установим следующий результат.


Теорема 5.4. В любом плоском графе найдется вершина, имеющая степень не выше пяти.


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

Пусть G – связный плоский граф. Тогда для G справедливо равенство


n-m+r=2


(теорема Эйлера о многогранниках). Напомним, что r – число граней графа G, т.е. число максимальных связных областей, на которые граф разбивает плоскость. Всякая грань ограничивается, по крайней мере, тремя ребрами, а каждое ребро может входить в границу не более чем двух граней. Следовательно,


3r/2£m или r£2m/3.

Отсюда следует, что

n-m+r £ n-m+2/3m = n-1/3m и n-1/3m³2


Сумма степеней всех вершин равна удвоенному числу ребер, поэтому


m=1/2r(v).

Подставим это значение m в неравенство n-1/3m³2, получим, что


n-1/6r(v)³2, или


6 - r(v)³12.


Последнее неравенство может быть записано следующим образом


(6-r(v))³12.

Если степень любой вершины v графа G больше пяти, то в левой части последнего неравенства стоит сумма неположительных чисел. Эта сумма не может быть большей или равной 12. Следовательно, найдется хотя бы одна вершина, степень которой не превосходит пяти.

Теорема доказана.


Теорема 5.5. Каждый плоский граф можно правильно раскрасить пятью красками.


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

По теореме 5.4 граф G содержит вершину, степень которой не превосходит пяти. Обозначим эту вершину через v0. Граф G’=G–v0 является плоским и содержит k вершин. Используя предположение индукции, правильно раскрасим граф G’ пятью красками. Если для раскраски вершин, смежных с v0, использовано четыре краски или меньше, то найдется краска для вершины v0 и в результате получится правильная раскраска графа G.

Предположим, что для раскраски вершин, смежных с v0, использованы все пять красок. Отсюда следует, что r(v0)=5. Занумеруем вершины, смежные v0, по часовой стрелке (см. рис. 5.10).


Рис.5.10.


Пусть вершина vi раскрашена i–краской. Обозначим через Н13 подграф графа G, порожденный вершинами, раскрашенными первой и третьей красками. Рассмотрим два случая.


Первый случай: вершины v1 и v3 лежат в разных компонентах связности графа Н13. Обозначим через K компоненту связности графа Н13, содержащую вершину v3. Вершины, принадлежащие K, перекрасим следующим образом: вершины, раскрашенные первой краской, покрасим третьей, а вершины, раскрашенные третьей краской, покрасим первой. Мы получим правильную раскраску графа G’.

Действительно, если мы возьмем смежные вершины x и y графа G’ и обе эти вершины не лежат в K, то они будут раскрашены разными красками, поскольку не перекрашивались (см. рис. 5.10). Если одна из вершин, скажем х, принадлежит K, а вторая вершина y не принадлежит K, то х раскрашена (и до и после перекрашивания) первой или третьей красками, а вершина y не может быть раскрашена этими красками, поскольку K – компонента связности графа Н13 и yÏK. Если же обе вершины х и y принадлежат K, то они до перекрашивания были раскрашены разными красками, а после перекрашивания их краски поменяются, но останутся различными. После перекраски вершина v3 будет раскрашена в первый цвет. Раскрасим вершину v0 в третий цвет и мы получим правильную раскраску всего графа G.


Второй случай: вершины v1 и v3 лежат в одной компоненте связности графа Н13. Тогда они соединены простой цепью, проходящей через вершины графа Н13. Отметим, что если к этой цепи добавить ребро, соединяющее вершины v0 и v1, и ребро, соединяющее вершины v0 и v3, то получится цикл графа G, который ограничивает часть плоскости, содержащей вершину v2 (см. рис. 5.10). Рассмотрим теперь подграф Н24 графа G’, содержащий вершины, раскрашенные второй и четвертой красками. Вершины v2 и v4 не могут быть соединены цепью в этом графе.

Действительно, в противном случае ребра этой цепи пересекали бы ребра (v1,v3)–цепи графа Н13, расширенной ребрами (v0,v1) и (v0,v3), что невозможно, поскольку G – плоский граф, или новая цепь проходила бы по вершинам старой цепи, что тоже невозможно, так как эти вершины раскрашены разными красками (см. рис. 5.11).


Рис.5.11

Обозначим буквой L компоненту связности графа Н24, содержащую вершину v4. Вершины этой компоненты перекрасим: вторую краску заменим на четвертую, а четвертую – на вторую. В результате, как и в первом случае, получим правильную окраску графа G’. Вершина v4 будет раскрашена второй краской, как и вершина v2 (так как v2ÏL). Четвертая краска освободится для вершины v0.

Теорема доказана.

Задачи

Ответы, указания и решения

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru