k- реберный граф

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

Края связность графы является самым большим к , для которого граф к -Станкам-подключено.

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

Формальное определение [ править ]

2-реберный граф

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

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

Понятия, связанные с данным [ править ]

Минимальная степень вершины дает тривиальную верхнюю оценку связности ребер. То есть, если граф является к -Станкам-подключено , то необходимо , чтобы к &  le ; & delta ; ( G ), где & delta ; ( G ) является минимальной степенью любой вершины об  ∈  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 О (п ^ {2})}$${\ Displaystyle О (п ^ {3})}$${\ Displaystyle О (п ^ {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-вершинно-связный граф
• Связность (теория графов)
• Соответствие преклюзии

Ссылки [ править ]