# Лекція 7. Основи теорії графів

## Огляд

**Граф** — це математична модель сукупності об'єктів разом із **попарними
зв'язками** між ними. Об'єкти малюють крапками, зв'язки — лініями, і саме тому графи
належать до найнаочніших і водночас найуніверсальніших структур дискретної
математики. Комп'ютерні мережі, схеми доріг, структура посилань між веб-сторінками,
молекули, діаграми залежностей між задачами, соціальні мережі, а у нашому фаху —
схема перетікань між сторінками макета, граф суміжності кольорів у растрі чи
з'єднань на друкованій платі — усе це природно описується графами.

Тема спирається на дві попередні. Граф ми означимо як **пару множин** $G=(V,E)$ —
отже, уся мова [Лекції 1](ODM-L01.md) (множини, підмножини, потужність) працює тут
безпосередньо. А ребро $\{u,v\}$ — це, по суті, **симетричне відношення** на множині
вершин, тож властивості відношень із [Лекції 2](ODM-L02.md) (рефлексивність,
симетричність, транзитивність, класи еквівалентності) знадобляться, коли ми
означуватимемо зв'язність. Конкретні **алгоритми** на графах — пошук найкоротшого
шляху (Дейкстра), мінімальне остовне дерево (Прим, Крускал), транспортні мережі —
винесено в наступну [Лекцію 8](ODM-L08.md); тут ми будуємо лише *мову* та *теорію*.

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

> **Про строгість.** Майже кожне твердження нижче — лема про рукостискання, наслідок
> про парність, формула Ейлера, непланарність $K_5$ і $K_{3,3}$, формула
> $|E|=|V|-1$ для дерев — оформлене як **теорема** й **доведене**, а не просто
> проголошене. Читайте доведення активно: означення — лише абетка, а справжній зміст
> курсу — навчитися *доводити* твердження про дискретні структури.

Наскрізь у лекції ми користуємося одним **робочим прикладом**:

$$
G = (V, E), \qquad V = \{a,b,c,d,e\}, \qquad E = \{\, ab,\ ac,\ ad,\ bc,\ ce,\ de \,\}.
$$

![Робочий граф G = (V, E): вершини a, b, c, d, e і шість ребер](img/l07_graph.png)

---

## 7.1 Граф: означення та перше знайомство

> **Історична довідка (Кенігсберзькі мости).** Теорія графів має точну дату
> народження. 1736 року Леонард Ейлер розв'язав головоломку про пруське місто
> Кенігсберг (нині Калінінград), розділене річкою Прегель на береги й два острови,
> з'єднані **сімома мостами**: чи можна прогулятися так, щоб перейти кожен міст
> **рівно один раз** і повернутися додому? Ейлерова ідея — відкинути всю геометрію:
> кожна ділянка суходолу стає **вершиною**, кожен міст — **ребром**. Питання
> перетворюється на суто комбінаторне. Систематичну відповідь (умову існування
> такого обходу) ми одержимо в [Лекції 8](ODM-L08.md); тут Кенігсберг лише пояснює,
> *чому* степені вершин та їхня парність варто вивчати так уважно.

> **Означення (граф).** **Граф** $G=(V,E)$ складається зі скінченної непорожньої
> множини $V$, елементи якої називають **вершинами** (*вузлами*), і множини $E$,
> елементи якої називають **ребрами**. Кожне ребро сполучає **невпорядковану** пару
> вершин; ребро між $u$ і $v$ позначають $uv$ або $\{u,v\}$. Оскільки пара
> невпорядкована, $uv$ і $vu$ — те саме ребро.

Число вершин $|V|$ називають **порядком** графа, число ребер $|E|$ — його
**розміром**. Увесь граф міститься в парі $(V,E)$; *малюнок* — лише зручність для
людини. Той самий граф має нескінченно багато різних малюнків (це уточнить
§7.10, ізоморфізм): важливо *чи* сполучені дві вершини, а не наскільки довгою чи
вигнутою намальовано лінію (доки ми не додамо ваги в §7.7).

> **Означення (простий граф, мультиграф).** Граф **простий**, якщо він не має ні
> петель, ні паралельних ребер (обидва поняття означено в §7.2); тоді $E$ — множина
> **двоелементних підмножин** $V$. Граф, що допускає паралельні ребра (тобто $E$ —
> *мультимножина*), називають **мультиграфом**. Якщо не вказано інше, під «графом»
> розуміємо простий граф.

**Приклад 7.1.** У робочому графі $G$ маємо $|V|=5$ і $|E|=6$. Вершини $a$ і $c$
сполучені ребром ($ac\in E$), а вершини $b$ і $d$ — ні ($bd\notin E$). Граф простий:
петель і кратних ребер немає.

---

## 7.2 Суміжність, інцидентність та інші базові поняття

Зафіксуймо граф $G=(V,E)$.

- **Суміжність вершин.** Дві вершини $u,v$ **суміжні** (є **сусідами**), якщо
  $uv\in E$. Множину сусідів вершини $v$ називають її **околом** $N(v)$.
- **Інцидентність.** Вершина $v$ та ребро $e$ **інцидентні**, якщо $v$ — один із двох
  кінців ребра $e$. Два ребра **суміжні**, якщо мають спільний кінець.
- **Петля.** **Петля** — це ребро, що сполучає вершину саму з собою (ребро $vv$). У
  простих графах петель немає.
- **Паралельні (кратні) ребра.** Два або більше ребер, що сполучають *ту саму* пару
  вершин, називають **паралельними (кратними)**. Прості графи їх не мають,
  мультиграфи можуть.
- **Ізольована вершина.** Вершина, з якою не інцидентне жодне ребро (сусідів немає).

![Мультиграф: петля, паралельні (кратні) ребра та ізольована вершина](img/l07_terms.png)

**Приклад 7.2.** На рисунку вгорі вершина $1$ має петлю; вершини $1$ і $2$ сполучені
**двома паралельними ребрами**; вершини $2$ і $3$ суміжні (сполучені одним ребром);
вершина $4$ — **ізольована**. Такий об'єкт уже не простий граф, а мультиграф.

> **Зауваження (як петлі впливатимуть на лічбу).** Петля інцидентна своїй вершині
> *двома* кінцями. Тому в §7.3 вона рахуватиметься у степені **двічі** — це не
> примха, а рівно те, що зберігає істинність леми про рукостискання. У простих
> графах питання не виникає, бо петель немає.

---

## 7.3 Степінь вершини. Лема про рукостискання

Найважливіша локальна характеристика вершини — скільки ребер із неї виходить.

> **Означення (степінь вершини).** **Степінь** $\deg(v)$ вершини $v$ — це кількість
> інцидентних їй ребер, причому петля рахується **двічі**. Вершину степеня $0$
> називають **ізольованою**, а вершину степеня $1$ — **висячою** (листком). У
> простому графі $\deg(v)=|N(v)|$.

Позначають $\Delta(G)=\max_v\deg(v)$ (максимальний степінь) і
$\delta(G)=\min_v\deg(v)$ (мінімальний). Граф **$r$-регулярний**, якщо всі вершини
мають однаковий степінь $r$. Список степенів усіх вершин, зазвичай записаний у
незростаючому порядку, називають **степеневою послідовністю**.

**Приклад 7.3 (степені в $G$).** Порахуймо степені робочого графа:

| вершина | інцидентні ребра | $\deg$ |
|:---:|:---|:---:|
| $a$ | $ab,\ ac,\ ad$ | $3$ |
| $b$ | $ab,\ bc$ | $2$ |
| $c$ | $ac,\ bc,\ ce$ | $3$ |
| $d$ | $ad,\ de$ | $2$ |
| $e$ | $ce,\ de$ | $2$ |

Степенева послідовність — $(3,3,2,2,2)$; її сума дорівнює
$3+3+2+2+2=12=2\cdot 6=2|E|$. Це не випадковість, а вияв фундаментальної теореми.

