Раскрашивание графа. Хроматическое число графа. Теор. о 5-и красках.

Опр. 1: Раскрашиванием графа назыв. такое приписывание весов (нат. чисел) его вершинам, что никакие две смежные вершины не имеют один цвет. Минимально возможное число красок в раскраске назыв. хроматическим числом графа χ(G). {χ(G)≤p(G).}

Теор. 1 (о 5-и красках): Всякий плоский граф можно раскрасить не более чем 5-ю красками.

Док-во:

ММИ по числу вершин графа.

1) Базис. Пусть число вершин графа не превосходит 5. Тогда каждую вершину можно покрасить в свой цвет и утвержд. выполнится.

2) Индукт. допущ. Пусть утверждение верно для плоского графа с числом вершин р.

3) Добавим к графу ещё одну вершину. Будет р+1 вершина. По сл. №3 из теор. Эйлера в данном графе сущ. вершина, степень кот. не превосходит 5. Пусть это v₀. Удалим v₀ и инцидентные ей рёбра из графа с р+1 вершиной. Получим граф с р вершинами. По индуктивному допущению этот граф можно раскрасить 5-ю красками. Раскрасим его. Вернём v₀ и все инцидентные ей рёбра. Покажем, что v₀ всегда можно покрасить в один из 5-и использованных цветов.

Возможно 3 случая:

1) d(v₀)<5. В этом случае всегда имеется по кр. мере 1 цвет.

2) d(v₀)=5 и среди смежных вершин есть хотя бы две одного цвета. Тогда есть по кр. мере 1 цвет.

3) d(v₀)=5 и все смежные вершины имеют уникальные цвета.

Рассм. плоскую укладку графа. Вершины занумерованы в определённом порядке. Рассм. мн-во V₁₃dV; это мн-во всех вершин, кот. отвечают следующим условиям: 1) эти вершины имеют цвета 1 или 3; 2) эти вершины достижимы из v₁ путями, проходящими только через вершины цветов 1 и 3.

Возможны 2 подслучая:

1`) вершина v₃ не входит во мн-во V₁₃. В этом случае перекрасим вершины, входящие во мн-во V₁₃: 1 в 3, 3 в 1. Получим для v₀ свободный первый член.

2`) вершина v₃ не входит во мн-во V₁₃. Рассм. мн-во V₂₄ (строится как V₁₃).

Возможны 2 подслучая:

1``) v₄ не входит во мн-во V₂₄. Далее как в 1`);

2``) v₄ входит во мн-во V₂₄. Значит сущ. простая цепь, соединяющая v₂ и v₄ и проходящая через вершины с цветами 2 и 4.

Данный случай получен из предположения, что v₃0V₁₃, а значит, сущ. простая цепь, соединяющая v₁ и v₃ и проходящая только через вершины с цветами 1 и 3. Получаем, что две простые цепи пересекаются. Эти цепи не могут иметь общую вершину, значит, должны пересекаться рёбра, что противоречит тому, что граф плоский, значит, случай 2``) невозможен. ВСЁ.

Дата добавления: 2015-07-20