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

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

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

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

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

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

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

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

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

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

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

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

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

Точнее, любой граф $G$ (полный или неполный ) называется $k$ -вершинно-связным, если он содержит не менее $k +1$ вершин, но не содержит набора из $k - 1$ вершин, удаление которых разрывает граф; и $κ (G)$ определяется как по величине $к$ таким образом, что $G$ является $к$ -связной. В частности, полный граф с $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-$ связность также называется трехсвязностью . Связный, но не $2-$ связный граф $G$ иногда называют сепарабельным .

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

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

Супер- и гипер-подключение

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

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

Cutset $Х$ из $G$ называется нетривиальной cutset , если $Й$ не содержат окрестности $N (U)$ любой вершину $у \notin х$ . Тогда superconnectivity κ1 из G является:

κ1 (G) = min {| X | : X - нетривиальное сечение}.

Аналогично определяются нетривиальная обрезка ребер и суперсвязность ребер λ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)$ . Этот факт на самом деле является частным случаем теоремы о максимальном потоке и минимальном разрезе .

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

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

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

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

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

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

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

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

п	графики
2	1
3	4
4	38
5	728
6	26704
7	1866256
8	251548592

Примеры

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

Границы подключения

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

Прочие свойства

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

Languages

In other projects