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

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

В математике и информатике связность — одно из основных понятий теории графов : она требует минимального количества элементов (узлов или ребер), которые необходимо удалить, чтобы разделить оставшиеся узлы на два или более изолированных подграфа . ^[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$ . Локальная связность симметрична для неориентированных графов; то есть $κ (ты, v) знак равно κ (v, ты)$ . Более того, за исключением полных графов, $κ (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] $\lambda _{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)$ могут быть эффективно определены с использованием алгоритма min-cut с максимальным потоком . Связность и связность ребер $G$ затем можно вычислить как минимальные значения $κ (u, v)$ и $λ (u, v)$ соответственно.

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

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

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

Количество различных связных помеченных графов с n узлами указано в электронной энциклопедии целочисленных последовательностей как последовательность A001187. Первые несколько нетривиальных терминов:

Примеры

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

Ограничения на подключение

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

Другие объекты недвижимости

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