Визначення хроматичного числа. Хроматичний поліном

Задача про чотири фарби. Правильне розфарбування графа

Тема 2.4. РОЗФАРБУВАННЯ ГРАФА

Додання однієї хорди до остова графа вказує на незалежний цикл.

Теорема 2.3.4. Граф G є зв’язним тоді і тільки тоді, коли він має остов.

Означення 2.3.8. Лісом з k дерев називають граф, що не має циклів і складається з k компонент.

Теорема 2.3.5. Кожне дерево з n вершинами має n -1 ребро.

Теорема 2.3.6. Ліс з дерев, який містить n вершин, має n - k ребер.

ЛІТЕРАТУРА

1. Алферова З.В. Математическое обеспечение экономических расчетов с помощью графов. – М.: Статистика, 1994. – С.18-23.

2. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974. – С. 30-34,136-143.

3. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. – С.43-59.

4. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печорін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – С.230-235, 273-275.

5. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984. – С.39-40, 105-108.

В основу теорії розфарбування графа лягла задача “Про чотири фарби”. Полягала вона в тому, щоб на політико-адміністративній карті розфарбувати країни так, щоб ніякі дві країни, що мають спільний кордон, не були розфарбовані однаковою фарбою, чотирма фарбами. При цьому спільний кордон, який зображений точкою, я не лінією, не враховувався.

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

Це одна з перших задач теорії графів. Гіпотезу про чотири фарби вперше було висунуто в 1840р. На лекціях Мьобіуса. Нею займався Де Морган (1850р.). У 1878р. Келей не зміг отримати строгого доведення цієї гіпотези. У 1890р. Хівуд довів суперечність і показав, що необхідно п’ять кольорів.

Надалі вважатимемо, що граф G – плоский, не має кратних ребер і неорієнтований.

Крім розфарбування граней графа існує його реберне і вершинне розфарбування.

Означення 2.4.1. Реберним k-розфарбуванням графа називають присвоєння ребрам графа k різних фарб.

Означення 2.5.2. Граф G (Х, Г) називають правильно реберно розфарбованим k фарбами, якщо кожне його ребро розфарбоване однією з k фарб і з того що два ребра u_i і u_j є суміжними слідує, що вони розфарбовані різними фарбами.

Означення 2.5.3. Хроматичний індекс або реберне хроматичне число Х ’(G) графа G – це мінімальне число k, для якого граф має правильне реберне k -розфарбування.

Теорема Візинга. Якщо G (Х, Г) – простий граф, то або Х ’(G)=D, або Х ’(G)=D+1, де D - максимальний степінь вершини у графі G (для дводольного графа Х’(G)=D).

Наприклад, у заданого графа максимальний степінь вершини 6, тобто 6 ребер є суміжними і повинні бути розфарбовані різними фарбами, тому менше, ніж 6 фарб неможливо використати для правильного розфарбування. На рисунку наведено один із способів правильного реберного розфарбування заданого графа.

Означення 2.5.4. Граф G (Х, Г) називають правильно вершинно розфарбованим l фарбами, якщо кожна його вершина розфарбована однією з l фарб і якщо з (х _i, x _j)Î Г слідує, що х _i і x _j розфарбовані різними фарбами.

Означення 2.5.5. Граф G (Х, Г) називають р-хроматичним, якщо існує правильне розфарбування вершин графа G р фарбами. Мінімальне з таких р називають хроматичним числом графа.

Для обчислення хроматичного числа вводять функцію p (G, l).

Означення 2.5.6. Для заданого графа G і натурального числа l через p (G, l) (хроматичний поліном) позначається кількість всіх правильних розфарбувань графа G з допомогою l фарб.

Слід відмітити що наступна формула справедлива для достатньо малих S ₀.

Теорема 2.5.2. Справедлива формула:

, де

S – кількість ребер суграфів графа G;

С – кількість компонент зв’язаності суграфів графа G;

- кількість суграфів графа G.

Якщо суграфів немає, то .

Ця формула дає змогу прослідкувати такі властивості функції p (G, l):

1) p (G, l) це многочлен степеня S ₀ з коефіцієнтом 1 при старшому члені;

2) p (G, l) ділиться на l.

Нариклад, за теоремою 2.5.2 обчислимо p (G, l) для трикутного графа G.

Розпишемо кожен з випадків, нагадавши, що сам граф є своїм суграфом (випадок г):

а) S=0, C=3,

б) S=1, C=2,

в) S=2, C=1,

г) S=3, C=1, .

Тоді .

Простим перебором чисел від 1, знаходимо хроматичне число. Підставивши у цю формулу або , отримаємо, що p (G,1)= p (G,2)=0, тобто кількість правильних розфарбувань графа однією чи двома фарбами дорівнює нулеві – однією або двома фарбами граф розфарбовувати не можна. Хроматичне число цього графа є 3, оскільки його підставляння у формулу дало позитивний результат:

p(G,3)=1×2×3=3!=6

Властивості хроматичних поліномів:

1) p (G, l)= p (G ₁, l)× p (G ₂, l) (якщо G (p, l) складається з двох незв’язних частин, то розфарбування можна вибирати незалежно для двох незв’язних графів).

2) p (G, l)= p (G ₁, l)× p (G ₂, l) (якщо граф G отримано з двох графів склеюванням в одній точці х ₀).

3) p (G, l)= p (G ₁, l)× p (G ₂, l) (якщо граф G отримано з двох незв’язних графів склеюванням по ребру, зовнішньому для обох графів).

4) p (G, l)= p (G ₁, l)- p (G ’, l) (якщо граф G отримано з G ₁ доданням ребра без зміни вершин, G ’ – граф, отриманий з G ₁ склеюванням вершин, які інцидентні доданому ребру).

Граф G є однохроматичним тоді і тільки тоді, коли він не містить ні одного ребра; двохроматичним – тоді і тільки тоді, коли він не містить циклів непарної довжини.

Для розфарбування граней, утворених перетином прямих ліній на площині достатньо двох кольорів.

Необхідною і достатньою умовою розфарбування двома кольорами є те, що кожна вершина повинна мати парний степінь ³ 2.

ЛІТЕРАТУРА

1. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974. – С. 3-16, 136-143.

2. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. – С.7-14.

3. Дискретная математика для програмистов / Ф.А.Новиков. – СПб.: Питер, 2002. – С.189-198.

4. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печорін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – С.224-229, 236-243.

5. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984. – С.11-23, 78-84.

РОЗДІЛ 3. ЗАГАЛЬНА АЛГЕБРА

Дата добавления: 2014-10-17