Сила графика

Теоретико-графовый параметр связности

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

Определения

Сила неориентированного простого графа G  = ( V ,  E ) допускает три следующих определения: ${\displaystyle \sigma (G)}$

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

${\displaystyle \sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T}}\ \lambda _{T}\geq 0{\mbox{ and }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.}$

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

${\displaystyle \sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geq 0{\mbox{ and }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.}$

Сложность

Вычисление прочности графа можно выполнить за полиномиальное время, и первый такой алгоритм был открыт Каннингемом (1985). Алгоритм с наибольшей сложностью для точного расчета силы принадлежит Трубину (1993) и использует разложение потока Голдберга и Рао (1998) по времени . ${\displaystyle O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))}$

Характеристики

• Если есть одно разбиение, которое максимизирует, и для является ограничением G на множество , то . ${\displaystyle \pi =\{V_{1},\dots ,V_{k}\}}$ ${\displaystyle i\in \{1,\dots ,k\}}$ ${\displaystyle G_{i}=G/V_{i}}$ ${\displaystyle V_{i}}$ ${\displaystyle \sigma (G_{k})\geq \sigma (G)}$
• Теорема Тутта-Нэша-Вильямса: максимальное количество непересекающихся по ребрам остовных деревьев, которые могут содержаться в G . ${\displaystyle \lfloor \sigma (G)\rfloor }$
• В отличие от проблемы разбиения графа , разбиения, полученные в результате вычисления силы, не обязательно сбалансированы (т.е. имеют почти одинаковый размер).

Рекомендации

• WH Каннингем. Оптимальная атака и усиление сети, журнал ACM, 32:549–561, 1985.
• А. Шрийвер . Глава 51. Комбинаторная оптимизация, Springer, 2003.
• В.А. Трубин. Сила графа и упаковка деревьев и ветвей, Кибернетика и системный анализ, 29:379–384, 1993.