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

В теории графов говорят, что граф G k-рёберно-связен, если он остаётся связным после удаления не более чем <math>k-1</math> рёбер.

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

Пусть <math>G = (V, E)</math> — любой граф. Если <math>G^\prime = (V, E \setminus X)</math> связен для всех <math>X \subseteq E</math> при <math>|X| < k</math>, то <math>G</math> называется k-рёберно связен. Ясно, что если граф является k-рёберно-связным, то он также и (k−1)-рёберно-связен.

Связь минимальной степенью вершин

Минимальная степень вершин даёт простую верхнюю границу рёберной связности. Таким образом, для того, чтобы граф <math>G = (V,E)</math> являлся k-рёберно-связным, необходимо, чтобы <math>k \le \delta(G) </math>, где <math>\delta(G)</math> — минимальная степень любой вершины <math>v \in V</math>. Очевидно, что удаление всех рёбер, инцидентных вершине v, приведёт к отделению вершины v из графа.

Вычислительная сторона

Существует полиномиальный по времени алгоритм определения наибольшего k, для которого граф G является k-рёберно-связным. В качестве простого алгоритма можно использовать следующий: для любой пары вершин (u, v) определим максимальный поток из u в v с пропускной способностью всех рёбер, равной единице в обоих направлениях. Граф является k-рёберно-связным, тогда и только тогда, когда максимальный поток из u в v не меньше k для любой пары (u, v). Таким образом k является наименьшим u-v-потоком среди всех пар (u, v).

Если n — число вершин в графе, этот простой алгоритм работает за <math>O(n^2)</math> итераций алгоритма максимального потока, который, в свою очередь, решает задачу нахождения потока за время <math>O(n^3)</math>. Таким образом, общая сложность алгоритма равна <math>O(n^5)</math>.

Улучшенный алгоритм решает задачу максимального потока для любой пары (u, v), где u — произвольная фиксированная вершина, а v пробегает все оставшиеся вершины. Этот алгоритм уменьшает сложность до <math>O(n^4)</math>. Если существует разрез размером меньше k, он отделяет u от некоторых других вершин. Можно улучшить алгоритм, если применить алгоритм Габова, работающий за время <math>O(n^3)</math>.

Связанная задача, нахождение минимального k-рёберно-связного подграфа графа G (то есть выбрать насколько можно мало рёбер из G, которые образуют k-рёберно-связный подграф) является NP-трудной для <math>k\geq 2</math>.

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

• k-вершинно-связный граф
• Связный граф
• Препятствущее паросочетанию множество
• Теорема Менгера
• Теорема Роббинса

Отрывок, характеризующий Рёберно k-связный граф

– С отцом и сестрой, не забудь, – тихо сказал князь Андрей.
– Всё равно одна, без моих друзей… И хочет, чтобы я не боялась.
Тон ее уже был ворчливый, губка поднялась, придавая лицу не радостное, а зверское, беличье выраженье. Она замолчала, как будто находя неприличным говорить при Пьере про свою беременность, тогда как в этом и состояла сущность дела.
– Всё таки я не понял, de quoi vous avez peur, [Чего ты боишься,] – медлительно проговорил князь Андрей, не спуская глаз с жены.
Княгиня покраснела и отчаянно взмахнула руками.
– Non, Andre, je dis que vous avez tellement, tellement change… [Нет, Андрей, я говорю: ты так, так переменился…]
– Твой доктор велит тебе раньше ложиться, – сказал князь Андрей. – Ты бы шла спать.
Княгиня ничего не сказала, и вдруг короткая с усиками губка задрожала; князь Андрей, встав и пожав плечами, прошел по комнате.
Пьер удивленно и наивно смотрел через очки то на него, то на княгиню и зашевелился, как будто он тоже хотел встать, но опять раздумывал.
– Что мне за дело, что тут мсье Пьер, – вдруг сказала маленькая княгиня, и хорошенькое лицо ее вдруг распустилось в слезливую гримасу. – Я тебе давно хотела сказать, Andre: за что ты ко мне так переменился? Что я тебе сделала? Ты едешь в армию, ты меня не жалеешь. За что?
– Lise! – только сказал князь Андрей; но в этом слове были и просьба, и угроза, и, главное, уверение в том, что она сама раскается в своих словах; но она торопливо продолжала:
– Ты обращаешься со мной, как с больною или с ребенком. Я всё вижу. Разве ты такой был полгода назад?
– Lise, я прошу вас перестать, – сказал князь Андрей еще выразительнее.
Пьер, всё более и более приходивший в волнение во время этого разговора, встал и подошел к княгине. Он, казалось, не мог переносить вида слез и сам готов был заплакать.
– Успокойтесь, княгиня. Вам это так кажется, потому что я вас уверяю, я сам испытал… отчего… потому что… Нет, извините, чужой тут лишний… Нет, успокойтесь… Прощайте…
Князь Андрей остановил его за руку.
– Нет, постой, Пьер. Княгиня так добра, что не захочет лишить меня удовольствия провести с тобою вечер.
– Нет, он только о себе думает, – проговорила княгиня, не удерживая сердитых слез.
– Lise, – сказал сухо князь Андрей, поднимая тон на ту степень, которая показывает, что терпение истощено.
Вдруг сердитое беличье выражение красивого личика княгини заменилось привлекательным и возбуждающим сострадание выражением страха; она исподлобья взглянула своими прекрасными глазками на мужа, и на лице ее показалось то робкое и признающееся выражение, какое бывает у собаки, быстро, но слабо помахивающей опущенным хвостом.
– Mon Dieu, mon Dieu! [Боже мой, Боже мой!] – проговорила княгиня и, подобрав одною рукой складку платья, подошла к мужу и поцеловала его в лоб.