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

Цей розділ **самодостатній**: у ньому зібрано всю теорію, потрібну для теми — графи
та їхні матриці суміжності, розфарбування вершин і ребер — разом із прийомами, якими
розв'язують задачі з [3task.md](3task.md). Ширший виклад — у
[Лекції 7](../../Lectures/ODM-L07.md).

## 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](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](3task.md). Приклад показує лише **техніку**, а не розв'язок вашого
> варіанта.

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

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

| | $P$ | $Q$ | $R$ | $S$ |
|:--:|:--:|:--:|:--:|:--:|
| $P$ | 0 | 2 | 1 | 0 |
| $Q$ | 2 | 1 | 0 | 1 |
| $R$ | 1 | 0 | 0 | 1 |
| $S$ | 0 | 1 | 1 | 0 |

Матриця **симетрична**, отже граф **неорієнтований**. На діагоналі
$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, петля при Q, ребра PR, QS, RS](img/p4_demo_undirected.png)

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

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

| | $P$ | $Q$ | $R$ |
|:--:|:--:|:--:|:--:|
| $P$ | 1 | 2 | 0 |
| $Q$ | 0 | 0 | 1 |
| $R$ | 1 | 1 | 0 |

Матриця **несиметрична** ($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.$$

![Орієнтований граф за матрицею: петля при P, подвійна дуга P→Q, дуги Q→R, R→P, R→Q](img/p4_demo_directed.png)

### (в) Хроматичне число $\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** за Візінгом.

![Розфарбування графа-«метелика»: ліворуч вершини у 3 кольори (χ=3), праворуч ребра у 4 кольори (χ'=4)](img/p4_demo_coloring.png)

## 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$ — так і зазначте.