2. Методичні вказівки #

Цей розділ самодостатній: у ньому зібрано всю теорію, потрібну для теми — графи та їхні матриці суміжності, розфарбування вершин і ребер — разом із прийомами, якими розв’язують задачі з 3task.md. Ширший виклад — у Лекції 7.

2.1 Граф та його елементи #

Граф $G = (V, E)$ — це множина вершин $V$ і множина ребер $E$, де кожне ребро сполучає дві вершини. Види ребер, які трапляються в цій роботі:

• неорієнтоване ребро $\{u, v\}$ не має напряму; орієнтоване ребро (дуга) $(u, v)$ спрямоване від $u$ до $v$;
• петля — ребро, що з’єднує вершину саму з собою;
• кратні (паралельні) ребра сполучають ту саму пару вершин. Граф, що допускає петлі та кратні ребра, називають мультиграфом; граф без них — простим.

Дві вершини, з’єднані ребром, називають суміжними; вершину й ребро, що її містить, — інцидентними.

2.2 Степені вершин #

Степінь $\deg(v)$ — це кількість «кінців ребер» при вершині $v$; петля дає до степеня $2$. У неорієнтованому графі за лемою про рукостискання

$$\sum_{v \in V} \deg(v) = 2\,|E|,$$

бо кожне ребро додає по одиниці до степенів двох своїх кінців.

В орграфі розрізняють напівстепінь виходу $\deg^{+}(v)$ (кількість дуг, що виходять з $v$) і напівстепінь заходу $\deg^{-}(v)$ (кількість дуг, що входять у $v$); кожна петля додає по одиниці до обох. Завжди $\sum_v \deg^{+}(v) = \sum_v \deg^{-}(v) = |E|$.

Найбільший степінь у графі позначають $\Delta(G)$. Множину попарно суміжних вершин називають клікою, а розмір найбільшої кліки — $\omega(G)$. Трикутник — це кліка розміру $3$.

2.3 Матриця суміжності #

Занумеруймо вершини $v_1, \dots, v_n$. Матриця суміжності $A = [a_{ij}]$ — це таблиця $n \times n$, у якій

$$a_{ij} = \bigl(\text{кількість ребер/дуг між } v_i \text{ та } v_j\bigr).$$

За матрицею одразу видно чотири речі:

• Орієнтований чи неорієнтований? Для неорієнтованого графа матриця симетрична ($a_{ij} = a_{ji}$): те, що над головною діагоналлю, дзеркально повторюється під нею. Якщо $A$ несиметрична, граф орієнтований.
• Петлі сидять на діагоналі: $a_{ii}$ — кількість петель при $v_i$ (тут кожну петлю рахуємо на діагоналі один раз — див. main.md).
• Кратні ребра проявляються як елементи, більші за $1$: $a_{ij} = 3$ означає три ребра між $v_i$ та $v_j$.
• Степені. Для неорієнтованого графа сума $i$-го рядка дорівнює $\deg(v_i)$, але діагональний елемент треба додати ще раз (петлю в сумі рядка враховано один раз, а в степені вона має рахуватися двічі): $\deg(v_i) = \bigl(\text{сума рядка } i\bigr) + a_{ii}$. Для орграфа сума рядка дає $\deg^{+}(v_i)$, а сума стовпця — $\deg^{-}(v_i)$.

2.4 Побудова графа за матрицею #

1. Розмістіть $n$ вершин зручно (по колу чи по кутах квадрата — так ребра менше перетинаються).
2. Визначте тип графа за симетрією $A$: симетрична — неорієнтований, ні — орієнтований.
3. Позадіагональні елементи. Для кожного $a_{ij}$ (у неорієнтованому графі досить брати $i < j$) проведіть $a_{ij}$ ребер між $v_i$ та $v_j$ — одну лінію або кілька паралельних, якщо елемент більший за $1$. Для орграфа проведіть стрілку $v_i \to v_j$ у кількості $a_{ij}$ та окрему стрілку $v_j \to v_i$ у кількості $a_{ji}$.
4. Діагональні елементи. Домалюйте $a_{ii}$ петель при $v_i$.
5. Перевірте, зчитавши степені назад із рядків (і стовпців — для орграфа).

