Связность (теория графов)

Этот график становится несвязным, если удалить пунктирное ребро.

В математике и информатике связность является одним из основных понятий теории графов : она требует минимального количества элементов (узлов или ребер), которые необходимо удалить, чтобы разделить оставшиеся узлы на два или более изолированных подграфа . ^[1] Она тесно связана с теорией проблем сетевых потоков . Связность графа является важной мерой его устойчивости как сети.

Связанные вершины и графы

С вершиной 0 этот граф несвязен. Остальная часть графа связна.

В неориентированном графе $G$ две вершины $u$ и $v$ называются связанными , если $G$ содержит путь от $u$ до $v$ . В противном случае они называются несвязными . Если две вершины дополнительно соединены путем длины $1$ (то есть являются конечными точками одного ребра), вершины называются смежными .

Граф называется связным, если каждая пара вершин в графе связна. Это означает, что между каждой парой вершин существует путь . Неориентированный граф, который не связен, называется несвязным . Неориентированный граф $G$ поэтому несвязен, если существуют две вершины в $G$ такие, что ни один путь в $G$ не имеет эти вершины в качестве конечных точек. Граф с одной вершиной связен. Граф без ребер с двумя или более вершинами несвязен.

Ориентированный граф называется слабосвязным, если замена всех его ориентированных ребер неориентированными ребрами дает связный (неориентированный) граф. Он является односторонне связанным или односторонним (также называемым полусвязным ), если он содержит ориентированный путь из $u$ в $v$ или ориентированный путь из $v$ в $u$ для каждой пары вершин $u, v$ . ^[2] Он является сильносвязным , или просто сильным, если он содержит ориентированный путь из $u$ в $v$ и ориентированный путь из $v$ в $u$ для каждой пары вершин $u, v$ .

Компоненты и разрезы

Связный компонент — это максимальный связный подграф неориентированного графа. Каждая вершина принадлежит ровно одному связному компоненту, как и каждое ребро. Граф связен тогда и только тогда, когда он имеет ровно один связный компонент.

Сильные компоненты — это максимальные сильно связанные подграфы ориентированного графа.

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

Точнее, любой граф $G$ (полный или нет) называется $k$ -вершинно-связным , если он содержит не менее $k + 1$ вершины, но не содержит множества из $k - 1$ вершин, удаление которых разрывает граф; и $κ (G)$ определяется как наибольшее $k,$ такое что $G$ является $k$ -связным. В частности, полный граф с $n$ вершинами, обозначаемый $K n$ , вообще не имеет вершинных разрезов, но $κ (K n) = n - 1$ .

Вершинный разрез для двух вершин $u$ и $v$ — это набор вершин, удаление которых из графа разъединяет $u$ и $v$ . Локальная связность $κ (u, v)$ — это размер наименьшего вершинного разреза, разделяющего $u$ и $v$ . Локальная связность симметрична для неориентированных графов; то есть $κ (u, v) = κ (v, u)$ . Более того, за исключением полных графов, $κ (G)$ равно минимуму $κ (u, v)$ по всем несмежным парам вершин $u, v$ .

$2$ -связность также называется двусвязностью , а $3$ -связность также называется трисвязностью . Граф $G$ , который является связным, но не $2$ -связным, иногда называется разделимым .

Аналогичные концепции можно определить для ребер. В простом случае, когда разрезание одного конкретного ребра разъединяет граф, это ребро называется мостом . В более общем смысле разрез ребра графа $G$ — это набор ребер, удаление которых делает граф несвязным. Связность ребер $λ (G)$ — это размер наименьшего разреза ребра, а локальная связность ребер $λ (u, v)$ двух вершин $u, v$ — это размер наименьшего разреза ребра, разъединяющего $u$ от $v$ . Опять же, локальная связность ребер симметрична. Граф называется $k$ -связным по ребрам, если его связность ребер равна $k$ или больше.

Граф называется максимально связным, если его связность равна его минимальной степени . Граф называется максимально реберно связным, если его реберная связность равна его минимальной степени. ^[3]

Супер- и гиперсвязность

