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

Огляд #

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

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

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

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

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

Ми спираємося на такі поняття з Лекції 7:

• Зважений граф приписує кожному ребру дійсне число $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$ (щоб потім відновити самий шлях).

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

Псевдокод #

Дейкстра(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\}$ з дев’ятьма ребрами:

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

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

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

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

• Крок 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$. Так само відновлюємо найкоротші шляхи до всіх вершин:

Разом усі вказівники $\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).

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

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

Теорема 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$ не перетинає цей розріз.

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

Теорема 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]$ — вагу найдешевшого відомого ребра, що сполучає її з поточним деревом, а черга з пріоритетом видає глобальний мінімум.

Прим(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$.

Розповідь:

• Крок 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$. Дерево завершене.

Ребра МОД: $\{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).

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

Теорема 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$ ребро.

Крускал(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).$$

Ребра МОД: $\{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$.

Після цих операцій виклик $\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)$, у якому $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$.

Псевдокод #

Форд–Фалкерсон(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$.

Ітерація 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.

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

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

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

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

• Дейкстра й Прим — структурні близнюки. Обидва в циклі «вилучити найдешевшу вершину, тоді релаксувати її ребра», відрізняючись лише змістом ключа: відстань від джерела (Дейкстра) чи вага найдешевшого ребра в дерево (Прим). Їхні профілі складності однакові.
• Крускал — інший за природою: керований ребрами, потребує сортування й 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, присвячена комбінаториці та теорії ймовірностей — методам підрахунку й оцінювання випадковості, корисним, зокрема, для контролю якості друку та вибіркових перевірок тиражу.

Вправи #

Якщо не сказано інакше, користуйтеся робочим графом $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. Побудуйте мережу, у якій єдиний спосіб досягти максимального потоку — застосувати збільшуючий ланцюг зі зворотною дугою; поясніть, чому без зворотних дуг алгоритм застряг би, і знайдіть мінімальний розріз.

Lectures/ODM-L08.md · 67.6 KB · updated 2026-08-04 15:46