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

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

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

Определения

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

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

$\sigma (G)=\max \{\sum _{T\in 𝒯}{\lambda }_T:\mathrm{\forall }T\in 𝒯{\lambda }_T⩾0;\mathrm{\forall }e\in E\sum _{T\ni e}{\lambda }_T⩽1\}.$

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

$\sigma (G)=\min \{\sum _{e\in E}{y}_e:\mathrm{\forall }e\in E{y}_e⩾0;\mathrm{\forall }T\in 𝒯\sum _{e\in E}{y}_e⩾1\}.$

Сложность

Вычисление мощности графа может быть осуществлено за полиномиальное время. Первый полиномиальный алгоритм обнаружил Каннингем (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)⩾\sigma (G)$.
• Теорема Татта — Нэша — Уильямса: $\lfloor \sigma (G)\rfloor$ является максимальным числом не пересекающихся по рёбрам остовных деревьев, которые могут содержаться в G.
• В отличие от задачи о разбиении графа, получаемые при вычислении мощности разбиения не обязательно сбалансированы (то есть почти одного размера).

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья