Мощность неориентированного графа — характеристика графа, равная минимальному отношению количества рёбер, удалённых из графа, к числу компонент, полученных в результате такого удаления (уменьшенного на 1). Этот метод позволяет определить зоны высокой концентрации рёбер. Мощность графа сходна с понятием жёсткости графа, которая, однако, определяется через процедуру удаления вершин, а не рёбер.
Определения Мощность неориентированного простого графа может быть определена тремя эквивалентными способами:
Пусть — множество всех разбиений множества . Для разбиения обозначим как множество рёбер, соединяющих вершины из разных компонент . Тогда . Пусть — набор всех остовных деревьев графа . Тогда
Согласно двойственности линейного программирования,
Сложность Вычисление мощности графа может быть осуществлено за полиномиальное время. Первый полиномиальный алгоритм обнаружил Каннингем (1985). Алгоритм для вычисления мощности с наилучшей сложностью, принадлежащий Трубину (1993), использует разложение потока Голдберга и Рао (1998) и работает за время .
Свойства Если является разбиением, максимизирующим отношение и для является сужением графа G на множество , то . Теорема Татта — Нэша — Уильямса: является максимальным числом не пересекающихся по рёбрам остовных деревьев, которые могут содержаться в G. В отличие от задачи о разбиении графа, получаемые при вычислении мощности разбиения не обязательно сбалансированы (то есть почти одного размера).
Литература
Категория:Связность графа Категория:Инварианты графов