Мощность графа

Мощность неориентированного графа — характеристика графа, равная минимальному отношению количества рёбер, удалённых из графа, к числу компонент, полученных в результате такого удаления (уменьшенного на 1). Этот метод позволяет определить зоны высокой концентрации рёбер. Мощность графа сходна с понятием жёсткости графа, которая, однако, определяется через процедуру удаления вершин, а не рёбер.

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

Определения

Мощность неориентированного простого графа может быть определена тремя эквивалентными способами:

  • Пусть  — множество всех разбиений множества . Для разбиения обозначим как множество рёбер, соединяющих вершины из разных компонент . Тогда .
  • Пусть  — набор всех остовных деревьев графа . Тогда

Сложность

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

Свойства

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

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.