Граф называется суперсвязным или супер-κ, если каждый минимальный вершинный разрез изолирует вершину. Граф называется гиперсвязным или гипер-κ, если удаление каждого минимального вершинного разреза создает ровно два компонента, один из которых является изолированной вершиной. Граф называется полугиперсвязным или полугипер-κ, если любой минимальный вершинный разрез разделяет граф ровно на два компонента. ^[4]

Точнее: $G-$ связный граф называется суперсвязным или супер-κ, если все минимальные вершинные разрезы состоят из вершин, смежных с одной вершиной (минимальной степени). $G$ -связный граф называется супер-рёберно-связным или супер-λ, если все минимальные рёберные разрезы состоят из рёбер, инцидентных некоторой вершине (минимальной степени). ^[5]

Сечение $X$ графа $G$ называется нетривиальным, если $X$ не содержит окрестность $N(u)$ любой вершины $u \notin X.$ Тогда сверхсвязность графа $G$ имеет вид $\каппа _{1}$ $\kappa _{1}(G)=\min\{|X|:X{\text{ — нетривиальное сечение}}\}.$

Аналогично определяются нетривиальный реберный разрез и реберная суперсвязность . ^[6] $\лямбда _{1}(G)$

Теорема Менгера

Одним из важнейших фактов о связности графов является теорема Менгера , которая характеризует связность и реберную связность графа с точки зрения числа независимых путей между вершинами.

Если $u$ и $v$ являются вершинами графа $G$ , то набор путей между $u$ и $v$ называется независимым, если никакие два из них не имеют общей вершины (кроме самих $u$ и $v$ ). Аналогично, набор является рёберно-независимым, если никакие два пути в нём не имеют общего ребра. Число взаимно независимых путей между $u$ и $v$ записывается как $κ'(u, v)$ , а число взаимно независимых путей между $u$ и $v$ записывается как $λ'(u, v)$ .

Теорема Менгера утверждает, что для различных вершин u , v , $λ (u, v)$ равно $λ'(u, v)$ , и если u также не является смежным с v , то $κ (u, v)$ равно $κ'(u, v)$ . ^[7]^[8] Этот факт на самом деле является частным случаем теоремы о максимальном потоке и минимальном разрезе .

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

Проблема определения того, связаны ли две вершины в графе, может быть эффективно решена с помощью алгоритма поиска , например поиска в ширину . В более общем случае легко вычислительно определить, связан ли граф (например, с помощью структуры данных непересекающегося множества ), или подсчитать количество связанных компонентов. Простой алгоритм может быть записан в псевдокоде следующим образом:

Начните с любого произвольного узла графа $G.$
Продолжайте работу с этого узла, используя поиск в глубину или в ширину, подсчитывая все достигнутые узлы.
После того, как граф полностью пройден, если число подсчитанных узлов равно числу узлов $G$ , граф считается связным; в противном случае он считается несвязным.

По теореме Менгера , для любых двух вершин $u$ и $v$ в связном графе $G$ числа $κ (u, v)$ и $λ (u, v)$ могут быть эффективно определены с помощью алгоритма max-flow min-cut . Связность и реберная связность графа $G$ затем могут быть вычислены как минимальные значения $κ (u, v)$ и $λ (u, v)$ , соответственно.

В теории вычислительной сложности SL — это класс задач, сводимых к задаче определения, связаны ли две вершины графа, что, как доказал Омер Рейнгольд в 2004 году, равно L. ^[9] Следовательно, неориентированная связность графа может быть решена в пространстве $O(log$ $n$ $)$ .

Проблема вычисления вероятности того, что случайный граф Бернулли связен, называется надежностью сети, а проблема вычисления того, связаны ли две заданные вершины, — проблемой надежности ST. Обе эти задачи являются #P -сложными. ^[10]

Количество связанных графов

Число различных связанных помеченных графов с n узлами приведено в таблице в On-Line Encyclopedia of Integer Sequences как последовательность A001187. Первые несколько нетривиальных членов:

Примеры

Связность вершин и ребер несвязного графа равна $0$ .
$1-$ связность эквивалентна связности для графов, имеющих не менее двух вершин.
Полный граф на n $вершинах$ имеет реберную связность, равную $n - 1.$ Любой другой простой граф на $n$ вершинах имеет строго меньшую реберную связность.
В дереве локальная реберная связность между любыми двумя различными вершинами равна $1$ .

Ограничения на связь

