Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Хроматичної число



План:


Введення

3-розмальовка графа Петерсена

Хроматичної число графа G - мінімальне число кольорів, в які можна розфарбувати вершини графа G так, щоб кінці будь-якого ребра мали різні кольори. Позначається χ (G).


1. Визначення

Хроматичної число графа - мінімальне число k , Таке що безліч V вершин графа можна розбити на k непересічних класів C_1, C_2, \ ldots, C_k :

V = \ bigcup_i ^ {} C_i; \ C_i \ cap C_j = \ varnothing,

таких, що вершини в кожному класі незалежні, тобто будь ребро графа не з'єднує вершини одного і того ж класу.


2. Пов'язані визначення

  • K-розфарбовуваним граф - граф, хроматичної число якого не перевершує K . Тобто його вершини можна розфарбувати K різними кольорами так, що у будь-якого ребра кінці будуть різного кольору.
  • K-хроматичний граф - граф, хроматичної число якого дорівнює K . Тобто вершини графа можна розфарбувати K квітами так, що у будь-якого ребра кінці будуть різного кольору, але так розфарбувати K - 1 квітами - вже не можна.

3. Реброва розмальовка

Реброва розмальовка кубічного графа

Хроматичний клас графа G - мінімальне число кольорів, в які можна розфарбувати ребра графа G так, щоб суміжні ребра мали різні кольори. Позначається χ '(G). Проблема реберної розмальовки довільного плоского кубічного графа без мостів трьома кольорами еквівалентна знаменитої Проблемі чотирьох фарб. Реброва розмальовка визначає 1-факторизацию графа.


4. Хроматичний многочлен

Якщо розглянути кількість різних розмальовок поміченого графа як функцію від доступного числа квітів t, то виявляється, що ця функція завжди буде поліномом від t. Цей факт був виявлений Біркгофом і Льюїсом [1] при спробі довести гіпотезу чотирьох фарб.

4.1. Хроматичні многочлени деяких графів

Трикутник K 3 t (t - 1) (t - 2)
Повний граф K n t (t - 1) (t - 2 )...( t - (n - 1))
Дерево з n вершинами t (t - 1) n - 1
Цикл C n (T - 1) n + (- 1) n (t - 1)
Граф Петерсена t (t - 1) (t - 2) (t 7 - 12 t 6 + 67 t 5 - 230 t 4 + 529 t 3 - 814 t 2 + 775 t - 352)

4.2. Знаходження хроматичного многочлена довільного графа

Для графа-вершини хроматичний многочлен дорівнює t

| V (G) | = 1 \ Rightarrow P (G, t) = t.

Хроматичний многочлен графа дорівнює добутку хроматичних многочленів його компонент

G_1 \ cap G_2 = \ emptyset \ Rightarrow P ((G_1 \ cup G_2), t) = P (G_1, t) P (G_2, t).

Також існує рекурентне співвідношення

P (G, t) = P (G - (u, v), t) - P (G / (u, v), t),

де u і v - Суміжні вершини, G - (u, v) - Граф, що виходить з графа G шляхом видалення ребра (U, v), а G / (u, v) - Граф, що виходить з графа G шляхом стягування ребра (U, v) в точку.
Можна використовувати еквівалентну формулу

P (G, t) = P (G + (u, v), t) + P (G \ Uparrow (u, v), t),

де u і v - Несуміжні вершини, а G + (u, v) - Граф, що виходить з графа G шляхом додавання ребра (U, v).


4.3. Властивості хроматичного многочлена

Для всіх цілих позитивних t

P (G, t) \ ge 0.

Хроматичної число χ (G) - Найменше ціле позитивне t , Для якого

P (G, t)> 0.

5. Узагальнення

Також хроматичної число можна розглядати для інших об'єктів, наприклад, для метричних просторів. Так, хроматичним числом площині називається мінімальне число χ таке, що існує розфарбування всіх точок площини в один з χ квітів і при цьому жодні дві точки одного кольору не знаходяться на відстані 1 один від одного (площину не містить монохроматичних відрізків довжини 1). Аналогічно для будь-якої розмірності простору. Елементарно доводиться, що для площині 4 \ leqslant \ chi \ leqslant 7 , Однак більше до цих пір невідомо - ця проблема носить назву Хадвігера-Нельсона (англ.).


6. Значення для теорії графів

Безліч глибоких завдань теорії графів легко формулюються в термінах розмальовки. Найзнаменитіша з таких завдань, проблема чотирьох фарб, в даний час вирішена, однак з'являються нові, наприклад, узагальнення проблеми чотирьох фарб, гіпотеза Хадвігера.

Примітки

  1. Birkhoff, GD and Lewis, DC "Chromatic Polynomials." Trans. Amer. Math. Soc. 60, 355-451, 1946.

Література

  • О. Оре. Теорія графів. Переклад з англійської І. Н. Врублевської, під редакцією М. Н. Воробйова. М.: Наука, 1986.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
90 (число)
3 (число)
e (число)
-1 (Число)
30 (число)
12 (число)
14 (число)
18 (число)
24 (число)
© Усі права захищені
написати до нас
Рейтинг@Mail.ru