> **Теорема 7.4 (лема про рукостискання).** У будь-якому графі (простому чи
> мультиграфі)
> $$ \sum_{v\in V}\deg(v)=2\,|E|. $$
>
> *Доведення (подвійна лічба).* Порахуймо **двома способами** множину
> **інцидентностей**
> $$ I=\{\,(v,e): v\in V,\ e\in E,\ v \text{ інцидентна } e\,\}. $$
> *Лічба за вершинами.* Згрупуймо пари $(v,e)$ за першою координатою. Фіксована
> вершина $v$ входить рівно у $\deg(v)$ пар — по одній на кожне інцидентне ребро
> (петля дає дві пари, відповідно до угоди «рахується двічі»). Отже,
> $|I|=\sum_{v\in V}\deg(v)$.
> *Лічба за ребрами.* Згрупуймо пари за другою координатою. Фіксоване ребро $e$ має
> рівно два кінці, тож входить рівно у дві пари. Отже, $|I|=\sum_{e\in E}2=2|E|$.
> Прирівнявши два вирази для однієї величини $|I|$, дістаємо
> $\sum_v\deg(v)=2|E|$. $\blacksquare$

Формулюють це й «за вечіркою»: **сумарна кількість потиснутих рук удвічі більша за
кількість рукостискань**, бо кожне рукостискання задіює дві руки. Найкорисніший
наслідок — твердження про парність.

> **Наслідок 7.5 (про вершини непарного степеня).** У будь-якому графі кількість
> вершин непарного степеня **парна**.
>
> *Доведення.* Розіб'ємо вершини за парністю степеня на
> $V_{\text{н}}=\{v:\deg(v)\text{ непарний}\}$ і
> $V_{\text{п}}=\{v:\deg(v)\text{ парний}\}$. За Теоремою 7.4
> $$ \sum_{v\in V_{\text{н}}}\deg(v)+\sum_{v\in V_{\text{п}}}\deg(v)=2|E|. $$
> Права частина парна; друга сума ліворуч — сума парних чисел, отже парна. Тоді й
> перша сума $\sum_{v\in V_{\text{н}}}\deg(v)$ парна. Але це сума $|V_{\text{н}}|$
> непарних чисел, а за модулем $2$ кожне непарне $\equiv 1$, тож
> $\sum_{v\in V_{\text{н}}}\deg(v)\equiv |V_{\text{н}}|\pmod 2$. Отже,
> $|V_{\text{н}}|$ парне. $\blacksquare$

**Приклад 7.6.** Чи можуть $7$ осіб потиснути руки так, щоб кожна привіталася рівно
з трьома іншими? Ні: це був би граф із $7$ вершинами степеня $3$, тобто $7$ вершин
непарного степеня — непарна кількість, що суперечить Наслідку 7.5. (Рівнозначно:
сума степенів $7\cdot 3=21$ непарна, а мусить дорівнювати $2|E|$.)

Ще один короткий, але корисний факт спирається на **принцип Діріхле**.

> **Твердження 7.7.** У кожному простому графі з $n\ge 2$ вершинами знайдуться дві
> різні вершини однакового степеня.
>
> *Доведення.* У простому графі степінь кожної вершини лежить у множині
> $\{0,1,\dots,n-1\}$ ($n$ можливих значень). Припустимо супротивне: усі $n$ степенів
> різні; тоді кожне значення $0,1,\dots,n-1$ трапляється рівно раз. Зокрема, є
> вершина степеня $0$ (ні з ким не суміжна) і вершина степеня $n-1$ (суміжна з усіма
> $n-1$ іншими, отже й з першою) — суперечність. Тож усі $n$ значень одночасно
> неможливі: різних степенів щонайбільше $n-1$ на $n$ вершин, і за принципом Діріхле
> два степені збігаються. $\blacksquare$

### Особливі сімейства графів

Кілька графів трапляються так часто, що мають власні назви й формули для розміру. Ми
покликатимемося на них у §7.11 (планарність) та §7.12 (розфарбування).

- **Порожній граф $N_n$** — $n$ вершин і **жодного** ребра; кожна вершина ізольована,
  граф $0$-регулярний.
- **Простий ланцюг $P_n$** — $n$ вершин у рядок із ребрами
  $v_1v_2,\dots,v_{n-1}v_n$; має $n-1$ ребро й дві висячі вершини (кінці).
- **Цикл $C_n$** ($n\ge 3$) — $n$ вершин по колу; має $n$ ребер і $2$-регулярний.
- **Повний граф $K_n$** — простий граф, у якому **кожна** пара різних вершин
  сполучена ребром; він $(n-1)$-регулярний.
- **Повний дводольний граф $K_{m,n}$** — вершини поділено на дві частини розмірів
  $m$ і $n$; кожну вершину однієї частини сполучено з кожною вершиною другої, а
  всередині частин ребер немає. Граф, вершини якого так розбиваються, називають
  **дводольним**.

> **Теорема 7.7а (розміри повних графів).**
> $$ |E(K_n)|=\binom{n}{2}=\frac{n(n-1)}{2}, \qquad |E(K_{m,n})|=mn. $$
>
> *Доведення.* У $K_n$ кожна з $n$ вершин має степінь $n-1$, тож за лемою про
> рукостискання $2|E|=\sum_v\deg(v)=n(n-1)$, звідки $|E|=\frac{n(n-1)}{2}$. У
> $K_{m,n}$ кожна з $m$ вершин однієї частини сполучена рівно з $n$ вершинами другої,
> і жодне ребро не лічиться двічі (кожне має рівно один кінець у кожній частині), тож
> $|E|=mn$. $\blacksquare$

**Приклад 7.7б.** $K_3$ (трикутник) має $3$ ребра, $K_4$ — $6$, $K_5$ — $10$,
$K_6$ — $15$. Дводольний $K_{3,3}$ має $3\cdot 3=9$ ребер. Ці значення знадобляться,
коли ми доводитимемо непланарність $K_5$ і $K_{3,3}$ (§7.11).

---

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

Графи зручно малювати, але комп'ютерові потрібне числове подання. Найпоширеніше —
матриця суміжності.

> **Означення (матриця суміжності).** **Матрицею суміжності** графа на вершинах
> $v_1,\dots,v_n$ називають $n\times n$ матрицю $A=[a_{ij}]$, де $a_{ij}$ — кількість
> ребер між $v_i$ і $v_j$. Для простого графа кожен запис — $0$ або $1$.

Ключові властивості для неорієнтованого простого графа: матриця **симетрична**
($a_{ij}=a_{ji}$); **діагональ нульова** (немає петель); а **сума $i$-го рядка
дорівнює $\deg(v_i)$**.

**Приклад 7.8.** Упорядкувавши вершини $a,b,c,d,e$, матриця суміжності робочого графа
$G$ така:

|  $a_{ij}$ | $a$ | $b$ | $c$ | $d$ | $e$ |
|:---:|:---:|:---:|:---:|:---:|:---:|
| $a$ | 0 | 1 | 1 | 1 | 0 |
| $b$ | 1 | 0 | 1 | 0 | 0 |
| $c$ | 1 | 1 | 0 | 0 | 1 |
| $d$ | 1 | 0 | 0 | 0 | 1 |
| $e$ | 0 | 0 | 1 | 1 | 0 |

Вона симетрична, діагональ нульова, а суми рядків $3,2,3,2,2$ відтворюють знайдену
раніше степеневу послідовність.

![Матриця суміжності графа G: симетрична, з нульовою діагоналлю](img/l07_adj.png)

> **Зауваження (степені матриці рахують маршрути).** Найкорисніша алгебраїчна
> властивість матриці суміжності: запис $(i,j)$ у степені $A^{k}$ дорівнює кількості
> **маршрутів** довжини $k$ з $v_i$ у $v_j$ (доводиться індукцією за $k$). Зокрема
> діагональ $A^{2}$ дає степені вершин. Ми користуватимемося цим побіжно; докладніше
> — у контексті алгоритмів [Лекції 8](ODM-L08.md).

