Сила графика

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

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

Определения

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

Позволять $\Pi$ быть набором разделов всех $V$ , и $\partial \pi$ — набор ребер, пересекающих множества разбиения $\pi \in \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}\geq 0{\mbox{ and }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.

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

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