Сила графика - Strength of a graph

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

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

Определения

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

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

${displaystyle sigma (G) = max left {sum _ {mathcal {T}}} lambda _ {T}: forall Tin {mathcal {T}} lambda _ {T} geq 0 {mbox {and}} forall ein E sum _ {Ti e} lambda _ {T} leq 1ight}.}$

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

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

Сложность

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

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

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

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

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