граф с k-связностью ребер

Граф, который остается связным, если удалить менее k ребер

В теории графов связный граф называется k -рёберно связным , если он остаётся связным при удалении менее k рёбер.

Реберная связность графа — это наибольшее значение k , при котором граф является k -реберно связным.

Связность ребер и перечисление k -связных графов изучались Камиллом Жорданом в 1869 году. ^[1]

Формальное определение

Граф с 2 рёбрами связи

Пусть будет произвольным графом. Если подграф связен для всех , где , то говорят, что G имеет k -рёберную связность. Реберная связность — это максимальное значение k, при котором G имеет k -рёберную связность. Наименьшее множество X , удаление которого разъединяет G, является минимальным разрезом в G . ${\displaystyle G=(V,E)}$ ${\displaystyle G'=(V,E\setminus X)}$ ${\displaystyle X\subseteq E}$ ${\displaystyle |X|<k}$ ${\displaystyle G}$

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

Связанные концепции

Минимальная степень вершины дает тривиальную верхнюю границу реберной связности. То есть, если граф k -реберно связен , то необходимо, чтобы k  ≤ δ( G ), где δ( G ) - минимальная степень любой вершины v  ∈  V . Удаление всех ребер, инцидентных вершине v, отключит v от графа. ${\displaystyle G=(V,E)}$

Связность ребер является двойственной концепцией к обхвату , длине кратчайшего цикла в графе, в том смысле, что обхват планарного графа является связностью ребер его двойственного графа , и наоборот. Эти концепции объединены в теории матроидов обхватом матроида , размером наименьшего зависимого множества в матроиде. Для графического матроида обхват матроида равен обхвату базового графа, тогда как для ко-графического матроида он равен связности ребер. ^[2]

Графы с 2-связными рёбрами также могут быть охарактеризованы отсутствием мостов , существованием разложения на уши или теоремой Роббинса , согласно которой именно эти графы имеют сильную ориентацию . ^[3]

Вычислительные аспекты

Существует полиномиальный алгоритм для определения наибольшего k, для которого граф G является k -связным по ребрам. Простой алгоритм для каждой пары (u,v) определил бы максимальный поток из u в v с пропускной способностью всех ребер в G, установленной в 1 для обоих направлений. Граф является k -связным по ребрам тогда и только тогда, когда максимальный поток из u в v составляет по крайней мере k для любой пары (u,v) , поэтому k является наименьшим uv -потоком среди всех (u,v) .

Если n — число вершин в графе, этот простой алгоритм будет выполнять итерации задачи максимального потока, которая может быть решена за время. Следовательно, сложность простого алгоритма, описанного выше, составляет всего. ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{5})}$

Улучшенный алгоритм решит задачу максимального потока для каждой пары (u,v) , где u произвольно фиксировано, а v меняется по всем вершинам. Это снижает сложность до и является обоснованным, поскольку, если существует разрез с емкостью меньше k , он обязательно отделит u от некоторой другой вершины. Его можно дополнительно улучшить с помощью алгоритма Габова , который работает в худшем случае . ^[4] ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{3})}$

Вариант алгоритма Каргера–Штейна обеспечивает более быстрый рандомизированный алгоритм определения связности с ожидаемым временем выполнения . ^[5] ${\displaystyle O(n^{2}\log ^{3}n)}$

Связанная задача: нахождение минимального k -связного остовного подграфа графа G (то есть выбор как можно меньшего количества ребер в G , которые являются k -связными) является NP-трудной для . ^[6] ${\displaystyle k\geq 2}$

Смотрите также

• граф с связностью k вершин
• Связность (теория графов)
• Соответствующее исключение

Ссылки

1. Джордан, Камилла (1869). «Сюр-ле-сборки линий». Journal für die reine und angewandte Mathematik (на французском языке). 70 (2): 185–190.
2. Чо, Юнг Джин; Чэнь, Йонг; Дин, Юй (2007), «О (со)обхвате связного матроида», Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR  2365057.
3. Роббинс, Х. Э. (1939). «Теорема о графах с приложением к проблеме управления движением». American Mathematical Monthly . 46 (5): 281–283. doi :10.2307/2303897. JSTOR  2303897.
4. Гарольд Н. Габов . Матроидный подход к поиску связности ребер и упаковке древовидных структур. J. Comput. Syst. Sci. , 50(2):259–273, 1995.
5. Каргер, Дэвид Р.; Стайн , Клиффорд (1996). "Новый подход к проблеме минимального разреза" (PDF) . Журнал ACM . 43 (4): 601. doi :10.1145/234533.234534.
6. М. Р. Гэри и Д. С. Джонсон. Компьютеры и неразрешимость: руководство по теории NP-полноты . Freeman, Сан-Франциско, Калифорния, 1979.