---

## 7.5 Орієнтовані графи

Досі ребро було симетричним зв'язком. Часто ж зв'язок **напрямлений**: одностороння
вулиця, гіперпосилання зі сторінки $u$ на сторінку $v$, відношення «передує» між
задачами.

> **Означення (орієнтований граф).** **Орієнтований граф** (**орграф**) $D=(V,A)$
> складається з множини вершин $V$ і множини **дуг** $A$, де кожна дуга — це
> **впорядкована** пара $(u,v)$, намальована стрілкою від **початку** $u$ до
> **кінця** $v$. Тепер $(u,v)$ і $(v,u)$ — *різні* дуги: напрям має значення.

У орграфі степінь розщеплюється на два. **Напівстепінь виходу** $\deg^{+}(v)$ —
кількість дуг із початком у $v$ (стрілки, що виходять); **напівстепінь входу**
$\deg^{-}(v)$ — кількість дуг із кінцем у $v$ (стрілки, що входять).

![Орієнтований граф на тих самих вершинах: ребра стали напрямленими дугами](img/l07_digraph.png)

**Приклад 7.9.** Зорієнтуймо ребра робочого графа так: $a\to b$, $a\to c$, $a\to d$,
$b\to c$, $c\to e$, $d\to e$. Напівстепені виходу й входу зведено в таблицю:

| вершина | $a$ | $b$ | $c$ | $d$ | $e$ |
|:---:|:---:|:---:|:---:|:---:|:---:|
| $\deg^{+}$ | $3$ | $1$ | $1$ | $1$ | $0$ |
| $\deg^{-}$ | $0$ | $1$ | $2$ | $1$ | $2$ |

> **Твердження 7.10 (орієнтована лема про рукостискання).** У будь-якому орграфі
> $D=(V,A)$
> $$ \sum_{v\in V}\deg^{+}(v)=\sum_{v\in V}\deg^{-}(v)=|A|. $$
>
> *Доведення.* Кожна дуга $(u,w)$ має рівно один початок $u$ і рівно один кінець
> $w$. Сума напівстепенів виходу лічить кожну дугу один раз — у її початку; сума
> напівстепенів входу лічить кожну дугу один раз — у її кінці. Обидві суми тому
> дорівнюють числу дуг $|A|$. $\blacksquare$

У прикладі 7.9: $\sum\deg^{+}=3+1+1+1+0=6$ і $\sum\deg^{-}=0+1+2+1+2=6=|A|$.

**Матриця суміжності орграфа.** Означують так само: $a_{ij}=1$, якщо є дуга
$(v_i,v_j)$. Тепер матриця **не обов'язково симетрична**; сума $i$-го рядка дає
$\deg^{+}(v_i)$, а сума $j$-го стовпця — $\deg^{-}(v_j)$.

|  $a_{ij}$ | $a$ | $b$ | $c$ | $d$ | $e$ |
|:---:|:---:|:---:|:---:|:---:|:---:|
| $a$ | 0 | 1 | 1 | 1 | 0 |
| $b$ | 0 | 0 | 1 | 0 | 0 |
| $c$ | 0 | 0 | 0 | 0 | 1 |
| $d$ | 0 | 0 | 0 | 0 | 1 |
| $e$ | 0 | 0 | 0 | 0 | 0 |

![Матриця суміжності орграфа: несиметрична; суми рядків — напівстепені виходу, стовпців — входу](img/l07_adj_dir.png)

Суми рядків $3,1,1,1,0$ — це напівстепені виходу, суми стовпців $0,1,2,1,2$ —
напівстепені входу, як і має бути.

---

## 7.6 Матриця інцидентності

Друге стандартне подання явно фіксує зв'язок «вершина — ребро».

> **Означення (матриця інцидентності).** **Матриця інцидентності** $M=[m_{ij}]$ має
> один рядок на вершину й один стовпець на ребро: $m_{ij}=1$, якщо вершина $v_i$ —
> кінець ребра $e_j$, і $m_{ij}=0$ інакше.

У простому графі **кожен стовпець містить рівно дві одиниці** (ребро має два кінці),
а **сума $i$-го рядка знову дорівнює $\deg(v_i)$**. Петля — виняток: у її стовпці
стоїть одна двійка.

**Приклад 7.11.** Занумеруймо ребра $e_1=ab,\ e_2=ac,\ e_3=ad,\ e_4=bc,\ e_5=ce,\
e_6=de$. Матриця інцидентності графа $G$:

|  $m_{ij}$ | $e_1$ | $e_2$ | $e_3$ | $e_4$ | $e_5$ | $e_6$ |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| $a$ | 1 | 1 | 1 | 0 | 0 | 0 |
| $b$ | 1 | 0 | 0 | 1 | 0 | 0 |
| $c$ | 0 | 1 | 0 | 1 | 1 | 0 |
| $d$ | 0 | 0 | 1 | 0 | 0 | 1 |
| $e$ | 0 | 0 | 0 | 0 | 1 | 1 |

![Матриця інцидентності графа G: у кожному стовпці рівно дві одиниці](img/l07_incidence.png)

Кожен стовпець дає в сумі $2$; додавши всі записи, дістаємо
$2|E|=12=\sum_v\deg(v)$ — та сама подвійна лічба, тепер за стовпцями. Суми рядків
$3,2,3,2,2$ — знову степені.

> **Зауваження (яке подання обрати).** Матриця суміжності компактна ($n\times n$) і
> за $O(1)$ відповідає на питання «чи суміжні $u,v$?»; матриця інцидентності
> ($n\times|E|$) явно зберігає структуру «вершина — ребро» й легко узагальнюється на
> мультиграфи та (із записами $\pm 1$) на орграфи. На практиці великі розріджені
> графи зберігають **списками суміжності** — головним поданням для алгоритмів
> [Лекції 8](ODM-L08.md).

---

## 7.7 Зважені графи

> **Означення (зважений граф).** **Зважений граф** — це граф разом із **ваговою
> функцією** $w\colon E\to\mathbb{R}$, що приписує кожному ребру число $w(e)$ —
> *вартість*, *довжину*, *пропускну здатність* чи *час*. **Вага маршруту** — сума ваг
> його ребер. (Орграфи зважують так само.)

Ваги роблять осмисленими питання на кшталт «найкоротший маршрут» чи «найдешевша
мережа». У комп'ютері ваги зберігають, замінивши одиниці матриці суміжності на
$w(v_iv_j)$, а «немає ребра» позначають нескінченністю $\infty$.

![Зважений граф: кожному ребру приписано число w(e)](img/l07_weighted.png)

**Приклад 7.12.** Нехай на робочому графі ваги (наприклад, довжини кабелю в метрах)
такі: $w(ab)=7,\ w(ac)=4,\ w(ad)=2,\ w(bc)=1,\ w(ce)=5,\ w(de)=3$. Маршрут
$a\to c\to e$ має вагу $4+5=9$, тоді як $a\to b\to c\to e$ — вагу $7+1+5=13$. Отже,
мінімізуємо **вагу**, а не кількість ребер: це розрізняє «найменше переходів»
(незважений випадок) і «найкоротша відстань» (зважений, алгоритм Дейкстри
[Лекції 8](ODM-L08.md)).

---

## 7.8 Маршрути, ланцюги та цикли

Рух графом описують **маршрути**, які далі уточнюють, забороняючи повторення ребер
або вершин.

> **Означення (маршрут).** **Маршрут** (шлях) довжини $k$ — це послідовність
> вершин і ребер, що чергуються,
> $$ v_0,\ e_1,\ v_1,\ e_2,\ v_2,\ \dots,\ e_k,\ v_k, $$
> де кожне ребро $e_i$ сполучає $v_{i-1}$ і $v_i$. Його **довжина** — кількість ребер
> $k$. Маршрут **замкнений**, якщо його кінці збігаються ($v_0=v_k$), і
> **незамкнений** інакше. У простому графі маршрут визначається списком вершин, тож
> його записують $v_0\text{–}v_1\text{–}\cdots\text{–}v_k$.

