Сила графика
Сила графика: пример | |
---|---|
![]() Граф с силой 2: здесь граф разложен на три части с 4 ребрами между частями, что дает соотношение 4/(3-1)=2. | |
Таблица графиков и параметров |
В теории графов сила компонентам , неориентированного графа соответствует минимальному соотношению удаленных ребер к созданным при декомпозиции рассматриваемого графа. Это метод вычисления разбиений множества вершин и обнаружения зон с высокой концентрацией ребер, аналогичный прочности графа , которая определяется аналогично для удаления вершин.
Определения
[ редактировать ]Сила неориентированного простого графа G = ( V , E ) допускает три следующих определения:
- Позволять быть набором разделов всех , и — набор ребер, пересекающих множества разбиения , затем .
- Также, если является множеством всех остовных деревьев G , то
- И благодаря двойственности линейного программирования,
Сложность
[ редактировать ]Вычисление прочности графа можно выполнить за полиномиальное время, и это первый такой алгоритм.был открыт Каннингемом (1985). Алгоритм с наибольшей сложностью для точного расчета силы принадлежит Трубину (1993), использует разложение потока Голдберга и Рао (1998) по времени .
Характеристики
[ редактировать ]- Если это один раздел, который максимизирует, и для , есть ограничение G на множество , затем .
- Теорема Тутта-Нэша-Вильямса: — максимальное количество непересекающихся по ребрам остовных деревьев, которые могут содержаться в G .
- В отличие от проблемы разделения графа , разделения, полученные в результате вычисления силы, не обязательно сбалансированы (т.е. имеют почти одинаковый размер).
Ссылки
[ редактировать ]- WH Каннингем. Оптимальная атака и усиление сети, журнал ACM, 32:549–561, 1985.
- А. Писатель . Глава 51. Комбинаторная оптимизация, Springer, 2003.
- В.А. Трубин. Сила графа и упаковка деревьев и ветвей, Кибернетика и системный анализ, 29:379–384, 1993.