2.5 Розфарбування вершин і хроматичне число $\chi$ #

Правильне розфарбування вершин приписує кожній вершині колір так, щоб суміжні вершини мали різні кольори. Хроматичне число $\chi(G)$ — найменша кількість кольорів, якої вистачає для правильного розфарбування. (Петля робить правильне розфарбування неможливим, а кратні ребра на $\chi$ не впливають — тому $\chi$ залежить лише від простого графа, що лежить в основі.)

Значення $\chi$ затиснуте між двома оцінками:

• Нижня оцінка — кліка. У кліці з $k$ вершин усі $k$ вершин попарно суміжні, тож потребують $k$ різних кольорів: $\ \chi(G) \ge \omega(G)$. Зокрема, один трикутник уже змушує $\chi \ge 3$.
• Верхня оцінка — жадібний алгоритм. Фарбуючи вершини по черзі, кожна має не більше за $\Delta$ уже пофарбованих сусідів, тож серед $\Delta + 1$ кольорів завжди знайдеться вільний: $\ \chi(G) \le \Delta(G) + 1$. (На практиці фарбують «найважчі» вершини — з найбільшим степенем — першими.)

Опорні значення: $\chi = 1$ тоді й лише тоді, коли ребер немає; $\chi(K_n) = n$ для повного графа; і $\chi(G) \le 2$ тоді й лише тоді, коли $G$ двочастковий, тобто не має циклів непарної довжини. Звідси парний цикл має $\chi = 2$, а непарний — $\chi = 3$.

Як довести, що $\chi(G) = k$. Треба обґрунтувати дві речі: (1) навести правильне розфарбування у $k$ кольорів (отже, $\chi \le k$); (2) вказати причину, чому меншого не досягти, — зазвичай кліку розміру $k$ (отже, $\chi \ge k$). Коли обидві оцінки збігаються, значення знайдено.

2.6 Розфарбування ребер і хроматичний клас (індекс) $\chi'$ #

Правильне розфарбування ребер фарбує ребра так, щоб ребра зі спільною вершиною мали різні кольори; найменша кількість кольорів — це хроматичний клас (його ще називають хроматичним індексом) $\chi'(G)$. Рівносильно: кожен клас одного кольору є паруванням (набором ребер без спільних кінців).