> **Означення (ланцюг, простий ланцюг, цикл).**
> - **Ланцюг** — маршрут, у якому **всі ребра різні** (вершини можуть повторюватися).
> - **Простий ланцюг** — маршрут, у якому **всі вершини різні** (а отже, і всі ребра).
> - **Цикл** — **замкнений ланцюг**. Якщо при цьому не повторюються й внутрішні
>   вершини, його називають **простим циклом**. Найкоротший простий цикл у простому
>   графі має довжину $3$ (трикутник).

Ієрархія вкладень: кожен простий ланцюг є ланцюгом, а кожен ланцюг — маршрутом;
кожен простий цикл є циклом, а кожен цикл — замкненим маршрутом. Обернені включення
хибні.

![Простий ланцюг a–b–c та цикл a–c–e–d–a, виділені на графі G](img/l07_walk.png)

**Приклад 7.13 (зі слайдів, на графі $G$).**

- $a\text{–}c\text{–}b\text{–}a\text{–}d$ використовує ребра $ac,cb,ba,ad$ — усі
  різні, тож це **ланцюг**; але вершина $a$ повторюється, тому це **не** простий
  ланцюг. Кінці $a$ і $d$ різні — незамкнений, довжина $4$.
- $a\text{–}c\text{–}e\text{–}d\text{–}a$ використовує ребра $ac,ce,ed,da$ — усі різні
  й повертається в $a$, отже **цикл**; внутрішні вершини не повторюються — це
  **простий цикл** довжини $4$.
- $a\text{–}b\text{–}c$ не повторює жодної вершини — **простий ланцюг** (незамкнений,
  довжина $2$).

Наступна теорема — робочий інструмент усіх міркувань про зв'язність: якщо вершини
з'єднано *хоч якимось* маршрутом, то їх з'єднано й простим ланцюгом.

> **Теорема 7.14 (маршрут $\Rightarrow$ простий ланцюг).** Якщо в графі є маршрут із
> $u$ у $v$, то є й простий ланцюг із $u$ у $v$.
>
> *Доведення.* Множина маршрутів із $u$ у $v$ непорожня за умовою, а довжини
> належать $\{0,1,2,\dots\}$, тож за принципом найменшого числа виберемо маршрут
> $W:\ u=w_0,w_1,\dots,w_k=v$ **найменшої** довжини $k$. Стверджуємо, що $W$ не
> повторює вершин (отже, є простим ланцюгом). Припустимо супротивне: $w_i=w_j$ для
> деяких $i<j$. Тоді $W':\ w_0,\dots,w_i,w_{j+1},\dots,w_k$ — теж маршрут із $u$ у
> $v$ (склейка законна, бо $w_i=w_j$ суміжна з $w_{j+1}$), але його довжина
> $k-(j-i)<k$ суперечить мінімальності $W$. Отже, вершини не повторюються.
> $\blacksquare$

---

## 7.9 Зв'язність та компоненти зв'язності

> **Означення (зв'язність).** Граф **зв'язний**, якщо між кожною парою вершин існує
> маршрут (рівнозначно, за Теоремою 7.14, простий ланцюг). Інакше граф
> **незв'язний** і розпадається на максимальні зв'язні частини — **компоненти
> зв'язності**.

Щоб уточнити «частини», згадаймо відношення еквівалентності з [Лекції 2](ODM-L02.md).

> **Твердження 7.15 (компоненти як класи еквівалентності).** Означимо на $V$
> відношення: $u\sim v$, якщо існує маршрут з $u$ у $v$. Тоді $\sim$ — відношення
> еквівалентності, а його класи — це вершинні множини компонент зв'язності.
>
> *Доведення.* Перевіримо три аксіоми. *Рефлексивність:* маршрут довжини $0$ сполучає
> $u$ із собою, тож $u\sim u$. *Симетричність:* обернувши маршрут $u$–$v$, дістаємо
> маршрут $v$–$u$ (ребра неорієнтовані), тож $u\sim v\Rightarrow v\sim u$.
> *Транзитивність:* приєднавши маршрут $v$–$w$ до маршруту $u$–$v$, дістаємо маршрут
> $u$–$w$, тож $u\sim v$ і $v\sim w\Rightarrow u\sim w$. Отже, $\sim$ розбиває $V$ на
> класи; кожен клас зв'язний і максимальний — це й є компонента. $\blacksquare$

Робочий граф $G$ зв'язний (наприклад, $b$ досягає $e$ через $b\text{–}c\text{–}e$).
Якби ми додали ізольовану вершину $f$, граф став би незв'язним із двома компонентами
$\{a,b,c,d,e\}$ і $\{f\}$.

> **Зауваження (мости та орграфи).** Ребро, вилучення якого збільшує кількість
> компонент, називають **мостом**. У $G$ ребро $ad$ **не** міст (є обхідний цикл
> $a\text{–}c\text{–}e\text{–}d\text{–}a$), тоді як у простому ланцюзі кожне ребро —
> міст. Для орграфів розрізняють **сильну** зв'язність (є напрямлений шлях і з $u$ у
> $v$, і з $v$ у $u$) та **слабку** (зв'язний неорієнтований «кістяк»). Граф посилань
> у вебі зазвичай лише слабко зв'язний.

---

## 7.10 Ізоморфізм графів

Два малюнки можуть виглядати геть по-різному й водночас зображати *той самий* граф.
Уточнимо «однакова структура».

> **Означення (ізоморфізм).** Графи $G_1=(V_1,E_1)$ і $G_2=(V_2,E_2)$ **ізоморфні**
> (пишуть $G_1\cong G_2$), якщо існує **бієкція** $f\colon V_1\to V_2$, що зберігає
> суміжність в обидва боки:
> $$ uv\in E_1\iff f(u)f(v)\in E_2\quad\text{для всіх } u,v\in V_1. $$
> Таку $f$ називають **ізоморфізмом**: вона перейменовує вершини $G_1$, перетворюючи
> його на $G_2$ без додавання чи вилучення ребер.

Ізоморфізм — відношення еквівалентності на графах, тож він сортує всі графи на *класи
ізоморфності*: «той самий» цикл $C_5$ означає один такий клас.

**Як довести ізоморфність:** пред'явити явну бієкцію $f$ і перевірити, що кожне ребро
$G_1$ переходить у ребро $G_2$ (за рівних $|V_1|=|V_2|$ і $|E_1|=|E_2|$ цього досить).

**Як довести неізоморфність:** знайти **інваріант** — величину чи властивість, яку
зберігає кожен ізоморфізм, — на якому графи різняться. Досить *одного* відмінного
інваріанта.

> **Твердження 7.16 (степенева послідовність — інваріант).** Якщо
> $f\colon G_1\to G_2$ — ізоморфізм, то $\deg_{G_1}(v)=\deg_{G_2}(f(v))$ для кожної
> вершини $v$; отже, $G_1$ і $G_2$ мають однакову степеневу послідовність.
>
> *Доведення.* Відображення $f$ звужується до бієкції між околами $N(v)$ і $N(f(v))$:
> якщо $u\in N(v)$, то $uv\in E_1$, звідки $f(u)f(v)\in E_2$, тобто $f(u)\in N(f(v))$;
> обернене — так само, бо $f$ бієкція. Отже, $|N(v)|=|N(f(v))|$, тобто
> $\deg(v)=\deg(f(v))$. $\blacksquare$

Інші зручні інваріанти: порядок $|V|$, розмір $|E|$, кількість компонент, довжина
найкоротшого циклу, кількість трикутників, дводольність.

**Приклад 7.17 (ізоморфні — п'ятикутник і п'ятикутна зірка).** Намалюймо $C_5$ раз як
правильний п'ятикутник із ребрами $\{12,23,34,45,51\}$, а раз як п'ятикутну зірку
(пентаграму) з ребрами $\{13,35,52,24,41\}$. Бієкція

| $x$ | $1$ | $2$ | $3$ | $4$ | $5$ |
|:---:|:---:|:---:|:---:|:---:|:---:|
| $f(x)$ | $1$ | $3$ | $5$ | $2$ | $4$ |

переводить кожне ребро п'ятикутника в ребро зірки ($\{1,2\}\!\to\!\{1,3\}$,
$\{2,3\}\!\to\!\{3,5\}$, $\dots$), тож обидва — це $C_5$.

