Мощность графа (Bkpukvm, ijgsg)

Граф с мощностью 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.
В отличие от задачи о разбиении графа, получаемые при вычислении мощности разбиения не обязательно сбалансированы (то есть почти одного размера).