# Лекція 8. Алгоритми на графах

## Огляд

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

Три задачі організують розділ:

1. **Який найдешевший маршрут від однієї вершини до всіх інших?** Це задача про
   найкоротший шлях; для графа з невід'ємними вагами її розв'язує **алгоритм
   Дейкстри** (§8.1).
2. **Яка найдешевша мережа зв'язків, що тримає все з'єднаним?** Це задача про
   **мінімальне остовне дерево** (МОД); її розв'язують два жадібні алгоритми — **Прима**
   (§8.3) і **Крускала** (§8.4), обидва обґрунтовані однією красивою лемою — *властивістю
   розрізу* (§8.2).
3. **Скільки продукту можна пропустити мережею від джерела до споживача?** Це задача
   про **максимальний потік** у транспортній мережі; її розв'язує **алгоритм
   Форда–Фалкерсона** (§8.5–8.6).

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

### Позначення та передумови

Ми спираємося на такі поняття з [Лекції 7](ODM-L07.md):

- **Зважений граф** приписує кожному ребру дійсне число $w(u,v)$ — *вагу*, *довжину*,
  *вартість* чи *пропускну здатність*.
- **Список суміжності** зберігає для кожної вершини $v$ перелік її сусідів разом із
  вагами ребер; він займає $O(n+m)$ пам'яті й дає змогу переглянути всі інцидентні
  вершині ребра за час, пропорційний її степеню. Це подання ми припускаємо всюди.
- **Остовне дерево** зв'язного графа — підграф, що є деревом (зв'язним і без циклів) і
  містить *усі* вершини; воно має рівно $n-1$ ребро.

Ми пишемо $n=|V|$ для кількості вершин і $m=|E|$ для кількості ребер. Усі приклади
розділу проганяються на **одному** зважному графі $G$ (нижче), щоб результати різних
алгоритмів можна було порівняти.

---

## 8.1 Задача про найкоротший шлях. Алгоритм Дейкстри

### Постановка задачі

Нехай задано зважений граф і одну **початкову** вершину $s$ (джерело). Потрібно знайти
найдешевший маршрут від $s$ до *кожної* іншої вершини. Це **задача про найкоротші
шляхи з однієї вершини** (single-source shortest paths) — обчислювальне ядро
GPS-навігації, маршрутизації пакетів (протокол OSPF виконує саме Дейкстру), аналізу
затримок у мережах і безлічі задач планування.

> **Означення (відстань і найкоротший шлях).** **Відстанню** $\delta(s,v)$ від джерела
> $s$ до вершини $v$ називають мінімальну сумарну вагу серед усіх шляхів з $s$ у $v$
> (і $\delta(s,v)=\infty$, якщо $v$ недосяжна). Шлях, що досягає цього мінімуму, —
> **найкоротший шлях**.

**Алгоритм Дейкстри** (E. W. Dijkstra, 1959) знаходить $\delta(s,v)$ для всіх $v$ за
умови, що всі ваги ребер **невід'ємні**. Він тримає для кожної вершини **орієнтовну
відстань** $\text{dist}[v]$ — довжину найкращого знайденого *досі* маршруту до $v$ —
і працює двома чергованими діями:

> **Означення (жадібний вибір і релаксація).** На кожному кроці Дейкстра **фіксує**
> (робить *позначеною*, остаточною) ще незафіксовану вершину $u$ з найменшою поточною
> $\text{dist}[u]$ — це **жадібний вибір найближчої вершини**. Потім він виконує
> **релаксацію** кожного ребра $(u,v)$: якщо
> $$\text{dist}[u] + w(u,v) < \text{dist}[v],$$
> то знайдено коротший маршрут до $v$ *через* $u$, тож покладають
> $\text{dist}[v] \leftarrow \text{dist}[u]+w(u,v)$ і запам'ятовують попередника
> $\text{prev}[v]\leftarrow u$ (щоб потім відновити самий шлях).

Ключова властивість: **щойно вершину вилучено (зафіксовано), її відстань остаточна й
більше ніколи не змінюється** — на цьому тримається доведення коректності.

### Псевдокод

```text
Дейкстра(G, w, s):
    для кожної вершини v графа G:
        dist[v] ← ∞                       # орієнтовна відстань
        prev[v] ← невизначено
    dist[s] ← 0
    Q ← черга з пріоритетом з усіх вершин, ключ = dist
    поки Q не порожня:
        u ← вилучити-мінімум(Q)            # найближча незафіксована вершина
        для кожного сусіда v вершини u:
            alt ← dist[u] + w(u, v)
            якщо alt < dist[v]:            # релаксація
                dist[v] ← alt
                prev[v] ← u
                зменшити-ключ(Q, v, alt)
    повернути dist, prev
```

### Робочий граф

Розгляньмо зважений граф $G=(V,E)$ на семи вершинах $V=\{A,B,C,D,E,F,G\}$ з дев'ятьма
ребрами:

| Ребро | $w$ | Ребро | $w$ | Ребро | $w$ |
|:----:|:---:|:----:|:---:|:----:|:---:|
| $A\text{–}D$ | 5 | $D\text{–}F$ | 6 | $C\text{–}G$ | 7 |
| $A\text{–}B$ | 9 | $B\text{–}F$ | 4 | $E\text{–}G$ | 10 |
| $D\text{–}B$ | 2 | $B\text{–}C$ | 8 | $F\text{–}E$ | 3 |