• Нижня оцінка — найзавантаженіша вершина. $\Delta$ ребер при вершині максимального степеня попарно сходяться в ній, тож усі потребують різних кольорів: $\ \chi'(G) \ge \Delta(G)$.
• Теорема Візінга. Для простого графа $\ \chi'(G) \in \{\Delta,\ \Delta+1\}$. Графи з нижнім значенням $\chi' = \Delta$ належать до класу I, а ті, що потребують $\Delta + 1$, — до класу II. (Для мультиграфа верхня межа може зрости: $\chi' \le \Delta + \mu$, де $\mu$ — найбільша кратність ребра.)
• Лічильна оцінка. Клас одного кольору — це парування, у ньому не більше за $\lfloor n/2 \rfloor$ ребер; тому $\ \chi'(G) \ge \lceil |E| / \lfloor n/2 \rfloor \rceil$. Саме вона піднімає щільний малий мультиграф вище за $\Delta$.

Як довести, що $\chi'(G) = k$. Так само двома кроками: навести правильне розфарбування ребер у $k$ кольорів і вказати причину, чому меншого не буває (оцінка $\Delta$ або лічильна оцінка).

2.7 Демонстраційний приклад #

Увага. Дані нижче — демонстраційні й не збігаються з жодним варіантом із 3task.md. Приклад показує лише техніку, а не розв’язок вашого варіанта.

(а) Неорієнтований граф за матрицею #

Розгляньмо симетричну матрицю (рядки й стовпці — $P, Q, R, S$):

Матриця симетрична, отже граф неорієнтований. На діагоналі $a_{QQ} = 1$ — це петля при $Q$. Елемент $a_{PQ} = 2$ дає два паралельні ребра $P \!=\! Q$; поодинокі $1$ дають ребра $PR$, $QS$, $RS$. Степені (сума рядка плюс діагональний елемент ще раз):

$$\deg P = 3 + 0 = 3,\quad \deg Q = 4 + 1 = 5,\quad \deg R = 2 + 0 = 2,\quad \deg S = 2 + 0 = 2.$$

(б) Орієнтований граф за матрицею #

Тепер несиметрична матриця (рядки — початок дуги, стовпці — кінець; вершини $P, Q, R$):

Матриця несиметрична ($a_{PQ} = 2 \ne a_{QP} = 0$), отже граф орієнтований. $a_{PP} = 1$ — петля при $P$. Дуги: $P \!\to\! P$ (петля), $P \!\to\! Q$ (подвійна), $Q \!\to\! R$, $R \!\to\! P$, $R \!\to\! Q$. Напівстепені виходу (суми рядків) і заходу (суми стовпців):

$$\deg^{+}\!: P{=}3,\ Q{=}1,\ R{=}2; \qquad \deg^{-}\!: P{=}2,\ Q{=}3,\ R{=}1.$$

(в) Хроматичне число $\chi$ та хроматичний клас $\chi'$ #

Візьмімо простий граф $G$ на вершинах $a, b, c, d, e$ з ребрами $ab, ac, bc, cd, ce, de$ — два трикутники $abc$ і $cde$ зі спільною вершиною $c$ («метелик»). Максимальний степінь $\Delta = 4$ (у вершині $c$).

Хроматичне число. Трикутник $abc$ — це кліка розміру $3$, тому $\chi \ge 3$. З іншого боку, розфарбування у три кольори існує: $a, d \to$ колір 1; $b, e \to$ колір 2; $c \to$ колір 3 (кожен клас — незалежна множина, суміжні вершини відрізняються). Отже, $\chi \le 3$, і разом $\boxed{\chi(G) = 3}$.

Хроматичний клас. Чотири ребра при вершині $c$ попарно сходяться в ній, тож $\chi' \ge \Delta = 4$. Правильне розфарбування ребер у чотири кольори існує: $ac \to 1$, $bc \to 2$, $cd \to 3$, $ce \to 4$, а тоді $ab \to 3$ і $de \to 1$ (перевірте: у кожній вершині всі інцидентні ребра різного кольору). Отже, $\chi' \le 4$, і разом $\boxed{\chi'(G) = 4}$; оскільки $\chi' = \Delta$, граф належить до класу I за Візінгом.

2.8 Робочий чек-лист #

• Матриця $\to$ граф: перевірте симетрію (орієнтований чи ні); розмістіть вершини; проведіть позадіагональні ребра (паралельні лінії / стрілки для елементів $> 1$); домалюйте діагональні петлі; звірте степені із сумами рядків (і стовпців).
• Хроматичне число $\chi$: знайдіть найбільшу кліку для нижньої оцінки; пофарбуйте жадібно (найважчі вершини першими) для верхньої; коли оцінки збіглися — значення знайдено. Трикутник уже дає $\chi \ge 3$; відсутність непарного циклу — $\chi \le 2$.
• Хроматичний клас $\chi'$: почніть із $\Delta$; спробуйте побудувати розфарбування ребер у $\Delta$ кольорів (клас I). Якщо це неможливо — за Візінгом зростає до $\Delta + 1$ (клас II) або, для щільного мультиграфа, до лічильної межі $\lceil |E| / \lfloor n/2 \rfloor \rceil$ — так і зазначте.

Practical/Practical4/2method.md · 15.4 KB · updated 2026-08-04 14:35