Вершинная связность графа меньше или равна его рёберной связности. То есть $κ (G) \leq λ (G)$ .
Связность ребер для графа с не менее чем 2 вершинами меньше или равна минимальной степени графа, поскольку удаление всех ребер, инцидентных вершине минимальной степени, отключит эту вершину от остальной части графа. ^[1]
Для вершинно-транзитивного графа степени $d$ имеем: $2(d + 1)/3 \leq κ (G) \leq λ (G) = d$ . ^[11]
Для вершинно-транзитивного графа степени $d \leq 4$ или для любого (неориентированного) минимального графа Кэли степени $d$ или для любого симметричного графа степени $d$ оба вида связности равны: $κ (G) = λ (G) = d$ . ^[12]

Другие свойства

Связность сохраняется благодаря гомоморфизмам графов .
Если $G$ связен, то его линейный граф $L (G)$ также связен.
Граф $G$ является $2$ -рёберно связным тогда и только тогда, когда его ориентация сильно связна.
Теорема Балинского утверждает, что политопальный граф ( $1$ - скелет ) $k$ -мерного выпуклого политопа является $k$ -вершинно-связным графом. ^[13] Предыдущая теорема Штейница о том, что любой 3-вершинно-связный плоский граф является политопальным графом ( теорема Штейница ), дает частичное обратное утверждение .
Согласно теореме Г. А. Дирака , если граф является $k$ -связным при $k \geq 2$ , то для любого набора из $k$ вершин в графе существует цикл , который проходит через все вершины в наборе. ^[14]^[15] Обратное утверждение верно при $k = 2$ .

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

Ссылки

^ ab Diestel, R. (2005). «Теория графов, Электронное издание». стр. 12.
↑ Глава 11: Орграфы: Принцип двойственности для орграфов: Определение
^ Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов. CRC Press . стр. 335. ISBN 978-1-58488-090-5.
^ Лю, Цинхай; Чжан, Чжао (2010-03-01). «Существование и верхняя граница для двух типов ограниченной связности». Дискретная прикладная математика . 158 (5): 516–521. doi : 10.1016/j.dam.2009.10.017 .
^ Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов. CRC Press . стр. 338. ISBN 978-1-58488-090-5.
^ Balbuena, Camino; Carmona, Angeles (2001-10-01). «О связности и суперсвязности двудольных орграфов и графов». Ars Combinatorica . 61 : 3–22. CiteSeerX 10.1.1.101.1458 .
^ Гиббонс, А. (1985). Алгоритмическая теория графов . Cambridge University Press .
^ Нагамочи, Х.; Ибараки, Т. (2008). Алгоритмические аспекты связности графов . Издательство Кембриджского университета.
^ Рейнгольд, Омер (2008). «Ненаправленная связность в лог-пространстве». Журнал ACM . 55 (4): 1–24. doi :10.1145/1391289.1391291. S2CID 207168478.
^ Прован, Дж. Скотт; Болл, Майкл О. (1983). «Сложность подсчета разрезов и вычисления вероятности того, что граф связен». SIAM Journal on Computing . 12 (4): 777–788. doi :10.1137/0212053. MR 0721012..
^ Годсил, К .; Ройл, Г. (2001). Алгебраическая теория графов . Springer Verlag.
^ Бабай, Л. (1996). Группы автоморфизмов, изоморфизм, реконструкция. Технический отчет TR-94-10. Чикагский университет. Архивировано из оригинала 2010-06-11.Глава 27 « Справочника по комбинаторике» .
^ Балински, М. Л. (1961). «О структуре графа выпуклых многогранников в n-пространстве». Pacific Journal of Mathematics . 11 (2): 431–434. doi : 10.2140/pjm.1961.11.431 .
^ Дирак, Габриэль Эндрю (1960). «In abstrakten Graphen vorhandene vollständige 4-Grapen und ihre Unterteilungen». Mathematische Nachrichten . 22 (1–2): 61–85. дои : 10.1002/мана.19600220107. МР 0121311..
^ Фландрен, Эвелин; Ли, Хао; Марчик, Антони; Возняк, Мариуш (2007). «Обобщение теоремы Дирака о циклах через k вершин в k-связных графах». Дискретная математика . 307 (7–8): 878–884. doi : 10.1016/j.disc.2005.11.052 . MR 2297171..