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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
3-розфарбовування графа Петерсена

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

Визначення[ред.ред. код]

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

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

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

Пов'язані визначення[ред.ред. код]

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

Реброве розфарбування[ред.ред. код]

реброве розфарбування кубічного графа

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

Хроматичний багаточлен[ред.ред. код]

Цей граф може бути 3-кольоровим 12-ма способами.

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

Розглянемо граф, зображений на малюнку. Використовуючи лише три кольори, існує 12 варіантів розфарбовання. З двома кольорами йго взагалі не можна розфарбовати. З чотирма, він може бути розфарбований у 24 + 4*12 = 72 спосіб: використання всіх чотирьох дає 4! = 24 вірних розфарбовань; і для кожного вибори 3-х з 4-ч доступних кольорів маємо 12 варіантів. Таким чином, таблиця кількості вірних розфарбовань виглядає таким чином:

Доступно кольорів 1 2 3 4
Кількість розфарбовань 0 0 12 72

Хроматичний багаточлен - функція P(Gt) яка рахує кількістьt-розфарбовань G. Для графа з малюнка P(Gt) = t(t − 1)2(t − 2), і насправді P(G, 4) = 72.

Хроматичні багаточлени деяких графів
Трикутник 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-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)


Узагальнення[ред.ред. код]

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

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

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.