Сила графика

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

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

Определения [ править ]

Силы неориентированного простого графа 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)}$
• Теорема Tutte-Nash-Williams: максимальное число реберно непересекающихся остовных деревьев , которые могут содержаться в G .${\displaystyle \lfloor \sigma (G)\rfloor }$
• В отличие от проблемы разбиения графа, разбиения , получаемые при вычислении силы, не обязательно сбалансированы (т. Е. Почти одинакового размера).

Ссылки [ править ]

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