> **Типова помилка (однакова степенева послідовність $\ne$ ізоморфізм).** Інваріанти
> **необхідні, але не достатні**. Розгляньмо два $2$-регулярні графи на $6$ вершинах:
> цикл $C_6$ і незв'язне об'єднання двох трикутників $C_3\cup C_3$. Обидва мають $6$
> вершин, $6$ ребер і степеневу послідовність $(2,2,2,2,2,2)$ — усі «локальні»
> інваріанти збігаються. Проте $C_6$ зв'язний (одна компонента), а $C_3\cup C_3$ —
> ні (дві), тож вони **не** ізоморфні. Тому «однакова степенева послідовність»
> ніколи не *доводить* ізоморфізму.

---

## 7.11 Планарність. Формула Ейлера. Теорема Понтрягіна–Куратовського

> **Означення (планарний / плоский граф).** Граф **планарний**, якщо його можна
> намалювати на площині так, щоб **жодні два ребра не перетиналися** (ребра
> сходяться лише у спільних кінцях). Таке зображення без перетинів називають
> **плоским графом**. Плоский граф ділить площину на **грані** (максимальні зв'язні
> області), зокрема одну необмежену — *зовнішню*.

> **Теорема 7.18 (формула Ейлера).** Для будь-якого **зв'язного** плоского графа з
> $V$ вершинами, $E$ ребрами та $F$ гранями
> $$ V-E+F=2. $$
>
> *Доведення (індукція за $E$, коротко).* **База** $E=0$: зв'язний граф без ребер —
> це одна вершина, $V=1$, єдина грань $F=1$, і $1-0+1=2$. **Крок.** Нехай $E\ge 1$.
> Якщо граф має цикл, вилучимо одне ребро циклу: дві сусідні грані зливаються в одну,
> тож $F$ і $E$ зменшуються на $1$, а $V$ і зв'язність не змінюються. Якщо ж циклів
> немає (граф — дерево), у ньому є висяча вершина; вилучимо її разом з інцидентним
> ребром: $V$ і $E$ зменшуються на $1$, а $F$ не змінюється (це ребро-міст межує з
> однією гранню з обох боків). В обох випадках величина $V-E+F$ не змінюється, тож за
> припущенням індукції дорівнює $2$. $\blacksquare$

**Приклад 7.19.** Граф $K_4$ планарний: намалювавши його без перетинів (трикутник із
центральною вершиною, сполученою з усіма трьома), маємо $V=4$, $E=6$ і $F=4$ (три
внутрішні трикутні області та зовнішня), і справді $4-6+4=2$.

Справжня сила формули Ейлера — у **межах на кількість ребер**, які вона нав'язує
планарним графам і які дають швидкий *тест непланарності*.

> **Наслідок 7.20 (реброва межа).** У простому зв'язному планарному графі з $V\ge 3$
> $$ E\le 3V-6. $$
>
> *Доведення.* Візьмімо плоске зображення з $F$ гранями. У простому графі з $V\ge 3$
> кожна грань обмежена щонайменше трьома ребрами (грань степеня $1$ вимагала б петлі,
> степеня $2$ — кратних ребер). Сумуючи степені всіх граней, лічимо кожне ребро двічі
> (воно межує з двома гранями), тож $\sum_F\deg(F)=2E$. Оскільки кожен із $F$
> доданків $\ge 3$, маємо $3F\le 2E$, тобто $F\le \tfrac{2E}{3}$. Підставимо
> $F=E-V+2$ з формули Ейлера: $E-V+2\le\tfrac{2E}{3}$, звідки $E\le 3V-6$.
> $\blacksquare$

> **Наслідок 7.21 ($K_5$ непланарний).** Повний граф $K_5$ простий і зв'язний, має
> $V=5$ і $E=\binom{5}{2}=10$. Якби він був планарним, Наслідок 7.20 давав би
> $10\le 3\cdot 5-6=9$ — хибно. Отже, $K_5$ непланарний. $\blacksquare$

Межа $E\le 3V-6$ не розв'язує випадку $K_{3,3}$ ($V=6$, $E=9$, $3V-6=12\ge 9$).
Потрібна гостріша межа, що враховує відсутність трикутників.

> **Наслідок 7.22 (межа для графів без трикутників, $K_{3,3}$ непланарний).** Якщо
> простий зв'язний планарний граф із $V\ge 3$ **не має трикутників**, то кожна грань
> обмежена $\ge 4$ ребрами, звідки $4F\le 2E$ і $E\le 2V-4$. Граф $K_{3,3}$
> дводольний, тож без трикутників; при $V=6$, $E=9$ маємо $9\le 2\cdot 6-4=8$ —
> хибно. Отже, $K_{3,3}$ непланарний. $\blacksquare$

![K₅ і K₃,₃ — два заборонені графи теореми Понтрягіна–Куратовського, з неминучими перетинами ребер](img/l07_forbidden.png)

Ці два графи — це відомі задачі: $K_{3,3}$ — «три колодязі» (з'єднати три будинки з
газом, водою та електрикою без перетину труб — неможливо), а $K_5$ — «п'ять взаємно
сполучених точок». Куратовський (і незалежно Понтрягін) довели, що вони —
*єдині* істотні перешкоди планарності.

> **Теорема 7.23 (Понтрягіна–Куратовського).** Граф планарний **тоді й лише тоді**,
> коли він не містить підграфа, який є **підрозбиттям** $K_5$ або $K_{3,3}$.

Тут **підрозбиття** графа одержують, багаторазово замінюючи ребро на простий ланцюг
через нові вершини степеня $2$ (тобто «розставляючи зайві точки» вздовж ребра).
Підрозбиття не змінює можливості намалювати граф без перетинів, тож прихований $K_5$
чи $K_{3,3}$ — навіть «розтягнутий» додатковими вершинами — унеможливлює планарність,
а його відсутність її гарантує.

> **Застосування (розведення без перетинів).** Планарність — не лише розвага. Плоскі
> графи розпізнають і малюють за лінійний час; вони прямо виникають у трасуванні
> друкованих плат і НВІС-кристалів (провідники одного шару не мають перетинатися) та
> у схемах-макетах, де лінії зв'язку бажано провести без перехрещень.

---

## 7.12 Розфарбування графів

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

Застосування: складання розкладів (кольори — часові слоти, ребра — конфлікти, тож
правильне розфарбування — розклад без накладок), призначення частот, розподіл
регістрів у компіляторі.

**Межі.** Якщо граф містить **кліку** з $k$ вершин (копію $K_k$ — $k$ попарно
суміжних вершин), то їм потрібно $k$ різних кольорів, тож $\chi(G)\ge\omega(G)$, де
$\omega(G)$ — найбільший розмір кліки. З іншого боку, завжди $\chi(G)\le\Delta(G)+1$
(розфарбовуючи вершини по черзі, для кожної маємо не більш ніж $\Delta$ уже
розфарбованих сусідів, тож один із $\Delta+1$ кольорів вільний).

**Базові значення.** $\chi(K_n)=n$; для парного циклу $\chi(C_{2k})=2$, для непарного
$\chi(C_{2k+1})=3$. Загалом $\chi(G)\le 2$ **тоді й лише тоді, коли** граф
**дводольний**, тобто не має циклів непарної довжини.

![Правильне розфарбування графа G у три кольори: χ(G) = 3](img/l07_coloring.png)