![Зважений граф G на семи вершинах A–G із дев'ятьма позначеними вагами ребер](img/l08_graph.png)

Усі дев'ять ваг **різні** — це, як ми доведемо в §8.2, робить мінімальне остовне дерево
*єдиним*, тож Прим і Крускал у §8.3–8.4 мусять дати той самий набір ребер.

### Покроковий приклад: Дейкстра з джерела $A$

Проженемо алгоритм із джерела $A$. Кожен рядок таблиці показує масив орієнтовних
відстаней *після* фіксації чергової вершини; стовпець «Позначено» називає щойно
вилучену вершину (з її вже остаточною відстанню), а прочерк «$-$» означає «ще не
досягнута» ($\infty$). **Жирним** позначено значення, яке щойно *суворо покращилося*
релаксацією.

| Крок | Позначено | $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ |
|:----:|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 0 (старт) | — | 0 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ |
| 1 | $A\,(0)$  | 0 | 9 | $-$ | 5 | $-$ | $-$ | $-$ |
| 2 | $D\,(5)$  | 0 | **7** | $-$ | 5 | $-$ | 11 | $-$ |
| 3 | $B\,(7)$  | 0 | 7 | 15 | 5 | $-$ | 11 | $-$ |
| 4 | $F\,(11)$ | 0 | 7 | 15 | 5 | 14 | 11 | $-$ |
| 5 | $E\,(14)$ | 0 | 7 | 15 | 5 | 14 | 11 | 24 |
| 6 | $C\,(15)$ | 0 | 7 | 15 | 5 | 14 | 11 | **22** |
| 7 | $G\,(22)$ | 0 | 7 | 15 | 5 | 14 | 11 | 22 |

Читаємо кроки уважно:

- **Крок 1.** Фіксуємо $A$ (відстань $0$); релаксуємо його ребра: $B=9$ (через $A\text{–}B$)
  і $D=5$ (через $A\text{–}D$).
- **Крок 2.** Найменша орієнтовна відстань — це $D=5$; фіксуємо $D$ і релаксуємо його
  ребра. Ребро $D\text{–}B$ дає $5+2=7<9$, тож **$B$ покращується з $9$ до $7$** (маршрут
  $A\to D\to B$ дешевший за пряме ребро $A\to B$). Ребро $D\text{–}F$ дає $F=5+6=11$.
- **Крок 3.** Фіксуємо $B=7$; релаксуємо $B\text{–}C$: $7+8=15$, тож $C=15$. Ребро
  $B\text{–}F$ дає $7+4=11$ — це *не менше* за наявні $11$, тож $F$ не змінюється.
- **Крок 4.** Фіксуємо $F=11$; релаксуємо $F\text{–}E$: $11+3=14$, тож $E=14$.
- **Крок 5.** Фіксуємо $E=14$; релаксуємо $E\text{–}G$: $14+10=24$, тож $G=24$ (перше
  досягнення $G$).
- **Крок 6.** Фіксуємо $C=15$; релаксуємо $C\text{–}G$: $15+7=22<24$, тож **$G$
  покращується з $24$ до $22$** — довший маршрут через $E$ відкинуто на користь маршруту
  через $C$.
- **Крок 7.** Фіксуємо $G=22$; покращувати більше нічого. Готово.

Остаточні відстані від $A$:

$$
A=0,\quad D=5,\quad B=7,\quad F=11,\quad E=14,\quad C=15,\quad G=22,
$$

а **порядок фіксації** вершин — рівно $A(0)\to D(5)\to B(7)\to F(11)\to E(14)\to
C(15)\to G(22)$: вершини стають позначеними в порядку зростання їхньої остаточної
відстані. Зверніть увагу на дві релаксації, що *покращили* вже досягнуте значення
($B\colon 9\to 7$ і $G\colon 24\to 22$) — це і є суть релаксації.

> **Зауваження (позначені та непозначені вершини).** Слайдова подача цієї самої задачі
> показує лише *позначені* (остаточні) мітки, що з'являються по одній: спочатку $A{=}0$,
> потім додається $D{=}5$, далі $B{=}7$, $F{=}11$, $E{=}14$, $C{=}15$ і нарешті $G{=}22$.
> Це — головна діагональ нашої таблиці (стовпець «Позначено»). Повна таблиця багатша: вона
> показує ще й *орієнтовні* мітки непозначених вершин, які змінюються дорогою.

### Відновлення шляху

Щоб відновити самий найкоротший шлях, ідуть за вказівниками $\text{prev}$ у зворотному
напрямку. Для $G$:
$$
\text{prev}[G]=C,\ \text{prev}[C]=B,\ \text{prev}[B]=D,\ \text{prev}[D]=A,
$$
тобто найкоротший шлях $A\to D\to B\to C\to G$ довжини $5+2+8+7=22$. Так само відновлюємо
найкоротші шляхи до всіх вершин:

| Вершина | Найкоротший шлях від $A$ | Довжина |
|:-------:|:-------------------------|:-------:|
| $D$ | $A\to D$ | $5$ |
| $B$ | $A\to D\to B$ | $5+2=7$ |
| $F$ | $A\to D\to F$ | $5+6=11$ |
| $E$ | $A\to D\to F\to E$ | $5+6+3=14$ |
| $C$ | $A\to D\to B\to C$ | $5+2+8=15$ |
| $G$ | $A\to D\to B\to C\to G$ | $5+2+8+7=22$ |

Разом усі вказівники $\text{prev}$ утворюють **дерево найкоротших шляхів** з коренем $A$:
$$
\{A\text{–}D,\ D\text{–}B,\ D\text{–}F,\ F\text{–}E,\ B\text{–}C,\ C\text{–}G\}.
$$

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

![Дерево найкоротших шляхів від A (помаранчеві ребра); біля кожної вершини — її відстань, найдальша вершина G на відстані 22](img/l08_dijkstra_tree.png)

### Коректність (коротко)

Ідея коректності — **інваріант зафіксованої відстані**: щойно вершину вилучено з черги,
її мітка вже дорівнює справжній відстані.

> **Теорема 8.1 (коректність Дейкстри).** Якщо всі ваги невід'ємні, то в мить вилучення
> вершини $u$ з $Q$ виконано $\text{dist}[u]=\delta(s,u)$. Отже, усі остаточні відстані
> правильні.
>
> *Доведення (від супротивного).* Спершу зауважимо два прості факти. **(А)** У будь-який
> момент $\text{dist}[v]\ge\delta(s,v)$, і якщо $\text{dist}[v]$ скінченна, то це довжина
> *якогось* реального шляху $s\to v$ (релаксація лише подовжує реальний шлях на одне
> ребро). **(Б)** Кожен префікс найкоротшого шляху сам є найкоротшим шляхом до своєї
> кінцевої вершини.
>
> Припустимо, що теорема хибна, і нехай $u$ — **перша** вилучена вершина, для якої
> $\text{dist}[u]\ne\delta(s,u)$; за фактом (А) тоді $\text{dist}[u]>\delta(s,u)$.
> Візьмімо найкоротший шлях $P$ з $s$ у $u$ і нехай $S$ — множина вже зафіксованих вершин
> перед вилученням $u$. Шлях $P$ починається в $S$ (бо $s\in S$) і закінчується поза $S$
> (бо $u\notin S$); нехай $y$ — перша вершина $P$ поза $S$, а $x$ — її попередник на $P$
> (отже $x\in S$). Оскільки $x$ зафіксовано раніше й (за вибором $u$) правильно, у мить
> фіксації $x$ ми релаксували ребро $(x,y)$, тож
> $\text{dist}[y]\le\text{dist}[x]+w(x,y)=\delta(s,x)+w(x,y)=\delta(s,y)$ (остання рівність
> — факт (Б)). Разом із (А): $\text{dist}[y]=\delta(s,y)$. Тепер відрізок $P$ від $y$ до
> $u$ має **невід'ємну** вагу (єдине місце, де потрібна невід'ємність!), тому
> $\delta(s,y)\le\delta(s,u)$. Складаємо ланцюжок:
> $$\text{dist}[y]=\delta(s,y)\le\delta(s,u)<\text{dist}[u].$$
> Але $y$ і $u$ обидві були в $Q$, і алгоритм обрав саме $u$ як вершину з **найменшою**
> міткою, тобто $\text{dist}[u]\le\text{dist}[y]$ — суперечність. Отже, такої $u$ немає.
> $\blacksquare$

