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

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

Мощность ${\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.

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (10 марта 2019) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (10 марта 2019) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.