**Приклад 7.24 (розфарбування $G$).** Робочий граф містить трикутник
$a\text{–}b\text{–}c$ — кліку розміру $3$, тож $\chi(G)\ge 3$. Трьох кольорів досить:
$a=1,\ b=2,\ c=3$, далі $d=2$ (єдиний розфарбований сусід $a=1$) і $e=1$ (сусіди
$c=3$ і $d=2$). Кожне ребро тепер сполучає вершини різних кольорів, отже,
$\chi(G)=3$.

Кольорувати можна не лише вершини, а й ребра.

> **Означення (реберне розфарбування, хроматичний клас).** **Правильне реберне
> розфарбування** приписує кожному ребру колір так, щоб **ребра зі спільною вершиною
> мали різні кольори**. Найменшу кількість кольорів називають **хроматичним класом**
> (**хроматичним індексом**) $\chi'(G)$.

Оскільки $\Delta(G)$ ребер, інцидентних вершині максимального степеня, попарно
ділять цю вершину, усі вони мусять мати різні кольори, тож $\chi'(G)\ge\Delta(G)$.
Ба більше, за **теоремою Візинга** для простого графа завжди
$\chi'(G)\in\{\Delta(G),\ \Delta(G)+1\}$.

> **Зауваження (хроматичне число проти хроматичного класу).** Це різні задачі, і їхні
> значення можуть не збігатися. Класичний приклад — **граф Петерсена** ($10$ вершин,
> $3$-регулярний): у нього $\chi=3$, але $\chi'=4$ (він досягає верхньої межі Візинга
> $\Delta+1$). Саме таку пару «хроматичне число $3$, хроматичний клас $4$» наведено
> й на слайдах.

> **Історична довідка (задача чотирьох фарб).** Кожен *планарний* граф
> $4$-розфарбовний — славнозвісна **теорема про чотири фарби**: будь-яку політичну
> карту можна розфарбувати чотирма кольорами так, щоб сусідні країни різнилися
> (граф суміжності областей карти планарний). Гіпотезу висловлено 1852 року, а
> доведено Аппелем і Гакеном 1976-го — це була перша велика теорема, доведена зі
> суттєвою допомогою комп'ютера.

---

## 7.13 Дерева й ліс

Найважливіша спеціальна структура — **дерево**: зв'язний граф без циклів. Дерева
організують файлові системи (коренева тека, теки, файли й *єдиний шлях* до кожного
файла), дерева розбору виразів, структури пошуку та префіксні коди.

> **Означення (дерево, ліс).** **Дерево** — це зв'язний неорієнтований граф без
> циклів (зв'язний ациклічний граф). **Ліс** — неорієнтований граф без циклів (не
> обов'язково зв'язний); кожна його компонента є деревом.

