Мощность графа

Граф с мощностью 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.