> **Типова помилка (від'ємні ваги).** Для графа з від'ємною вагою Дейкстра може дати
> **неправильний** результат: вона фіксує вершину назавжди й не переглядає її, а від'ємне
> ребро згодом здатне відкрити коротший маршрут. Для таких графів застосовують алгоритм
> **Беллмана–Форда** (релаксує всі ребра $n-1$ разів за $O(nm)$ і виявляє цикли від'ємної
> ваги). Умова невід'ємності ваг для Дейкстри — не дрібниця, а суттєва передумова.

### Складність

Час залежить винятково від черги з пріоритетом. Вилучень-мінімуму рівно $n$, а
релаксацій (зменшень ключа) — не більш ніж $m$. З **двійковою купою** обидві операції
коштують $O(\log n)$, тож увесь алгоритм — $O((n+m)\log n)$. На щільних графах вигіднішим
буває невпорядкований масив: $O(n^2)$.

> **Зауваження (ліниве видалення).** Багато реалізацій узагалі не мають операції
> «зменшити-ключ»: під час релаксації вони просто *додають* у купу нову пару
> $(\text{dist}, v)$, а під час вилучення відкидають застарілі пари, чий ключ більший за
> поточну $\text{dist}[v]$. Купа може містити до $m$ записів, але $\log m\le 2\log n$, тож
> оцінка $O((n+m)\log n)$ зберігається. Це трохи більше пам'яті в обмін на суттєво простіший
> код — так робить більшість стандартних бібліотек.

---

## 8.2 Мінімальне остовне дерево. Властивість розрізу

### Задача

> **Означення (мінімальне остовне дерево).** **Мінімальне остовне дерево** (МОД, англ.
> minimum spanning tree) зв'язного зваженого графа — це остовне дерево *найменшої
> сумарної ваги ребер*.

МОД відповідає на запитання «яка найдешевша сукупність зв'язків тримає всю мережу
з'єднаною?» — прокладання кабелю, доріг, трубопроводів; воно ж лежить в основі деяких
алгоритмів кластеризації. Обидва алгоритми, що ми розглянемо (Прим і Крускал), жадібні,
і обидва обґрунтовуються **однією** лемою. Щоб її сформулювати, потрібен словник розрізів.

> **Означення (розріз, перетинне ребро, легке ребро).** **Розрізом** називають розбиття
> вершин на дві непорожні частини $(S,\ V\setminus S)$. Ребро **перетинає** розріз, якщо
> один його кінець лежить у $S$, а другий — у $V\setminus S$. Перетинне ребро найменшої
> ваги називають **легким ребром** розрізу. Кажуть, що набір ребер $A$ **узгоджений** із
> розрізом, якщо *жодне* ребро $A$ не перетинає цей розріз.

![Розріз (S, V∖S) із S = {A, D}; перетинні ребра A–B, D–B, D–F; легке ребро розрізу — D–B вагою 2](img/l08_cut.png)

### Властивість розрізу

> **Теорема 8.2 (властивість розрізу).** Нехай набір ребер $A$ міститься в якомусь МОД
> графа $G$. Нехай $(S,V\setminus S)$ — будь-який розріз, узгоджений з $A$, і нехай $e$ —
> легке ребро цього розрізу. Тоді ребро $e$ **безпечне** для $A$, тобто $A\cup\{e\}$ також
> міститься в якомусь МОД.
>
> *Доведення (обмінний аргумент).* Нехай $T$ — МОД, що містить $A$. Якщо $e\in T$ — усе
> доведено. Тож припустимо $e=(u,v)\notin T$, де $u\in S$, $v\in V\setminus S$. Додавання
> $e$ до дерева $T$ утворює рівно **один** цикл $\mathcal C$ (у дереві між $u$ і $v$ уже є
> єдиний шлях, а ребро $e$ замикає його в цикл). Обходячи $\mathcal C$, ми стартуємо в
> $u\in S$, ребром $e$ переходимо у $v\in V\setminus S$ і зрештою повертаємось у $u$; що
> кожен перетин розрізу змінює бік, а закінчити треба там, де почали, — цикл перетинає
> розріз **парну** кількість разів. Один перетин — це саме $e$; отже, є ще принаймні один
> перетин, ребром $e'\ne e$. Це $e'$ не належить $A$ (бо $A$ узгоджений із розрізом, а $e'$
> його перетинає). Виконаймо **обмін**: покладемо $T'=(T\setminus\{e'\})\cup\{e\}$.
> Вилучення ребра $e'$, що лежить на циклі, зберігає зв'язність; $T'$ має ті самі $n-1$
> ребро, тож $T'$ — остовне дерево. Його вага
> $$w(T')=w(T)-w(e')+w(e).$$
> Оскільки $e$ — легке (мінімальне) перетинне ребро, а $e'$ теж перетинає, то
> $w(e)\le w(e')$, звідки $w(T')\le w(T)$. Але $T$ — МОД, тож $w(T')\ge w(T)$; отже,
> $w(T')=w(T)$ і $T'$ — теж МОД. При цьому $A\subseteq T'$ (ми вилучили $e'\notin A$ й
> додали $e$) і $e\in T'$, тобто $A\cup\{e\}\subseteq T'$: ребро $e$ безпечне. $\blacksquare$

> **Наслідок 8.3 (єдиність МОД).** Якщо всі ваги ребер різні, то МОД єдине. Справді, за
> різних ваг нерівність $w(e)\le w(e')$ у доведенні стає *суворою* для легкого ребра, тож
> кожен розріз має рівно одне легке ребро, і воно належить кожному МОД — це однозначно
> визначає дерево. $\blacksquare$

Наш граф $G$ має різні ваги, отже, його МОД єдине, і Прим із Крускалом мусять повернути
**однаковий** набір ребер, а не лише однакову вагу.

---

## 8.3 Алгоритм Прима

### Ідея та псевдокод

**Алгоритм Прима** (V. Jarník 1930; R. Prim 1957) вирощує *одне* дерево, розпочинаючи з
довільної стартової вершини. Він тримає множину вершин дерева й на кожному кроці додає
**найдешевше ребро, що з'єднує дерево з вершиною поза ним**. Кожна вершина $v$ поза
деревом зберігає $\text{key}[v]$ — вагу найдешевшого відомого ребра, що сполучає її з
поточним деревом, а черга з пріоритетом видає глобальний мінімум.

```text
Прим(G, w, s):
    для кожної вершини v:
        key[v] ← ∞               # вага найдешевшого ребра з v до дерева
        parent[v] ← невизначено
        inMST[v] ← хиба
    key[s] ← 0
    Q ← черга з пріоритетом з усіх вершин, ключ = key
    поки Q не порожня:
        u ← вилучити-мінімум(Q)
        inMST[u] ← істина
        для кожного сусіда v вершини u:
            якщо (не inMST[v]) і w(u, v) < key[v]:
                key[v] ← w(u, v)
                parent[v] ← u
                зменшити-ключ(Q, v, key[v])
    повернути { (v, parent[v]) : v ≠ s }      # ребра МОД
```

### Покроковий приклад: Прим із вершини $A$

Проженемо Прим на $G$ від $A$. Кожен рядок показує масив $\text{key}[\,]$ після чергової
фіксації; знак «$\bullet$» означає «вершина вже в дереві», **жирне** — щойно покращений
ключ. **Додане ребро** — це $(\text{parent}[u],u)$ для вилученої вершини $u$.

| Крок | Вилучено | Додане ребро | $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ |
|:----:|:--------:|:------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 0 | — | — | 0 | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| 1 | $A$ | — | $\bullet$ | 9 | $\infty$ | 5 | $\infty$ | $\infty$ | $\infty$ |
| 2 | $D\,(5)$ | $A\text{–}D$ | $\bullet$ | **2** | $\infty$ | $\bullet$ | $\infty$ | 6 | $\infty$ |
| 3 | $B\,(2)$ | $D\text{–}B$ | $\bullet$ | $\bullet$ | 8 | $\bullet$ | $\infty$ | **4** | $\infty$ |
| 4 | $F\,(4)$ | $B\text{–}F$ | $\bullet$ | $\bullet$ | 8 | $\bullet$ | **3** | $\bullet$ | $\infty$ |
| 5 | $E\,(3)$ | $F\text{–}E$ | $\bullet$ | $\bullet$ | 8 | $\bullet$ | $\bullet$ | $\bullet$ | 10 |
| 6 | $C\,(8)$ | $B\text{–}C$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | **7** |
| 7 | $G\,(7)$ | $C\text{–}G$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |

Розповідь:

- **Крок 1.** Зі старту $A$ ключі сусідів $B,D$ стають $9,5$.
- **Крок 2.** Вилучаємо $D$ (ключ $5$ — найменший), додаємо ребро $A\text{–}D$. Релаксація
  ребер $D$ *опускає* $\text{key}[B]$ з $9$ до $2$ (ребро $D\text{–}B$) і задає
  $\text{key}[F]=6$.
- **Крок 3.** Вилучаємо $B$ (ключ $2$), додаємо $D\text{–}B$. Ребро $B\text{–}F$ опускає
  $\text{key}[F]$ з $6$ до $4$; ребро $B\text{–}C$ задає $\text{key}[C]=8$.
- **Крок 4.** Вилучаємо $F$ (ключ $4$), додаємо $B\text{–}F$. Ребро $F\text{–}E$ задає
  $\text{key}[E]=3$.
- **Крок 5.** Вилучаємо $E$ (ключ $3$), додаємо $F\text{–}E$. Ребро $E\text{–}G$ задає
  $\text{key}[G]=10$.
- **Крок 6.** Вилучаємо $C$ (ключ $8$), додаємо $B\text{–}C$. Ребро $C\text{–}G$ опускає
  $\text{key}[G]$ з $10$ до $7$.
- **Крок 7.** Вилучаємо $G$ (ключ $7$), додаємо $C\text{–}G$. Дерево завершене.

![Прим, крок 2: дерево {A–D, D–B} з двома помаранчевими ребрами](img/l08_prim1.png)

![Прим, крок 4: дерево {A–D, D–B, B–F, F–E} з чотирма помаранчевими ребрами](img/l08_prim2.png)

Ребра МОД: $\{A\text{–}D,\ D\text{–}B,\ B\text{–}F,\ F\text{–}E,\ B\text{–}C,\
C\text{–}G\}$; сумарна вага $5+2+4+3+8+7=\mathbf{29}$. Шість ребер на сім вершин —
коректне остовне дерево. Зверніть увагу: Прим додавав ваги в порядку $5,2,4,3,8,7$ — він
щоразу бере найдешевше ребро *на межі* свого дерева, а це загалом **не** найдешевше з усіх
ребер, що лишилися (пор. Крускал у §8.4).

![Мінімальне остовне дерево графа G (єдине): помаранчеві ребра дерева, вага 29](img/l08_mst.png)

### Коректність

> **Теорема 8.4.** Алгоритм Прима повертає мінімальне остовне дерево.
>
> *Доведення.* Нехай $A$ — множина вже дібраних ребер, а $S$ — множина вершин дерева.
> Доводимо індукцією за кроками інваріант: *$A$ міститься в якомусь МОД*. **База:**
> $A=\varnothing$ міститься в будь-якому МОД. **Крок:** нехай $A$ у якомусь МОД. Кожне
> ребро $A$ сполучає дві вершини дерева, тож лежить усередині $S$, отже, $A$ **узгоджений**
> із розрізом $(S,V\setminus S)$. Наступне ребро, яке додає Прим, — за побудовою
> мінімальне ребро від $S$ до $V\setminus S$, тобто **легке ребро** цього розрізу. За
> властивістю розрізу (Теорема 8.2) воно безпечне, отже, $A\cup\{e\}$ теж у якомусь МОД —
> інваріант зберігається. Коли $Q$ спорожніє, $S=V$ і $A$ має $n-1$ ребро, що утворюють
> остовне дерево, яке міститься в МОД, — а це і є те МОД. $\blacksquare$

### Складність

Структурно Прим — це Дейкстра з іншим ключем («найдешевше ребро в дерево» замість
«відстань від джерела»), тож і час той самий: $O((n+m)\log n)$ з двійковою купою або
$O(n^2)$ з масивом (краще для щільних графів).

> **Типова помилка.** Прим вимагає **зв'язного** графа; на незв'язному він побудує лише
> дерево компоненти стартової вершини. Також релаксувати треба лише до вершин, які *ще не
> в дереві*.

---

## 8.4 Алгоритм Крускала

### Ідея та псевдокод

**Алгоритм Крускала** (J. Kruskal, 1956) підходить до МОД з боку *ребер*. Він сортує
**всі** ребра за зростанням ваги й переглядає їх по черзі, додаючи ребро до зростаючого
**лісу** щоразу, коли воно **не утворює циклу** — тобто коли його кінці лежать у *різних*
компонентах. Алгоритм зупиняється, коли додано $n-1$ ребро.

```text
Крускал(G, w):
    A ← ∅                              # набір ребер МОД
    для кожної вершини v: MakeSet(v)
    відсортувати всі ребра за зростанням ваги
    для кожного ребра (u, v) у відсортованому порядку:
        якщо Find(u) ≠ Find(v):        # кінці в різних компонентах
            A ← A ∪ { (u, v) }
            Union(u, v)
            якщо |A| = n − 1: зупинитися
    повернути A
```

### Система неперетинних множин (union–find)

Єдина нетривіальна операція — швидко перевіряти «в одній компоненті?» й оновлювати
компоненти після злиття. Це робота **системи неперетинних множин** (union–find), що
підтримує розбиття вершин на неперетинні множини — поточні компоненти лісу — трьома
операціями:

- `MakeSet(x)` — покласти $x$ в окрему одноелементну множину;
- `Find(x)` — повернути канонічного **представника** (корінь) множини $x$; дві вершини в
  одній множині **тоді й лише тоді**, коли їхні представники збігаються;
- `Union(x, y)` — злити множини, що містять $x$ і $y$.

Кожну множину зберігають як кореневе дерево через масив $\text{parent}$ (корінь указує сам
на себе); `Find` іде вказівниками до кореня. Дві оптимізації тримають дерева пласкими:
**об'єднання за рангом** (менше дерево підвішують під більше) і **стиснення шляхів** (під
час `Find` кожну пройдену вершину перепідвішують просто до кореня). Разом вони дають
амортизований час $O(\alpha(n))$ на операцію, де $\alpha$ — обернена функція Аккермана,
що зростає так повільно, що $\alpha(n)\le 4$ для будь-якого мислимого $n$ — практично
стала.

### Покроковий приклад: Крускал на $G$

Відсортовані ребра графа $G$:
$$
D\text{–}B\,(2),\ F\text{–}E\,(3),\ B\text{–}F\,(4),\ A\text{–}D\,(5),\ D\text{–}F\,(6),\
C\text{–}G\,(7),\ B\text{–}C\,(8),\ A\text{–}B\,(9),\ E\text{–}G\,(10).
$$

| Ребро | $w$ | $\text{Find}(u)$ vs $\text{Find}(v)$ | Цикл? | Дія | Компоненти після |
|:----:|:---:|:------------------------------------:|:-----:|:----|:-----------------|
| $D\text{–}B$ | 2 | $D\ne B$ | ні | **додати** | $\{DB\},\{A\},\{C\},\{E\},\{F\},\{G\}$ |
| $F\text{–}E$ | 3 | $F\ne E$ | ні | **додати** | $\{DB\},\{FE\},\{A\},\{C\},\{G\}$ |
| $B\text{–}F$ | 4 | $B\ne F$ | ні | **додати** | $\{DBFE\},\{A\},\{C\},\{G\}$ |
| $A\text{–}D$ | 5 | $A\ne D$ | ні | **додати** | $\{ADBFE\},\{C\},\{G\}$ |
| $D\text{–}F$ | 6 | $D=F$ | **так** | пропустити | $\{ADBFE\},\{C\},\{G\}$ |
| $C\text{–}G$ | 7 | $C\ne G$ | ні | **додати** | $\{ADBFE\},\{CG\}$ |
| $B\text{–}C$ | 8 | $B\ne C$ | ні | **додати** | $\{ADBFECG\}$ — усе |
| $A\text{–}B$ | 9 | $A=B$ | так | пропустити | (уже $6$ ребер) |
| $E\text{–}G$ | 10 | $E=G$ | так | пропустити | — |

![Ребра за зростанням ваги: додані до МОД (D–B, F–E, B–F, A–D, C–G, B–C) позначено галочкою, пропущені як цикл (D–F, A–B, E–G) — хрестиком](img/l08_kruskal_sorted.png)

Ребра МОД: $\{D\text{–}B,\ F\text{–}E,\ B\text{–}F,\ A\text{–}D,\ C\text{–}G,\
B\text{–}C\}$; сумарна вага $2+3+4+5+7+8=\mathbf{29}$.

**Це те саме дерево, що знайшов Прим** (обидва дають $\{A\text{–}D, D\text{–}B, B\text{–}F,
F\text{–}E, B\text{–}C, C\text{–}G\}$, вага $29$) — як і гарантує Наслідок 8.3, адже ваги
$G$ різні. Ребро $D\text{–}F\,(6)$ було **пропущене**, бо $D$ і $F$ уже лежали в одній
компоненті $\{A,D,B,F,E\}$: додавання замкнуло б цикл $D\text{–}B\text{–}F\text{–}D$, на
якому $D\text{–}F$ — найважче ребро.

### Трасування union–find

Простежмо структуру неперетинних множин крізь **об'єднання** Крускала (у порядку доданих
ребер), стартуючи з кожної вершини як окремого кореня з рангом $0$.

