k -реберно-связный граф

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

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

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

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

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

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

Связанные понятия

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Джордан, Камилла (1869). «Сюр-ле-сборки линий» . Журнал чистой и прикладной математики (на французском языке). 70 (2): 185–190.
^ Чо, Юнг Джин; Чен, Юн; Дин, Ю (2007), «О (со)обхвате связного матроида», Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR 2365057 .
^ Роббинс, HE (1939). «Теорема о графах с применением к задаче управления дорожным движением». Американский математический ежемесячник . 46 (5): 281–283. дои : 10.2307/2303897 . JSTOR 2303897 .
^ Гарольд Н. Габоу . Матроидный подход к поиску связности ребер и упаковке древообразий. Дж. Компьютер. Сист. наук. , 50(2):259–273, 1995.
^ Каргер, Дэвид Р .; Штейн, Клиффорд (1996). «Новый подход к проблеме минимального разреза» (PDF) . Журнал АКМ . 43 (4): 601. дои : 10.1145/234533.234534 .
^ Г-н Гэри и Д.С. Джонсон. Компьютеры и трудноразрешимость: Руководство по теории NP-полноты . Фримен, Сан-Франциско, Калифорния, 1979 год.

[1] Джордан, Камилла (1869). «Сюр-ле-сборки линий» . Журнал чистой и прикладной математики (на французском языке). 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 (5): 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 год.

[1]

[2]

[3]

[4]

[5]

[6]