Теорема Менгера: зв'язність, непересічні шляхи та дуальність max-flow min-cut

3D Simulations

🕸️ Мережі · Теорія графів

📅 Липень 2026⏱ 12 хв🟡 Середній рівень · Останнє оновлення: 9 липня 2026 р.

Теорема Менгера: зв'язність, непересічні шляхи та дуальність max-flow min-cut

Скільки незалежних маршрутів з'єднують два міста на карті, і скільки ланок довелося б розірвати зловмиснику, щоб їх ізолювати? У 1927 році австрійський математик Карл Менгер довів, що відповідь на обидва питання завжди однакова — дуальність, яка через десятиліття виявилася окремим випадком теореми про максимальний потік і мінімальний розріз і сьогодні лежить в основі кожного розрахунку надійності мереж — від магістралей інтернету до електромереж.

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. Вершинна та реберна зв'язність

Візьмемо дві різні вершини s і t у графі G. Набір s-t шляхів називають внутрішньо вершинно-непересічним, якщо жодні два шляхи з цього набору не мають спільних вершин, окрім самих s і t. Аналогічно, набір є реберно-непересічним, якщо жодні два шляхи не мають спільних ребер (при цьому вони можуть проходити через спільні проміжні вершини).

s-t вершинний розріз (роздільник) — це множина вершин, окрім s і t, видалення яких знищує кожен шлях від s до t. s-t реберний розріз аналогічно є множиною ребер, видалення яких роз'єднує s і t. Обидва показники вимірюють одну й ту саму інтуїтивну ідею з різних боків: наскільки "надлишковим" є з'єднання між s і t?

Побутова інтуїція: уявіть s і t як два дата-центри, а граф — як фізичні оптоволоконні лінії. Вершинно-непересічні шляхи відповідають маршрутам, які не мають жодного спільного маршрутизатора; реберно-непересічні шляхи відповідають маршрутам без спільного кабельного сегмента, навіть якщо вони можуть коротко проходити через один і той самий маршрутизатор.

2. Теорема Менгера — вершинна форма

Карл Менгер довів наступну надзвичайну дуальність у своїй роботі 1927 року про теорію кривих — задовго до того, як "теорія графів" стала окремою дисципліною, а потокові мережі були формалізовані:

Теорема Менгера (вершинно-непересічна форма): Нехай G — граф, s і t — дві несуміжні вершини. Максимальна кількість внутрішньо вершинно-непересічних s-t шляхів дорівнює мінімальній кількості вершин (окрім s, t), видалення яких роз'єднує t від s. max #(вершинно-непересічних s-t шляхів) = min |вершинний s-t розріз|

Напрям "≤" простий: будь-який вершинний розріз розміру k повинен перетинати кожен з вершинно-непересічних шляхів (кожен шлях повинен проходити через хоча б одну вершину розрізу, а непересічні шляхи не можуть ділити її), тому не може бути більше k непересічних шляхів, якщо мінімальний розріз має розмір k. Глибока частина теореми — і причина, чому знадобився серйозний доказовий апарат для її встановлення — це напрям "≥": що завжди можна знайти k непересічних шляхів, якщо мінімальний розріз має розмір k. Рівність тут — не збіг, а гарантія теореми для кожного графа.

3. Реберна версія теореми

Теорема Менгера має "близнюка" для ребер, іноді приписуваного спільно Менгеру, а пізніше незалежно виведеного як наслідок теорії максимального потоку:

Теорема Менгера (реберно-непересічна форма): Максимальна кількість реберно-непересічних s-t шляхів дорівнює мінімальній кількості ребер, видалення яких роз'єднує t від s (мінімальний s-t реберний розріз). max #(реберно-непересічних s-t шляхів) = min |реберний s-t розріз|

Це саме те твердження, яке отримують, якщо встановити пропускну здатність кожного ребра рівною 1 у потоковій мережі та застосувати теорему про максимальний потік і мінімальний розріз: максимальний потік = мінімальний розріз, і завдяки одиничним пропускним здатностям та теоремі про цілочисельність максимальний потік розкладається саме на стільки реберно-непересічних шляхів з одиничним потоком.

4. Ідея доведення: зведення до max-flow

Найелегантніше сучасне доведення теореми Менгера проходить через теорему про максимальний потік і мінімальний розріз, відкриту незалежно на три десятиліття пізніше Фордом і Фалкерсоном у 1956 році. Зведення майже дивовижно пряме:

Зведення: реберна теорема Менгера \to Max-Flow 1. Довільно орієнтуємо кожне ребро G (або залишаємо обидва напрями для неорієнтованого графа) і присвоюємо кожному ребру пропускну здатність 1. 2. Призначаємо s джерелом, t — стоком. 3. Обчислюємо максимальний потік f від s до t (наприклад, через Форда-Фалкерсона або Едмондса-Карпа — див. статтю про максимальний потік для деталей). 4. За теоремою про цілочисельність існує максимальний потік, що є 0/1 на кожному ребрі. Розкладаємо цей одиничний потік на |f| реберно-непересічних s-t шляхів, повторно простежуючи шлях із ребер потоку-1 від s до t і видаляючи його. 5. За теоремою max-flow min-cut, |f| = пропускна здатність мінімального розрізу = мінімальна кількість ребер, що розділяють s і t. Отже: max реберно-непересічних шляхів = min реберний розріз. ∎

Вершинно-непересічна версія випливає з тієї ж ідеї після невеликого, але вирішального трюку — розщеплення кожної вершини на два вузли, з'єднані ребром пропускної здатності 1, — про що йдеться далі.

5. Розщеплення вершин: обмеження на вершини

