WikiDer > Сила графика

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

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

Определения

В сила неориентированного простой график грамм = (VE) допускает три следующих определения:

  • Позволять быть набором всех перегородки из , и - множество ребер, пересекающих множества разбиения , тогда .
  • Также если - это множество всех остовных деревьев грамм, тогда
  • И по двойственности линейного программирования

Сложность

Вычислить силу графа можно за полиномиальное время, и первый такой алгоритм был открыт Каннингемом (1985). Алгоритм с наилучшей сложностью для точного вычисления силы разработан Трубином (1993), использует разложение потока Голдберга и Рао (1998), во времени .

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

  • Если один раздел, который максимизирует, а для , это ограничение грамм к набору , тогда .
  • Теорема Тутте-Нэша-Вильямса: - максимальное количество непересекающихся остовных деревьев, которые могут содержаться в грамм.
  • В отличие от раздел графа проблема, выходные разделы путем вычисления силы не обязательно сбалансированы (то есть почти одинакового размера).

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