| Операція | Дія (об'єднання за рангом) | Корені після |
|:---------|:---------------------------|:-------------|
| `Union(D,B)` | рівні ранги: $\text{parent}[B]{=}D$, $\text{rank}[D]{=}1$ | $D\!:\{D,B\}$ |
| `Union(F,E)` | рівні ранги: $\text{parent}[E]{=}F$, $\text{rank}[F]{=}1$ | $F\!:\{F,E\}$ |
| `Union(B,F)` | $\text{Find}(B){=}D,\ \text{Find}(F){=}F$, рівні ранги $1$: $\text{parent}[F]{=}D$, $\text{rank}[D]{=}2$ | $D\!:\{D,B,F,E\}$ |
| `Union(A,D)` | $\text{rank}[A]{=}0<\text{rank}[D]{=}2$: $\text{parent}[A]{=}D$ | $D\!:\{A,D,B,F,E\}$ |
| `Union(C,G)` | рівні ранги: $\text{parent}[G]{=}C$, $\text{rank}[C]{=}1$ | $C\!:\{C,G\}$ |
| `Union(B,C)` | $\text{rank}[C]{=}1<\text{rank}[D]{=}2$: $\text{parent}[C]{=}D$ | $D\!:\{A,B,C,D,E,F,G\}$ |

Після цих операцій виклик $\text{Find}(E)$ проходить $E\to F\to D$ і завдяки **стисненню
шляхів** перепідвішує $\text{parent}[E]\leftarrow D$, тож наступний $\text{Find}(E)$ — це
вже один крок. Саме так дві оптимізації тримають дерева пласкими.

### Коректність

> **Теорема 8.5.** Алгоритм Крускала повертає мінімальне остовне дерево.
>
> *Доведення.* Знову доводимо інваріант «набір $A$ міститься в якомусь МОД» індукцією за
> додаваннями. Нехай Крускал збирається **додати** ребро $e=(u,v)$, бо
> $\text{Find}(u)\ne\text{Find}(v)$. Нехай $S$ — компонента вершини $u$ в поточному лісі;
> візьмімо розріз $(S,V\setminus S)$. Кожне ребро $A$ лежить усередині якоїсь компоненти,
> тож $A$ **узгоджений** із цим розрізом, а $e$ його перетинає. Ба більше, $e$ — легке
> ребро розрізу: якби якесь перетинне ребро $e'$ мало $w(e')<w(e)$, то Крускал розглянув би
> $e'$ *раніше* (порядок за зростанням ваги) і додав би його (його кінці й тоді були в
> різних компонентах, бо компоненти лише зливаються), тобто $e'\in A$ — суперечність із
> тим, що $A$ узгоджений. За властивістю розрізу (Теорема 8.2) $e$ безпечне. Пропущені
> ребра нешкідливі: ребро пропускають лише тоді, коли його кінці вже з'єднані дешевшими
> ребрами, тож воно найважче на своєму циклі й не належить жодному МОД. $\blacksquare$

