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)}$

Связанная с этим проблема: нахождение минимального охватывающего подграфа G с k -связными ребрами (то есть: выберите в 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. Роббинс, HE (1939). «Теорема о графах с применением к задаче управления дорожным движением». Американский математический ежемесячник . 46 : 281–283. дои : 10.2307/2303897. JSTOR  2303897.
4. Гарольд Н. Габоу . Матроидный подход к поиску связности ребер и упаковке древообразий. Дж. Компьютер. Сист. наук. , 50(2):259–273, 1995.
5. Каргер, Дэвид Р .; Штейн, Клиффорд (1996). «Новый подход к проблеме минимального разреза» (PDF) . Журнал АКМ . 43 (4): 601. дои : 10.1145/234533.234534.
6. Г-н Гэри и Д.С. Джонсон. Компьютеры и трудноразрешимость: Руководство по теории NP-полноты . Фримен, Сан-Франциско, Калифорния, 1979 год.