![Дерево на семи вершинах: зв'язне, без циклів, з |E| = |V| − 1](img/l07_tree.png)

Ключова кількісна властивість дерева — жорсткий зв'язок між числами вершин і ребер.
Спершу — допоміжний факт про висячі вершини.

> **Лема 7.25 (про дві висячі вершини).** Кожне дерево з $n\ge 2$ вершинами має
> щонайменше дві висячі вершини (листки).
>
> *Доведення.* Серед усіх простих ланцюгів дерева виберемо **найдовший**
> $P\colon v_0,v_1,\dots,v_k$ (він існує, бо граф скінченний); оскільки дерево має
> ребро, $k\ge 1$ і $v_0\ne v_k$. Покажемо, що $v_0$ — листок. Якби $v_0$ мала сусіда
> $w\ne v_1$, то: або $w\notin P$ — і тоді $w,v_0,\dots,v_k$ довший ланцюг, що
> суперечить максимальності; або $w=v_i$ для деякого $i\ge 2$ — і тоді
> $v_0,\dots,v_i,v_0$ цикл, що суперечить ациклічності. Отже, $\deg(v_0)=1$.
> Так само $v_k$ — листок. $\blacksquare$

> **Теорема 7.26 (кількість ребер дерева).** Дерево з $n$ вершинами має рівно $n-1$
> ребро: $|E|=|V|-1$.
>
> *Доведення (індукція за $n$).* **База** $n=1$: єдина вершина, $0=1-1$ ребро.
> **Крок.** Нехай $n\ge 2$ і твердження справджується для всіх дерев із меншою
> кількістю вершин. За Лемою 7.25 у дереві $T$ є листок $v$ з єдиним сусідом $u$.
> Вилучимо $v$ разом із ребром $uv$; одержаний граф $T'$ лишається зв'язним (через
> вершину степеня $1$ жоден простий ланцюг між іншими вершинами не проходив) і
> ациклічним, тобто є деревом на $n-1$ вершинах. За припущенням індукції $T'$ має
> $(n-1)-1=n-2$ ребра, а повернувши $v$ та ребро $uv$, додаємо рівно одне ребро — тож
> $T$ має $n-1$ ребро. $\blacksquare$

**Приклад 7.27.** Дерево на рисунку має $|V|=7$ вершин і $|E|=6=|V|-1$ ребер;
листки — $d,e,f,g$ (степінь $1$), внутрішні вершини — $a,b,c$. Степені такі:
$\deg a=2,\ \deg b=3,\ \deg c=3$, а $\deg d=\deg e=\deg f=\deg g=1$; їхня сума
$2+3+3+1+1+1+1=12=2\cdot 6=2|E|$, як і має бути за лемою про рукостискання.

Для лісу формула узагальнюється, і саме кількість компонент «псує» рівність.

> **Твердження 7.28 (ребра лісу).** Ліс із $n$ вершинами та $c$ компонентами має
> рівно $n-c$ ребер.
>
> *Доведення.* Нехай компоненти — дерева на $n_1,\dots,n_c$ вершинах, $\sum_i n_i=n$.
> За Теоремою 7.26 компонента $i$ має $n_i-1$ ребро, тож усього
> $\sum_{i=1}^{c}(n_i-1)=n-c$. $\blacksquare$

Дерево — окремий випадок $c=1$, що повертає $|E|=n-1$. Обернувши рівність,
$c=n-|E|$: **у лісі кількість компонент дорівнює вершини мінус ребра** — крихітний
лічильний рушій, на якому тримається структура «система неперетинних множин» в
алгоритмі Крускала.

> **Зауваження (остовне дерево).** Для зв'язного графа **остовне дерево** — це
> підграф, який є деревом і містить *усі* вершини (отже, $|V|-1$ ребро). Кожен
> зв'язний граф має остовне дерево, а для зваженого графа шукають **мінімальне
> остовне дерево** — найдешевший «кістяк» мережі. Алгоритми Прима й Крускала для його
> побудови — тема [Лекції 8](ODM-L08.md).

---

## 7.14 Ейлерові та гамільтонові цикли. Задача комівояжера

Маючи мову маршрутів і циклів (§7.8), поставимо два класичні питання про **повний
обхід** графа. Перше стосується **ребер**: чи можна пройти графом, скориставшись
кожним ребром рівно один раз? Друге — **вершин**: чи можна обійти граф, відвідавши
кожну вершину рівно один раз? Питання звучать симетрично, та, як побачимо, мають
зовсім різну складність.

### Ейлерові ланцюги та цикли

Перше питання — це рівно головоломка про кенігсберзькі мости з §7.1.

> **Означення (ейлерів ланцюг, ейлерів цикл).** **Ейлерів ланцюг** — це ланцюг, що
> містить **кожне ребро** графа (а отже, рівно один раз, бо в ланцюзі ребра не
> повторюються). Замкнений ейлерів ланцюг, який повертається у початкову вершину,
> називають **ейлеровим циклом**, а граф, що його має, — **ейлеровим**.

![Мультиграф кенігсберзьких мостів; біля вершин — їхні степені, усі непарні](img/l07_konigsberg.png)

Ейлер помітив, що можливість обходу залежить лише від **парності степенів**. Уявімо,
що ланцюг проходить графом; щоразу, входячи у проміжну вершину одним ребром, ми
мусимо вийти з неї іншим, ще не використаним ребром. Тому ребра при кожній проміжній
вершині розбиваються на пари «увійшов–вийшов», а її степінь має бути **парним**. Це
спостереження і є ядром критерію.

> **Теорема 7.29 (критерій Ейлера).** Нехай $G$ — зв'язний граф без ізольованих
> вершин. Тоді:
> - $G$ має **ейлерів цикл** тоді й лише тоді, коли **всі** вершини мають парний
>   степінь;
> - $G$ має **ейлерів ланцюг**, який не є циклом, тоді й лише тоді, коли рівно
>   **дві** вершини мають непарний степінь (саме вони й будуть кінцями ланцюга).
>
> *Доведення (необхідність).* Нехай у $G$ є ейлерів цикл $C$. Пройдімо ним і для
> кожної вершини $v$ полічимо інцидентні їй ребра, якими скористалися. Кожен прохід
> «крізь» $v$ задіює рівно **два** такі ребра — одне на вхід, одне на вихід, — і всі
> вони різні, бо ланцюг ребер не повторює. Оскільки цикл замкнений, і в початковій
> вершині є вихід та відповідний йому вхід. Тому ребра при $v$ повністю розбиваються
> на пари, а отже, $\deg(v)$ парний для кожної вершини. Для ейлерового **ланцюга**,
> що не є циклом, той самий підрахунок дає пари скрізь, **окрім** двох кінців: у
> початковій вершині лишається непарований вихід, у кінцевій — непарований вхід, тож
> рівно ці дві вершини мають непарний степінь. *Достатність* (виконання умови про
> парність гарантує існування обходу) доводять індукцією за кількістю ребер або
> алгоритмом Флері, що рухається лише ребрами, які не є мостами; приймаємо її без
> подробиць. $\blacksquare$

Навпаки, «додатний» приклад — граф, усі степені якого парні. На рисунку нижче
центральна вершина $o$ має степінь $4$, а решта — степінь $2$; за Теоремою 7.29 граф
ейлерів, і обхід $o\text{–}a\text{–}b\text{–}o\text{–}c\text{–}d\text{–}o$ (номери на
ребрах указують порядок проходження) повертається у старт, скориставшись кожним
ребром рівно раз.

![Граф з ейлеровим циклом: усі степені парні, ребра пронумеровано в порядку обходу](img/l07_euler.png)

**Приклад 7.30 (мости й робочий граф).** У кенігсберзькому мультиграфі степені вершин
дорівнюють $5,3,3,3$ — **чотири** вершини непарного степеня. За Теоремою 7.29 немає ні
ейлерового циклу, ні навіть ейлерового ланцюга: обійти всі сім мостів рівно по разу
**неможливо** — така відповідь Ейлера 1736 року. Натомість робочий граф $G$ має
степеневу послідовність $(3,2,3,2,2)$, тож непарний степінь мають рівно **дві**
вершини — $a$ і $c$. Отже, ейлерів ланцюг існує; наприклад,
$$ a\text{–}b\text{–}c\text{–}e\text{–}d\text{–}a\text{–}c $$
проходить усі шість ребер по разу й веде від $a$ до $c$. Ейлерового *циклу* в $G$
немає.

### Гамільтонові шляхи та цикли

> **Означення (гамільтонів шлях, гамільтонів цикл).** **Гамільтонів шлях** — простий
> ланцюг, що містить **кожну вершину** графа (рівно один раз). Замкнений гамільтонів
> шлях (простий цикл через усі вершини) називають **гамільтоновим циклом**, а граф,
> що його має, — **гамільтоновим**.

Різниця з ейлеровим поняттям — у тому, *що саме* вичерпує обхід: ейлерів — **ребра**,
гамільтонів — **вершини**. Попри позірну симетрію, задачі кардинально різні. Для
ейлеровості є простий локальний критерій (парність степенів), який перевіряється за
один прохід графом. Для гамільтоновості ж **простого критерію не існує**: питання «чи
є в графі гамільтонів цикл?» **NP-складне**, тобто (наскільки відомо) не має
алгоритму, істотно швидшого за повний перебір. Тому послуговуються лише **достатніми**
умовами — вони гарантують цикл, коли граф «достатньо густий».

> **Теорема 7.31 (достатня умова Дірака).** Якщо в простому графі з $n\ge 3$
> вершинами кожна вершина має степінь $\deg v\ge n/2$, то граф має гамільтонів цикл.
> *(наводимо без доведення).*

Умова Дірака лише **достатня**, а не необхідна: граф цілком може бути гамільтоновим і
з меншими степенями.

![Гамільтонів цикл a–b–c–e–d–a у графі G, виділений помаранчевим](img/l07_hamilton.png)

**Приклад 7.32 (гамільтонів цикл у $G$).** У робочому графі кожна з вершин $b,d,e$ має
степінь $2$; тому в будь-який цикл, що проходить через таку вершину, мусять увійти
**обидва** її ребра. Це відразу фіксує ребра $ab,bc$ (через $b$), $ad,de$ (через $d$)
та $ce,de$ (через $e$), а разом із ними цикл однозначно замикається:
$$ a\text{–}b\text{–}c\text{–}e\text{–}d\text{–}a. $$
Він відвідує всі п'ять вершин по разу, отже, $G$ **гамільтонів**. Зауважимо, що умова
Дірака тут **не** виконується (при $n=5$ вона вимагає степеня $\ge n/2=2{,}5$, а
$b,d,e$ мають степінь $2$) — і все ж цикл існує; це вкотре підкреслює, що Дірак дає
лише достатню умову.

### Задача комівояжера

> **Означення (задача комівояжера).** У зваженому повному графі **задача комівояжера**
> (англ. *travelling salesman problem*, TSP) полягає у відшуканні гамільтонового
> циклу **найменшої** сумарної ваги: замкненого маршруту, що виходить із початкової
> вершини, відвідує кожну іншу рівно раз і повертається назад з найменшими сумарними
> витратами.

Назва походить від образу торгового агента, який мусить об'їхати задані міста
найкоротшим замкненим маршрутом. Задача сумнозвісно **складна**: у повному графі на
$n$ вершинах різних гамільтонових циклів аж $\frac{(n-1)!}{2}$, тож повний перебір
стає безнадійним уже за кількох десятків міст; TSP теж **NP-складна**. Тому на
практиці застосовують **наближені** й **евристичні** методи — жадібний алгоритм
«найближчого сусіда» (щоразу переходити в найближче ще не відвідане місто), локальні
покращення обміном ребер (2-opt) чи побудову маршруту з мінімального остовного дерева
([Лекція 8](ODM-L08.md)); вони дають добрий, хоч і не конче оптимальний, тур швидко.

![Задача комівояжера на K₄: оптимальний тур — периметр, що оминає дорогі діагоналі](img/l07_tsp.png)

**Приклад 7.33 (чотири вузли).** Нехай чотири вузли повного графа $K_4$ сполучено з
вагами (відстанями)
$$ w_{12}=3,\quad w_{23}=5,\quad w_{34}=2,\quad w_{14}=4,\quad w_{13}=6,\quad w_{24}=7. $$
У $K_4$ є рівно $\frac{(4-1)!}{2}=3$ різних гамільтонових цикли; порахуймо їхні ваги:
$$ 1\text{–}2\text{–}3\text{–}4\text{–}1:\ 3+5+2+4=14; \qquad 1\text{–}2\text{–}4\text{–}3\text{–}1:\ 3+7+2+6=18; \qquad 1\text{–}3\text{–}2\text{–}4\text{–}1:\ 6+5+7+4=22. $$
Найдешевший тур — $1\text{–}2\text{–}3\text{–}4\text{–}1$ вагою $14$ (периметр квадрата,
що оминає «дорогі» діагоналі $6$ і $7$). Для чотирьох вузлів перебір тривіальний; уся
складність TSP виявляється, коли вузлів десятки й сотні.

> **Застосування у поліграфії.** TSP — не абстракція, а щоденна цехова задача. **Хід
> ножа різака чи плотера:** контури, які треба вирізати або надсікти, — це «міста», а
> мінімізація холостих переміщень різальної головки між ними є прямою задачею
> комівояжера. **Свердління друкованих плат:** свердлильна головка мусить пройти всі
> отвори, і порядок обходу з найменшим сумарним ходом свердла — знову TSP. **Обхід
> елементів макета** при автоматизованому контролі чи лакуванні, а також черговість
> приладки фарбових зон — тієї самої природи. Оскільки точний оптимум задорогий, у
> виробничих контролерах закладають саме наближені евристики.

---

## 7.15 Застосування у видавництві та поліграфії

Мова графів безпосередньо описує задачі фаху:

- **Макет і навігація.** Сторінки видання з переходами (посилання, «далі»,
  перехресні відсилання) — це орграф; зв'язність гарантує, що з будь-якої сторінки
  досяжна будь-яка інша, а напівстепені входу/виходу виявляють «глухі кути» й
  «вузли-концентратори».
- **Трасування друкованих плат і монтажних схем.** З'єднання компонентів — граф;
  можливість розвести провідники в один шар **без перетинів** — це питання
  **планарності** (Наслідки 7.21–7.22 і теорема Понтрягіна–Куратовського).
- **Складання розкладів друку.** Завдання, що конкурують за спільний ресурс (машину,
  фарбову секцію, оператора), — вершини; конфлікт — ребро; безконфліктний розклад —
  це **правильне розфарбування вершин**, а $\chi(G)$ — мінімальна кількість змін/слотів.
- **Кольороподіл і суміжність.** Області зображення, що межують, не повинні
  зливатися в один колір — це розфарбування графа суміжності; теорема про чотири
  фарби гарантує, що для пласкої карти вистачить чотирьох кольорів.
- **Мережі й найкоротші маршрути.** Логістика доставки накладу, топологія
  внутрішньої мережі друкарні — це **зважені графи**; найдешевший кабельний «кістяк»
  — мінімальне **остовне дерево**, а найшвидший маршрут — найкоротший шлях
  ([Лекція 8](ODM-L08.md)).

---

## Підсумок

- **Граф** $G=(V,E)$ поєднує вершини з невпорядкованими ребрами; **орграф**
  використовує впорядковані **дуги**. Прості графи забороняють **петлі** й
  **паралельні ребра**; порядок $=|V|$, розмір $=|E|$.
- **Базові поняття:** суміжність вершин, інцидентність вершини й ребра, **степінь**
  $\deg(v)$ (для орграфа — напівстепені входу $\deg^{-}$ і виходу $\deg^{+}$),
  ізольована та висяча вершини, $\Delta$, $\delta$, регулярність.
- **Лема про рукостискання** (Т. 7.4): $\sum_v\deg(v)=2|E|$ — подвійною лічбою
  інцидентностей; **Наслідок 7.5:** кількість вершин непарного степеня парна.
  Орієнтований варіант (Тв. 7.10): $\sum\deg^{+}=\sum\deg^{-}=|A|$.
- **Подання:** симетрична **матриця суміжності** (суми рядків — степені) та **матриця
  інцидентності** (суми стовпців $=2$); для орграфа матриця суміжності несиметрична.
  **Зважений граф** приписує ребрам ваги $w(e)$.
- **Рух:** маршрут $\supseteq$ **ланцюг** (усі ребра різні) $\supseteq$ **простий
  ланцюг** (усі вершини різні); замкнений ланцюг — **цикл**. Т. 7.14: з маршруту
  дістаємо простий ланцюг.
- **Зв'язність:** досяжність — відношення еквівалентності, а його класи —
  **компоненти зв'язності** (Тв. 7.15).
- **Ізоморфізм** $\cong$: бієкція вершин, що зберігає суміжність. Доводять
  пред'явленням бієкції; спростовують **відмінним інваріантом** (порядок, розмір,
  степенева послідовність, кількість компонент, дводольність). Однакова степенева
  послідовність ізоморфізму *не гарантує*.