### Складність

Домінує **сортування** $m$ ребер: $O(m\log m)=O(m\log n)$. Усі операції union–find разом
коштують $O(m\,\alpha(n))$ — практично лінійно й дешевше за сортування. Отже, Крускал
працює за $O(m\log n)$.

> **Прим чи Крускал?** Обидва дають те саме МОД. **Прим** вирощує одне зв'язне дерево від
> зерна, беручи найдешевше ребро на *межі*; його масивна версія $O(n^2)$ незалежна від $m$,
> тож він добрий на **щільних** графах. **Крускал** розглядає ребра глобально від
> найдешевшого, склеюючи окремі фрагменти лісу; він добрий на **розріджених** графах і
> коли ребра вже відсортовані.

> **Історична довідка.** Задачу про МОД першим поставив і розв'язав **Отакар Боровка**
> (1926), проєктуючи ефективну електромережу Моравії. Метод вирощування одного дерева
> описав **Войтех Ярник** (1930); згодом його незалежно перевідкрили **Роберт Прим**
> (1957) і **Едсгер Дейкстра** (1959). Той самий Дейкстра в короткій нотатці 1959 р.
> опублікував і свій алгоритм найкоротших шляхів, придуманий, за його спогадами, хвилин за
> двадцять «подумки» в амстердамській кав'ярні. **Джозеф Крускал** оприлюднив свій алгоритм
> 1956 р. Через таку потрійну історію алгоритм Прима іноді звуть алгоритмом **Ярника–Прима**.

