Файл:Force-wiki.jpgГраф с мощностью 2. На изображении показан максимизирующий рассматриваемое отношение способ удаления рёбер: граф разбивается на три части, при этом удаляется 4 рёбра между этими частями, что даёт отношение 4/(3-1)=2.
Мощностьнеориентированного графа — характеристика графа, равная минимальному отношению количества рёбер, удалённых из графа, к числу компонент, полученных в результате такого удаления (уменьшенного на 1). Этот метод позволяет определить зоны высокой концентрации рёбер. Мощность графа сходна с понятием жёсткости графа, которая, однако, определяется через процедуру удаления вершин, а не рёбер.
Мощность <math>\sigma(G)</math> неориентированного простого графа <math>G=(V,E)</math> может быть определена тремя эквивалентными способами:
Пусть <math>\Pi</math> — множество всех разбиений множества <math>V</math>. Для разбиения <math>\pi\in\Pi</math> обозначим как <math>\partial \pi</math> множество рёбер, соединяющих вершины из разных компонент <math>\pi</math>. Тогда <math>\displaystyle\sigma(G)=\min_{\pi\in\Pi}\frac{|\partial \pi|}{|\pi|-1}</math>.
Пусть <math> \mathcal T</math> — набор всех остовных деревьев графа <math>G</math>. Тогда
Вычисление мощности графа может быть осуществлено за полиномиальное время. Первый полиномиальный алгоритм обнаружил Каннингем (1985). Алгоритм для вычисления мощности с наилучшей сложностью, принадлежащий Трубину (1993), использует разложение потока Голдберга и Рао (1998) и работает за время <math>O(\min(\sqrt{m},n^ {2/3})mn\log(n^2/m+2))</math>.
Свойства
Если <math>\pi=\{V_1,\dots,V_k\}</math> является разбиением, максимизирующим отношение и для <math> i\in\{1,\dots,k\}</math> <math>G_i=G/V_i</math> является сужением графа G на множество <math>V_i</math>, то <math>\sigma(G_k)\geqslant \sigma(G)</math>.
Теорема Татта — Нэша — Уильямса: <math>\lfloor\sigma(G)\rfloor</math> является максимальным числом не пересекающихся по рёбрам остовных деревьев, которые могут содержаться в G.
В отличие от задачи о разбиении графа, получаемые при вычислении мощности разбиения не обязательно сбалансированы (то есть почти одного размера).
