Потужність графа

Граф із потужністю 2. На зображенні показано спосіб видалення ребер, що максимізує описуване відношення: граф розбивається на три частини, при цьому видаляється 4 ребра між цими частинами, що дає відношення 4/(3-1)=2.

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

Визначення

Потужність $\sigma (G)$ неорієнтованого простого графа $G=(V,E)$ можна визначити трьома еквівалентними способами:

• Нехай $\Pi$ — множина всіх розбиттів множини $V$. Для розбиття $\pi \in \Pi$ позначимо як $\partial \pi$ множину ребер, що з'єднують вершини з різних компонент $\pi$. Тоді $\displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1}}$.
• Нехай ${\mathcal {T}}$ — набір усіх кістякових дерев графа $G$. Тоді

$\sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T}}\ \lambda _{T}\geqslant 0;\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leqslant 1\right\}.$

• Відповідно до двоїстості лінійного програмування,

$\sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geqslant 0;\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geqslant 1\right\}.$

Складність

Потужність графа можна обчислити за поліноміальний час. Перший поліноміальний алгоритм виявив Каннінгем (1985). Алгоритм для обчислення потужності з найкращою складністю, який належить Трубіну (1993), використовує розклад потоку Голдберга та Рао (1998) і працює за час $O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))$.

Властивості

• Якщо $\pi =\{V_{1},\dots ,V_{k}\}$ — розбиття, яке максимізує відношення і для $i\in \{1,\dots ,k\}$$G_{i}=G/V_{i}$ є звуженням графа $G$ на множину $V_{i}$, то $\sigma (G_{k})\geqslant \sigma (G)$.
• Теорема Татта — Неша — Вільямса: $\lfloor \sigma (G)\rfloor$ є найбільшим числом кістякових дерев, що не перетинаються по ребрах, які можуть міститися в $G$.
• На відміну від задачі про розбиття графа, одержувані при обчисленні потужності розбиття не обов'язково збалансовані (тобто майже одного розміру).

Література

• Cunningham W. H. Optimal attack and reinforcement of a network // J of ACM. — 1985. — Вип. 32. — С. 549—561.
• Alexander Schrijver. Chapter 51 // Combinatorial Optimization. Polyhedra and Efficiency. — Springer, 2003. — ISBN 978-3-540-44389-6.
• Trubin V. A. Strength of a graph and packing of trees and branchings // Cybernetics and Systems Analysis. — 1993. — Вип. 29. — С. 379—384.