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

Мощность неориентированного графа — характеристика графа, равная минимальному отношению количества рёбер, удалённых из графа, к числу компонент, полученных в результате такого удаления (уменьшенного на 1). Этот метод позволяет определить зоны высокой концентрации рёбер. Мощность графа сходна с понятием жёсткости графа, которая, однако, определяется через процедуру удаления вершин, а не рёбер.

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

Определения

Мощность ${\displaystyle \sigma (G)}$ неориентированного простого графа ${\displaystyle G=(V,E)}$ может быть определена тремя эквивалентными способами:

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

${\displaystyle \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\}.}

• Согласно двойственности линейного программирования,

${\displaystyle \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) и работает за время ${\displaystyle O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))}$.

Свойства

• Если ${\displaystyle \pi =\{V_{1},\dots ,V_{k}\}}$ является разбиением, максимизирующим отношение и для ${\displaystyle i\in \{1,\dots ,k\}}$ ${\displaystyle G_{i}=G/V_{i}}$ является сужением графа G на множество ${\displaystyle V_{i}}$, то ${\displaystyle \sigma (G_{k})\geqslant \sigma (G)}$.
• Теорема Татта — Нэша — Уильямса: ${\displaystyle \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.