- **Планарність:** малюється без перетинів. **Формула Ейлера** $V-E+F=2$ (Т. 7.18)
  дає $E\le 3V-6$ і, без трикутників, $E\le 2V-4$; звідси $K_5$ та $K_{3,3}$
  непланарні. **Теорема Понтрягіна–Куратовського** (Т. 7.23): планарний $\iff$ немає
  підрозбиття $K_5$ чи $K_{3,3}$.
- **Розфарбування:** **хроматичне число** $\chi(G)$ (вершини) з
  $\omega\le\chi\le\Delta+1$ і **хроматичний клас** $\chi'(G)$ (ребра) з
  $\chi'\ge\Delta$, а за Візингом $\chi'\in\{\Delta,\Delta+1\}$; теорема про чотири
  фарби для планарних графів.
- **Дерева й ліс:** дерево — зв'язний ациклічний граф, $|E|=|V|-1$ (Т. 7.26); ліс із
  $c$ компонентами має $n-c$ ребер (Тв. 7.28); остовне дерево — «кістяк» зв'язного
  графа.

## Вправи

### Для розігріву

1. Граф має $10$ вершин, кожна степеня $3$. Скільки в нього ребер? Поясніть, чому
   **не існує** графа з рівно $7$ вершинами, кожна з яких має степінь $3$.
2. Запишіть матрицю суміжності й матрицю інцидентності простого ланцюга
   $a\text{–}b\text{–}c\text{–}d$ та перевірте, що суми рядків дають степені, а кожен
   стовпець матриці інцидентності дає в сумі $2$.
3. Класифікуйте кожен маршрут у графі $G$ як маршрут / ланцюг / простий ланцюг /
   цикл і вкажіть довжину: (i) $b\text{–}a\text{–}c\text{–}b$;
   (ii) $d\text{–}a\text{–}b\text{–}c\text{–}e$; (iii) $a\text{–}c\text{–}a$.

### Стандартні

4. Для орграфа з прикладу 7.9 випишіть матрицю суміжності й перевірте, що суми рядків
   дорівнюють напівстепеням виходу, а суми стовпців — напівстепеням входу.
5. Використавши межі $E\le 3V-6$ і (де доречно) $E\le 2V-4$, з'ясуйте планарність:
   (i) $K_6$; (ii) $K_{2,3}$; (iii) граф Петерсена ($V=10$, $E=15$, без трикутників).
   Для випадків, які межі не вирішують, зазначте це явно.
6. Обчисліть $\chi$ і $\chi'$ для $C_4$, $C_5$ та $K_4$; обґрунтуйте кожне значення.
7. Доведіть, що в будь-якій компанії з $n\ge 2$ осіб знайдуться двоє з однаковою
   кількістю знайомих усередині компанії. (Змоделюйте простим графом і застосуйте
   Твердження 7.7.)

### Підвищеної складності

8. Доведіть, що зв'язний граф на $V$ вершинах має щонайменше $V-1$ ребро, причому
   рівність досягається саме для дерев. (Вказівка: остовне дерево й Теорема 7.26.)
9. З'ясуйте, чи ізоморфні графи $G_1$ і $G_2$; якщо так — наведіть бієкцію й
   перевірте її на ребрах, якщо ні — назвіть відмінний інваріант.
   $G_1$: вершини $\{1,\dots,6\}$, ребра $\{12,23,34,45,56,61\}$;
   $G_2$: вершини $\{1,\dots,6\}$, ребра $\{14,42,25,53,36,61\}$.
10. Зв'язний планарний граф намальовано так, що кожна грань (зокрема зовнішня)
    обмежена рівно $5$ ребрами, і він має $V=20$ вершин. Знайдіть $E$ і $F$.
    (Скористайтеся $\sum_F\deg(F)=2E$ разом із формулою Ейлера.)
11. Доведіть, що простий граф, у якому кожна вершина має степінь $\ge 2$, містить
    цикл. (Вказівка: розгляньте найдовший простий ланцюг і його кінцеву вершину.)