Розв'язник вправ по дискретній математиці/Графи/Хроматичне число

Матеріал з Вікіпідручника

Розв'язник вправ по дискретній математиці. Графи. Хроматичне число[ред.]

Розфарбовування графа Петерсена у 3 кольори.

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

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

Приклади на хроматичне число[ред.]

Обчисліть хроматичне число для графу:

  • N1 (складається з однієї вершини).
Розвязок.
Граф N - це граф без ребер. Тому для графу, що складається тільки з однієї вершини, хроматичне число 1.
Відповідь - 1.
  • Nk (складається з k незв'язних вершини).
Розвязок.
Ми маємо граф, який складається тільки з k-вершин без ребер. Тому, хроматичним числом для графа Nk - є 1.
Відповідь - 1.
  • K2 (дві вершини з'єднані ребром).
Розвязок.
Уявимо, що маємо граф G у вигляді відрізку. Тому, розфарбовуємо вершини у 2 кольори. І маємо, що це і є мінімальною кількістю кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори.
Відповідь - 2.
  • K3 (повний граф).
Розвязок.
Граф K3 - це трикутник.
Припустимо, що вершину А ми розфарбували у червоний колір, з неї виходить ще 2 ребра, які потім з'єднанні ще 1 ребром, тому, щоб кінцівки цих ребер були різних кольорів, розфарбуємо іх у зелений та синій кольори. Таким чином, для графу K3 хроматичним числом - є 3.
Відповідь - 3.
  • W4 (колесо).
Розвязок.
Граф W4 - це трикутник з вершиною в центрі. Таким чином, якщо починати розфарбовувати саме з центральної вершини, виходить, що вона з'єднана з усіма іншими. Тому хроматичним числом для графу W4 - є 4.
Відповідь - 4.
  • S4 (зірка).
Розвязок.
Граф S4 - це граф W4, але без ободка. Тому, розмірковуючи аналогічно до W4, спочатку розфарбуємо центр у чевроний, а потім усі інші вершини у синій, бо вони не з'єднані між собою. Таким чином, хроматичним числом для графу S4 - є 2.
Відповідь - 2.
  • C4 (цикл).
Розвязок.
Граф C4 - це квадрат. Тому, задля знаходження хроматичного числа для цього графу, розфарбуємо 2 вершини, які з'єднані умовною діагоналлю у синій колір, а інші у червоний.
Відповідь - 2.

Хроматичний поліном[ред.]

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

Хроматичний поліном[ред.]

Приклади на хроматичний поліном[ред.]

Обчисліть хроматичний многочлен для графу:

  • N1 (складається з однієї вершини).
Розвязок.
Граф N1 - це 1 вершина без ребер. Тому, поліномом для цього графу - є t.
Відповідь - t.
  • Nk (складається з k незв'язних вершини).
Розвязок.
Граф N1 - це k-вершина без ребер. Тому, поліномом для цього графу - є t.
Відповідь - t.
  • K2 (дві вершини з'єднані ребром).
Розвязок.
Граф K2 - це відрізок. Тоді одну кінцівку можна розфарбувати у t кольорів, а іншу вже у t-1. Таким чином, многочленом для K2 - t*(t-1).
Відповідь - t*(t-1).
  • K3 (повний граф).
Розвязок.
Розмірковуючи аналогічно, як для K2, получаємо поліном t*(t-1)*(t-2).
Відповідь - t*(t-1)*(t-2).
  • W4 (колесо).
Розвязок.
Розглянемо граф W4. Центральну вершину ми можемо розфарбувати у t-кольорів, а інші у (t-1), (t-2) i (t-3), бо вони з'єднанні між собою. Таким чином, многочлен для графу W4 - t*(t-1)*(t-2)*(t-3).
Відповідь - t*(t-1)*(t-2)*(t-3).
  • S4 (зірка).
Розвязок.
Якщо розфарбовувати граф S4 з центру, то цю вершину ми можемо побачити в t кольорах, а інші у (t-1). Таким чином, поліном для S4 - t*(t-1)^3.
Відповідь - t*(t-1)^3.
  • L4 (ломана).
Розвязок.
Припустимо, що маємо декілька з'єднаних між собою відрізків. Таким чином, якщо поліном від K2 - t*(t-1), то L4 - це 2 з'єднаних відрізка і поліном виглядає так
t^2*(t-1)^2.
Відповідь - t^2*(t-1)^2.
  • C4 (цикл).
Розвязок.
Граф C4 = L4 - K3.
C4 = t^2*(t-1)^2 - t*(t-1)*(t-2) = t*(t^3-3*t^2+2*t - 2)
Відповідь - t*(t^3-3*t^2+2*t - 2).
Таким чином, за рекурентим відношенням, маємо:
  • Kn (цикл).
Розвязок.
Якщо провести аналогію з K2, та K3, то маємо, що Kn має поліном вигляду
t*(t-1)*(t-2)*...*(t-(n-1))
Відповідь - t*(t-1)*(t-2)*...*(t-(n-1)).

Рекурентні формули для хроматичного поліному[ред.]

Приклад. Знайти хроматичний поліном графа, показаного на мал. 12.8.

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

мал. 12.9

1. Хроматична редукція по порожніх|пустих| графах. Видаляючи ребра і ототожнюючи відповідні вершини (стягуючи ребра), зведемо початковий граф до порожного графу. Спочатку розкладемо граф на два, прибравши, а потім стягнемо ребро 1-3. Тепер ми маємо (мал.12.9) : трикутник з точкою - трикутник. Так, як точка з трикутником є незв'язним графом, то ми маємо: t*(t*(t-1)*(t-2)) - (t*(t-1)*(t-2).

Відповідь - t*(t*(t-1)*(t-2)) - (t*(t-1)*(t-2).

Розкладання (12.9) називається хроматичною редукцією графа по порожніх графах.

2. Хроматична редукція по повних|цілковитих| графах. Додавши до зображеного на мал. 12.8 графа ребро 1–4, одержимо граф із великим числом ребер. Потім в початковому графі ототожнимо вершини 1 і 4. В результаті отримаємо двa графa. (мал 12.10)

мал. 12.10

Ототожнення вершин приводить до зменшення порядку і інколи розміру графа. Другий граф – це повний граф, його перетворювати більше не потрібно. До першого графа додамо ребро 1–2 і ототожнимо вершини 1 і 2: мал. 12.11

мал. 12.11

Хроматичний поліном прийме вигляд: K4+2K3 = t*(t-1)*(t-2)*(t-3) + 2*t*(t-1)*(t-2)

Відповідь - t*(t-1)*(t-2)*(t-3) + 2*t*(t-1)*(t-2).

Обчислення хроматичного поліному для циклу, колеса і дерева[ред.]

  • хроматичний многочлен для Cn (цикл).
Розвязок.
Нехай Cn - цикл довжини n. Тоді хроматичний многочлен циклу P(Cn,x)=(x−1)n+(−1)n(x−1)
Доведемо по індукції за кількістю вершин. База індукції
розглянемо випадок n = 3:
P(C3,x)=x(x−1)(x−2)=(x3−3x2+3x−1)−(x−1)=(x−1)3+(−1)3(x−1), що задовольняє формулюванні теореми. Індукційний перехід
нехай P(Ck,x)=(x−1)k+(−1)k(x−1). Розглянемо випадок n=k+1.
По теоремі про рекуррентну формулу для хроматичних многочленів
P(Ck+1,x)=P(Ck+1∖e,x)−P(Ck+1/e,x) (де e - будь ребро Ck+1/e). Зауважимо, що граф Ck+1/e ізоморфний Ck, а граф Ck+1∖e  є простим ланцюгом. Тоді  P(C(k+1,x)=P(Tk+1,x)−P(Ck,x)=x(x−1)k−(x−1)k−(−1)k(x−1) = (x−1)k+1+(−1)k+1(x−1).
Відповідь: (x−1)k+1+(−1)k+1(x−1).
  • хроматичний многочлен для Wn (колесо).
Розвязок.
Нехай  Wn — колесо с nл,  вершинами. Вибравши і зафіксувавши один з x кольорів на вершині, пов'язаної з усіма іншими, маємо P(Cn−1,x−1) варіантів розмальовки графа. Тоді хроматичний многочлен колеса PWn(x)=x⋅PCn−1(x−1)=x((x−2)(n−1)−(−1)n(x−2)).
Відповідь: x((x−2)(n−1)−(−1)n(x−2)).
  • хроматичний многочлен для дерева.

Граф  з n  вершинами є деревом тоді, коли P(G,x)=x(x−1)n−1

Розвязок.
Доведення:
Спочатку покажемо, що хроматичний многочлен будь-якого дерева T з n вершинами є x (x-1) n-1. Доказ за індукцією по числу n. Для n = 1 і n = 2 результат очевидний. Припустимо, що P (T ', x) = x (x-1)n-2 для будь-якого дерева T' з кількістю вершин рівним n-1. Нехай uv - ребро дерева T, таке що v є висячої вершиною. Хроматичний многочлен дерева T без ребра uv дорівнює P (T / uv, x) = x (x-1)n-2 за нашим припущенням. Вершину v можна розфарбувати x-1 способом, так як її колір повинен тільки відрізнятися від кольору вершини u. Разом
P (T, x) = (x-1) P (T / uv, x) = x (x-1)n-1.
⇐ Назад, нехай G - граф, у якого P (G, x) = x (x-1) n-1. Тоді вірні два наступних твердження
  1. Граф G зв'язний, тому що якщо було б дві компоненти зв'язності (або більше), то P (G, x) ділився б на 2 без залишку.
  2. У графі G кількість ребер одно n-1, так як по одній з теорем про коефіцієнти хроматичного многочлена, кількість ребер в графі відповідає коефіцієнту при xn-1, взятому зі знаком мінус. У нашому випадку, цей коефіцієнт зручно шукати, використовуючи біном Ньютона: P(G,x)=x(x−1)n−1=x(xn−1−(n−1,1)xn−2+(n−1,2)xn−3−...+(−1)n−1)=xn−(n−1)xn−1+...+(−1)n−1x Из этих двух утверждений (связность и n-1 ребро) следует, что граф  є деревом.

Коефіціенти хроматичного поліному[ред.]

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

Теорема 2. Абсолютна величина другого коефіцієнта хроматичного полінома рівна числу ребер графа.

Теорема 3. Найменше число i, для якого відмінний від нуля коефіцієнт при в хроматичному поліномі графа G, рівне числу компонент зв'язності графа G.