---

## 8.5 Транспортні мережі

Досі ваги ребер означали *довжину*. Тепер вони означатимуть *пропускну здатність* —
скільки продукту дуга здатна пропустити за одиницю часу.

> **Означення (транспортна мережа).** **Транспортна мережа** — це орієнтований граф
> $G=(V,E)$ з двома виділеними вершинами: **джерелом** $s$ (звідки продукт витікає) і
> **стоком** $t$ (куди він стікає), у якому кожній дузі $(u,v)$ приписано невід'ємну
> **пропускну здатність** $c(u,v)\ge 0$.

> **Означення (потік).** **Потоком** називають функцію $f$, що приписує кожній дузі число
> $f(u,v)$ і задовольняє дві умови:
> - **обмеження пропускної здатності:** $0\le f(u,v)\le c(u,v)$ для кожної дуги (крізь
>   дугу не можна пропустити більше, ніж вона витримує);
> - **збереження потоку:** для кожної проміжної вершини $v\ne s,t$ сума вхідного потоку
>   дорівнює сумі вихідного:
>   $$\sum_{(u,v)\in E} f(u,v) \;=\; \sum_{(v,w)\in E} f(v,w).$$
>
> **Величиною потоку** $|f|$ називають чистий потік, що витікає з джерела (він дорівнює
> чистому потоку, що втікає у стік):
> $$|f| \;=\; \sum_{(s,w)\in E} f(s,w) \;-\; \sum_{(u,s)\in E} f(u,s).$$

Дугу називають **насиченою**, якщо $f(u,v)=c(u,v)$ (заповнена вщерть), і **порожньою**,
якщо $f(u,v)=0$.

![Транспортна мережа: джерело s, стік t, проміжні вершини u, v; на кожній дузі — позначення «потік/пропускна здатність», спочатку 0/3](img/l08_network.png)

> **Означення (розріз мережі та його пропускна здатність).** **Розрізом** мережі
> називають розбиття вершин $(S,T)$, у якому $s\in S$ і $t\in T$. **Пропускною здатністю**
> розрізу $c(S,T)$ називають суму пропускних здатностей дуг, що йдуть *із $S$ у $T$* (лише
> в цьому напрямку):
> $$c(S,T)=\sum_{\substack{(u,v)\in E \\ u\in S,\ v\in T}} c(u,v).$$

Фундаментальний зв'язок між потоками й розрізами — **слабка двоїстість**:

> **Твердження 8.6 (потік не перевищує розрізу).** Для будь-якого потоку $f$ і будь-якого
> розрізу $(S,T)$ виконано $|f|\le c(S,T)$.
>
> *Ідея доведення.* Увесь потік з $s$ у $t$ мусить *хоч раз* перетнути межу з $S$ у $T$;
> сумарний потік крізь межу дорівнює $|f|$ (за збереженням у проміжних вершинах), а він
> обмежений сумою пропускних здатностей прямих дуг межі, тобто $c(S,T)$. $\blacksquare$

Отже, величина будь-якого потоку $\le$ пропускної здатності будь-якого розрізу; зокрема,
**максимальний потік $\le$ мінімальний розріз**. У §8.6 ми побачимо, що насправді тут
завжди рівність.

---

## 8.6 Максимальний потік. Алгоритм Форда–Фалкерсона

### Залишкова мережа та збільшуючий ланцюг

Як збільшувати потік? Наївна ідея «шукати ще не насичені шляхи від $s$ до $t$ і доливати
по них» майже правильна, але недостатня: іноді, щоб дійти оптимуму, доводиться *відкликати*
частину вже пущеного потоку. Це вловлює поняття залишкової мережі.

> **Означення (залишкова мережа).** Для потоку $f$ **залишкова мережа** має на кожній дузі
> дві залишкові пропускні здатності:
> - *за напрямком* дуги $(u,v)$ можна додати ще $c(u,v)-f(u,v)$ одиниць — це працює, поки
>   дуга **не насичена**;
> - *проти напрямку* дуги $(u,v)$ можна «повернути» до $f(u,v)$ одиниць (зменшивши потік)
>   — це працює, поки дуга **не порожня**.

> **Означення (збільшуючий / чередуючий ланцюг).** **Збільшуючим ланцюгом** називають
> маршрут із $s$ у $t$ у залишковій мережі. Його будують, чергуючи напрямки: дугу проходять
>
> - **за напрямком** — якщо вона **не насичена** ($f<c$), або
> - **проти напрямку** — якщо вона **не порожня** ($f>0$).
>
> **Пропускна здатність ланцюга** $\Delta$ — це мінімальна залишкова пропускна здатність
> уздовж нього. Пустивши уздовж ланцюга ще $\Delta$ одиниць (додаючи $\Delta$ до прямих дуг
> і віднімаючи $\Delta$ від зворотних), дістаємо новий коректний потік, більший на $\Delta$.

### Псевдокод

```text
Форд–Фалкерсон(G, c, s, t):
    для кожної дуги (u, v): f(u, v) ← 0
    поки в залишковій мережі існує збільшуючий ланцюг P від s до t:
        Δ ← мінімальна залишкова пропускна здатність уздовж P
        для кожної дуги ланцюга P:
            якщо дугу пройдено за напрямком:  f ← f + Δ
            якщо дугу пройдено проти напрямку: f ← f − Δ
    повернути f            # максимальний потік
```

За цілих пропускних здатностей кожна ітерація збільшує $|f|$ принаймні на $1$, тож
алгоритм завершується, і підсумковий потік теж цілий (**теорема про цілочисловість**).

