Сила графика

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

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

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

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

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