Стандартний max-flow обмежує лише те, скільки потоку може пройти через ребро; він нічого не говорить про кількість шляхів, що можуть проходити через вершину. Класичне вирішення, необхідне для вершинної форми теореми Менгера, — розщеплення вершин:

Конструкція розщеплення вершин Для кожної вершини v, окрім s і t: замінюємо v на дві вершини v_in і v_out, з'єднані єдиним орієнтованим ребром v_in \to v_out з пропускною здатністю 1 (це "пропускна здатність" вершини). Кожне вихідне ребро (u, v) стає (u_out \to v_in), зберігаючи свою вихідну пропускну здатність (1 — для задачі непересічних шляхів). Тепер запускаємо звичайний max-flow з реберними пропускними здатностями від s_out до t_in. Оскільки кожне ребро v_in \to v_out має пропускну здатність 1, через v може пройти щонайбільше одна одиниця потоку — саме моделюючи обмеження, що непересічні шляхи не можуть ділити внутрішню вершину.

Запуск max-flow на цьому перетвореному графі та розкладання отриманого цілочисельного потоку на шляхи дає максимальну кількість внутрішньо вершинно-непересічних s-t шляхів, а відповідний мінімальний розріз у розщепленому графі відповідає точно мінімальному вершинному розрізу у вихідному графі — тому що будь-яке ребро розрізу вигляду v_in → v_out відповідає "видаленню" вершини v.

6. Теорема Уітні та k-зв'язність

Гасслер Уітні узагальнив парний результат Менгера в глобальне твердження про загальну стійкість графа. Граф G є k-вершинно-зв'язним, якщо він має більше ніж k вершин і залишається зв'язним після видалення будь-яких k−1 вершин.

Теорема Уітні: Граф G принаймні з k+1 вершинами є k-вершинно-зв'язним тоді й лише тоді, коли кожна пара вершин s, t у G з'єднана принаймні k внутрішньо вершинно-непересічними шляхами. Еквівалентно (через Менгера): G є k-зв'язним тоді й лише тоді, коли між жодною парою вершин немає вершинного розрізу розміру < k.

Саме це на практиці означає "вершинна зв'язність" κ(G): κ(G) є одночасно (а) розміром найменшого вершинного розрізу в усьому графі, і (б) гарантованою мінімальною кількістю непересічних маршрутів між будь-якою парою вершин. Ідентична дуальність зберігається для реберної зв'язності λ(G), і для довільних графів завжди виконується κ(G) ≤ λ(G) ≤ δ(G) (мінімальний степінь).

Чому це важливо для проєктування: якщо потрібно, щоб мережа дата-центру пережила будь-які 2 одночасні відмови маршрутизаторів, не роз'єднавши жодну пару серверів, граф мережі має бути 3-вершинно-зв'язним — Уітні та Менгер разом кажуть, що це точно еквівалентно гарантії 3 непересічних шляхів між кожною парою серверів, умові, яку можна перевірити алгоритмічно повторними обчисленнями max-flow.

7. Зв'язок із теоремою Кеніга

Теорема Менгера має відомого "родича", обмеженого дводольними графами: теорему Кеніга, яка стверджує, що у дводольному графі розмір максимального паросполучення дорівнює розміру мінімального вершинного покриття. Обидва результати є прикладами більш загального патерну — max-min дуальності, реалізованої через потік у мережі, — і обидва можна вивести з max-flow min-cut, використовуючи по суті ту саму конструкцію джерело/стік, яку застосовують для дводольного паросполучення.

Фактично, вся ця родина (Менгер, Кеніг, теорема Холла про шлюби, теорема Ділворта про покриття ланцюгами) об'єднана під парасолькою дуальності лінійного програмування: кожна з них є цілочисельною програмою, чия лінійна релаксація має цілочисельний оптимум, гарантований повною унімодулярністю матриці обмежень потоку в мережі.

8. Застосування: надійність мереж і стійкість до відмов

Проєктування відмовостійких мереж: провайдери та оператори дата-центрів використовують теорему Менгера, щоб підтвердити, що топологія може пережити k одночасних відмов лінії або маршрутизатора — прямо перетворюючи вимогу надійності на гарантію непересічних шляхів.
Стійкі протоколи маршрутизації: протоколи, що заздалегідь обчислюють кілька непересічних резервних шляхів (наприклад, MPLS fast reroute), спираються на алгоритми, які є прямою реалізацією наведеного вище зведення до max-flow через розщеплення вершин.
Трасування у VLSI та мікросхемах: непересічна маршрутизація дротів на чіпі так, щоб жодні дві мережі не перетинали один і той самий канальний ресурс, — пряме застосування реберної теореми Менгера.
Аналіз соціальних мереж: вершинна зв'язність між двома людьми в соціальному графі вимірює, скільки "незалежних" людей потрібно було б видалити, щоб розірвати їхній зв'язок, — показник структурної стійкості потоку впливу чи інформації.
Біологічні транспортні мережі: судинні та міцелієві мережі часто аналізують на k-зв'язність, щоб зрозуміти їхню стійкість до локальних пошкоджень, використовуючи ті самі алгоритми на основі Менгера.

Алгоритмічна вартість: знаходження вершинної або реберної зв'язності для однієї пари (s, t) коштує одного обчислення max-flow — O(VE) з хорошим алгоритмом. Знаходження глобальної зв'язності κ(G) наївно вимагає запуску цього для всіх O(V²) пар, але класичні результати (Івен, 1975) показують, що достатньо зафіксувати одну вершину й тестувати проти всіх інших, зменшуючи вартість до O(V) обчислень max-flow.