> **Зауваження (вибір ланцюга).** За *ірраціональних* пропускних здатностей і невдалого
> вибору ланцюгів метод може не завершитися взагалі. Тому на практиці збільшуючий ланцюг
> шукають **пошуком у ширину** (найкоротший за кількістю дуг) — це варіант **Едмондса–Карпа**,
> що гарантовано завершується за $O(n\,m^2)$ незалежно від величин пропускних здатностей.

### Теорема про максимальний потік і мінімальний розріз

> **Теорема 8.7 (Форд–Фалкерсон; max-flow min-cut).** Для будь-якої транспортної мережі
> величина **максимального потоку** дорівнює пропускній здатності **мінімального розрізу**:
> $$\max_f |f| \;=\; \min_{(S,T)} c(S,T).$$
> Потік $f$ максимальний тоді й лише тоді, коли в залишковій мережі **немає** збільшуючого
> ланцюга.
>
> *Ідея доведення.* Якщо збільшуючий ланцюг існує, потік не максимальний (його можна
> збільшити на $\Delta>0$). Навпаки, якщо ланцюга немає, візьмімо за $S$ множину всіх
> вершин, досяжних із $s$ у залишковій мережі; тоді $t\notin S$, усі прямі дуги з $S$ у
> $T=V\setminus S$ **насичені**, а всі зворотні — **порожні**, тому $|f|=c(S,T)$. За
> Твердженням 8.6 більший потік неможливий, тож $f$ максимальний, а розріз $(S,T)$ —
> мінімальний. $\blacksquare$

### Покроковий приклад

Розгляньмо мережу з чотирма вершинами $s,u,v,t$ і п'ятьма дугами однакової пропускної
здатності $3$: $s\to u$, $s\to v$, $u\to v$, $u\to t$, $v\to t$. Позначаємо стан дуги як
«потік/пропускна здатність».

**Ітерація 1.** Нехай алгоритм спершу знайшов ланцюг $s\to u\to v\to t$ — усі три дуги
прямі й не насичені, залишок кожної $3$. Пропускна здатність ланцюга $\Delta=\min(3,3,3)=3$.
Пускаємо $3$ одиниці: тепер $s\to u$, $u\to v$, $v\to t$ насичені ($3/3$), а $s\to v$ і
$u\to t$ порожні ($0/3$). Величина потоку $|f|=3$.

**Ітерація 2.** Прямого ненасиченого шляху з $s$ у $t$ вже немає: $s\to u$ насичена. Але в
залишковій мережі є ланцюг, що **чергує напрямки**:
$$
s \xrightarrow{\ \text{за напрямком}\ } v \xrightarrow{\ \text{проти напрямку}\ } u \xrightarrow{\ \text{за напрямком}\ } t.
$$
Тут дугу $s\to v$ проходимо за напрямком (вона порожня, залишок $3$); дугу $u\to v$
проходимо **проти напрямку** (вона *не порожня*, $f=3$, тож можна повернути до $3$); дугу
$u\to t$ проходимо за напрямком (порожня, залишок $3$). Пропускна здатність ланцюга
$\Delta=\min(3,3,3)=3$. Збільшуємо потік: $s\to v$ стає $3/3$, потік дуги $u\to v$
**зменшуємо** на $3$ (з $3/3$ до $0/3$), $u\to t$ стає $3/3$. Тепер $|f|=6$.

![Збільшуючий ланцюг s→v→u→t: дуги s–v та u–t пройдено за напрямком, а дугу u–v — проти напрямку (вона не порожня)](img/l08_augment.png)

**Ітерація 3.** Обидві дуги з джерела ($s\to u$, $s\to v$) тепер насичені, тож з $s$ у
залишковій мережі нема куди рушити — збільшуючого ланцюга немає. Алгоритм зупиняється.

Максимальний потік $|f|=6$. Перевіримо теорему: розріз $S=\{s\}$, $T=\{u,v,t\}$ має прямі
дуги $s\to u$ і $s\to v$ пропускною здатністю $3+3=6$. Отже, $|f|=6=c(S,T)$ — потік
максимальний, а цей розріз мінімальний, як і обіцяє Теорема 8.7.

![Максимальний потік величиною 6; штрихова лінія — мінімальний розріз {s} проти {u, v, t} пропускною здатністю 6](img/l08_maxflow.png)

> **Зауваження.** Другу ітерацію можна було б уникнути, якби алгоритм від початку обрав
> «розумні» шляхи $s\to u\to t$ і $s\to v\to t$. Сила залишкової мережі саме в тому, що
> вона **виправляє** невдалий ранній вибір: зворотна (чередуюча) дуга «відкликала» три
> одиниці невдало пущеного потоку $u\to v$ і перенаправила їх правильно. Без зворотних дуг
> алгоритм застряг би на $|f|=3$.

---

## 8.7 Порівняння алгоритмів

Усі чотири алгоритми **жадібні**, але їхні гарантії й ідеальні входи різні.

| Алгоритм | Задача | Жадібний крок | Структура даних | Час |
|:---------|:-------|:--------------|:----------------|:----|
| Дейкстра | найкоротші шляхи з $s$, $w\ge 0$ | фіксувати найближчу, релаксувати ребра | черга з пріоритетом | $O((n+m)\log n)$ |
| Прим | мінімальне остовне дерево | додати найдешевше ребро *межі* дерева | черга з пріоритетом | $O((n+m)\log n)$ |
| Крускал | мінімальне остовне дерево | додати найдешевше *безциклове* ребро | сортування + union–find | $O(m\log n)$ |
| Форд–Фалкерсон | максимальний потік $s\!\to\! t$ | збільшити потік уздовж ланцюга | залишкова мережа | $O(m\,|f|)$ за цілих ПЗ |

Кілька спостережень:

- **Дейкстра й Прим — структурні близнюки.** Обидва в циклі «вилучити найдешевшу вершину,
  тоді релаксувати її ребра», відрізняючись *лише* змістом ключа: відстань від джерела
  (Дейкстра) чи вага найдешевшого ребра в дерево (Прим). Їхні профілі складності однакові.
- **Крускал — інший за природою:** керований ребрами, потребує сортування й union–find;
  вигідний на розріджених графах.
- **Стежте за передумовами.** Дейкстра вимагає невід'ємних ваг (інакше — Беллман–Форд);
  Прим і Крускал вимагають зв'язного графа (інакше будують остовний *ліс*); різні ваги
  роблять МОД єдиним. Форд–Фалкерсон із пошуком найкоротших збільшуючих ланцюгів (варіант
  **Едмондса–Карпа**) працює за $O(n\,m^2)$ незалежно від величини потоку.

---

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

Алгоритми на графах безпосередньо обслуговують задачі фаху:

