Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

1-й сем-ДМ-слайды-ДГТУ / Графы, л.5-7 / раскрашивание графов

.doc
Скачиваний:
60
Добавлен:
19.05.2015
Размер:
79.87 Кб
Скачать

Раскрашивание графов.

При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро инцидентно вершинам разного цвета?

Х

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

Если G-K-раскрашиваемый, но не является (K-1)-раскрашиваемым, то назовем его K- хроматическим, а число K- хроматическим числом графа G и обозначим X(G).

Пример:

4- хроматический

К≥4- раскрашиваемый граф

Граф может иметь кратные ребра.

Ясно, что X( Kn )= n.

С другой стороны X(G)=1, если G-вполне несвязный граф. X(G)=2, если G- двудольный граф, отличный от вполне несвязного графа. Любое дерево, имеющее не менее двух вершин, является 2-хроматическим.

Теорема 1.Если наибольшая из степеней вершин графа G равна P, то граф (Р+1)- раскрашиваем.

Доказательство. По индукции. Пусть G-граф с n-вершинами. Если из него удалить производную вершину V вместе с инцидентными ей ребрами, то в оставшемся графе будет n-1 вершин, причем, степени вершин не превосходят Р. По предположению индукции этот граф (Р+1)- раскрашиваем => получается (Р+1)- раскраска для G, если окрасить вершину U цветом, отличным от тех, которыми окрашены смежные с ней вершины (а их не более чем Р).

Теорема 2. (Брукс) Пусть наибольшая из степеней вершин графа G равна Р. Тогда G-P-раскрашиваемый, за исключением тех случаев, когда

1) G содержит в качестве компоненты граф Kp+1

2) Р=2 и угол нечетной длины является компонентой G.

Теорема 3. Любой граф 5-раскрашиваем.

Гипотеза четырех красок. Всякий граф 4-раскрашиваем.

Известно, что а) всякий граф, имеющий менее 52 вершин, 4-раскрашиваем. б) любой, не содержащий треугольников граф, 3-раскрашиваем. (теорема Грега)

Усиление теоремы 1 =>

Теорема 4. Пусть G- простой связный граф, не являющийся полным ,если наибольшая из степеней его вершин равна Р(Р≥3), то Р- раскрашиваем.

Реберная раскраска.

Граф G- реберно K- раскрашиваем, если его ребра можно раскрасить K красками таким образом, что никакие два смежных ребра не окажутся одного цвета. Если граф G-реберно K-раскрашиваем, но не является реберно (K-1)-раскрашиваемым, то K-хроматическое число (хроматический класс или хроматический индекс) графа G.

X(G)=K.

X(G)=4

Ясно, что если наибольшая из степеней вершин графа G равна Р, то Xi(G)≥P

Теорема 5. (Визинг).Пусть в графе G, не имеющем петель, наибольшая из степеней вершин равна Р, тогда ρ≤Xl(b)≤Р=1.

Пример: известно, что Хl(Cn)=2, если n-четно, Хl(Cn)=3, если нечетно.

Теорема 6. Xl(Km,n)=P=max (m,n).

Хроматический класс любого двудольного графа равен Р.