- **Маршрутизація й навігація.** Дейкстра знаходить найдешевший маршрут у будь-якій
  зваженій мережі: від прокладання оптимального шляху доставки накладу між складами до
  маршрутизації даних у видавничій комп'ютерній мережі (протокол OSPF — це Дейкстра в дії).
- **Найдешевша мережа зв'язків (МОД).** Прим і Крускал дають найдешевший набір ліній, що
  з'єднує всі вузли: прокладання кабелю локальної мережі між цехами друкарні, розведення
  живлення чи пневматики між машинами так, щоб сумарна довжина (вартість) була мінімальною.
- **Логістика й пропускна здатність (потоки).** Транспортну мережу застосовують до
  планування завантаження: джерело — склад паперу, стік — відділ відвантаження, дуги —
  ділянки виробничої лінії з їхньою пропускною здатністю (аркушів за годину); максимальний
  потік показує, скільки продукції реально пропустить лінія, а **мінімальний розріз**
  вказує на «вузьке місце», яке варто розширити.
- **Планування завдань.** Розподіл замовлень на друкарські машини й ділянки природно
  моделюється потоком у мережі «замовлення → машини → зміни».
- **Кластеризація зображень і кольорів.** МОД слугує заготовкою для кластеризації: вилучивши
  найважчі ребра дерева, отримують групи схожих пікселів або кольорів (сегментація,
  побудова палітри).

---

## Підсумок

- **Задача про найкоротші шляхи** з однієї вершини для графа з невід'ємними вагами
  розв'язується **алгоритмом Дейкстри**: багаторазово *фіксувати* найближчу непозначену
  вершину (жадібний вибір) і *релаксувати* її ребра. На нашому графі від $A$ порядок
  фіксації — $A(0), D(5), B(7), F(11), E(14), C(15), G(22)$; відстані правильні за
  **інваріантом зафіксованої відстані** (Теорема 8.1), який суттєво спирається на
  невід'ємність ваг. Час — $O((n+m)\log n)$ з двійковою купою.
- **Мінімальне остовне дерево** керується **властивістю розрізу** (Теорема 8.2): легке
  ребро будь-якого розрізу, узгодженого з поточним набором, — **безпечне**. Різні ваги
  роблять МОД **єдиним** (Наслідок 8.3).
- **Алгоритм Прима** вирощує одне дерево від старту, щоразу додаючи найдешевше ребро межі;
  **алгоритм Крускала** сортує ребра й додає кожне, що *не утворює циклу*, перевіряючи це
  **системою неперетинних множин** (union–find) за амортизований $O(\alpha(n))$. На нашому
  графі обидва дають те саме МОД $\{A\text{–}D, D\text{–}B, B\text{–}F, F\text{–}E,
  B\text{–}C, C\text{–}G\}$ вагою $29$; Крускал пропускає ребро $D\text{–}F\,(6)$ як таке,
  що замикає цикл.
- **Транспортна мережа** — орієнтований граф із джерелом $s$, стоком $t$ і пропускними
  здатностями дуг; **потік** підпорядкований обмеженню пропускної здатності й збереженню,
  а його **величина** обмежена пропускною здатністю будь-якого **розрізу** (Твердження 8.6).
- **Алгоритм Форда–Фалкерсона** нарощує потік уздовж **збільшуючих (чередуючих) ланцюгів**
  у **залишковій мережі** — за напрямком дуги, якщо вона не насичена, і проти напрямку,
  якщо не порожня. За **теоремою про максимальний потік і мінімальний розріз** (Теорема
  8.7) максимальний потік дорівнює мінімальному розрізу; у прикладі $|f|=6=c(\{s\},\cdot)$.

На цьому завершується модуль **теорії графів**. Наступна, [Лекція 9](ODM-L09.md), присвячена
**комбінаториці та теорії ймовірностей** — методам підрахунку й оцінювання випадковості,
корисним, зокрема, для контролю якості друку та вибіркових перевірок тиражу.

## Вправи

Якщо не сказано інакше, користуйтеся робочим графом $G$ (вершини $A$–$G$; ваги з таблиці
у §8.1).

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

1. Проженіть Дейкстру на $G$ із джерела $A$ й **випишіть найкоротші шляхи** (не лише
   відстані) до $F$, до $C$ і до $G$. Яка вершина найдальша від $A$?
2. У трасуванні Дейкстри вершина $B$ спершу дістала мітку $9$, а потім $7$. Яка релаксація
   її покращила і чому пізніше ребро $A\text{–}B$ не змінило $\text{dist}[B]$?
3. Перелічіть ребра МОД графа $G$ і його сумарну вагу. Чому Прим і Крускал тут *зобов'язані*
   дати однаковий набір ребер?
4. У трасуванні Крускала ребро $D\text{–}F\,(6)$ було пропущене. Яке порівняння $\text{Find}$
   спричинило пропуск і який цикл замкнуло б це ребро?
5. Дайте означення насиченої та порожньої дуги. У прикладі §8.6 після першої ітерації
   назвіть усі насичені й усі порожні дуги.

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

6. Проженіть Дейкстру на $G$ із джерела **$G$** (а не $A$). Наведіть таблицю, що
   еволюціонує, і остаточні відстані до всіх вершин.
7. Побудуйте повне трасування Прима на $G$, стартуючи з вершини **$C$** (а не $A$). Чи
   збіглося отримане дерево з деревом зі старту $A$? Поясніть, спираючись на Наслідок 8.3.
8. Сформулюйте **властивість розрізу** й застосуйте її до *першого* кроку Прима зі старту
   $A$: укажіть розріз $(S,V\setminus S)$ і легке ребро, яке додається.
9. Наведіть невеликий *орієнтований* граф із одним від'ємним ребром, на якому Дейкстра дає
   **неправильну** відстань; покажіть її результат і справжню відстань та назвіть алгоритм,
   яким слід скористатися.
10. У мережі §8.6 знайдіть **усі** розрізи $(S,T)$ і їхні пропускні здатності. Який із них
    мінімальний? Звірте з величиною максимального потоку.

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

11. Доведіть **властивість розрізу** (Теорема 8.2) повністю, зокрема твердження, що цикл
    перетинає будь-який розріз парну кількість разів.
12. Доведіть коректність Дейкстри (Теорема 8.1) і вкажіть єдиний крок, який потребує
    невід'ємності ваг. Що зламається за наявності від'ємного ребра?
13. Доведіть, що якщо всі ваги ребер різні, то МОД єдине (Наслідок 8.3). *Підказка:*
    візьміть найлегше ребро в симетричній різниці двох різних МОД і застосуйте обмінний
    аргумент.
14. Змініть у $G$ вагу ребра $B\text{–}C$ з $8$ на $1$. Перерахуйте МОД (ребра й вагу) і
    скажіть, яке ребро залишає дерево та чому.
15. Побудуйте мережу, у якій **єдиний** спосіб досягти максимального потоку — застосувати
    збільшуючий ланцюг зі зворотною дугою; поясніть, чому без зворотних дуг алгоритм застряг
    би, і знайдіть мінімальний розріз.