В математике и информатике , подключение является одним из основных понятий теории графов : он запрашивает для минимального числа элементов (узлы или ребер) , которые должны быть удалены , чтобы отделить остальные узлы в двух или более изолированных подграфы . [1] Это тесно связано с теорией задач сетевого потока . Связность графа - важная мера его устойчивости как сети.
В неориентированном графе G две вершины u и v называются связными, если G содержит путь из u в v . В противном случае их называют отключенными . Если две вершины дополнительно соединены путем длины 1 , т. Е. Одним ребром, вершины называются смежными .
Граф называется соединены , если каждая пара вершин в графе соединена. Это означает, что между каждой парой вершин есть путь . Несвязный неориентированный граф называется несвязным . Следовательно, неориентированный граф G является несвязным, если существуют две вершины в G такие, что ни один путь в G не имеет этих вершин в качестве конечных точек. Связан граф только с одной вершиной. Edgeless граф с двумя или более вершинами отсоединен.
Ориентированный граф называется слабо связным , если замена всех его направленных ребер неориентированными ребрами дает связный (неориентированный) граф. Он является односторонне связным или односторонним (также называемым полусвязным ), если он содержит направленный путь от 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 ) определяется как по величине к таким образом, что 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 или больше.
Граф называется максимально связным, если его связность равна минимальной степени. Граф называется максимально рёберно связным, если его рёберная связность равна его минимальной степени. [3]
Граф называется сверхсвязным или супер-κ, если каждая минимальная вершина сечения изолирует вершину. Граф называется гиперсвязным или гипер-κ, если удаление каждого минимального разреза вершины создает ровно две компоненты, одна из которых является изолированной вершиной. Граф является полугиперсвязным или полугипер-κ, если любая минимальная вершина разрезает его ровно на две составляющие. [4]
Более точно: G- связный граф называется суперсвязным или супер-κ, если все минимальные вершинные разрезы состоят из вершин, смежных с одной вершиной (минимальной степени). G связный граф называется супер-края соединены или супер-λ , если все минимальные краевые разрезы состоят из ребер , инцидентных на некотором (минимальной степени) вершине. [5]
Cutset Х из G называется нетривиальной cutset , если Й не содержат окрестности N (U) любой вершину у ∉ х . Тогда superconnectivity κ1 из G является:
Нетривиальные края разрез и кромка-superconnectivity λ1 (G) , определяются аналогично. [6]
Одним из наиболее важных фактов о связности в графах является теорема Менгера , которая характеризует связность и связность ребер графа с точки зрения количества независимых путей между вершинами.
Если 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] Этот факт на самом деле является частным случаем теоремы о максимальном потоке и минимальном разрезе .
Проблема определения, связаны ли две вершины в графе, может быть эффективно решена с помощью алгоритма поиска , такого как поиск в ширину . В более общем плане легко определить с помощью вычислений, связан ли граф (например, с помощью структуры данных с непересекающимся набором данных ), или подсчитать количество связанных компонентов. Простой алгоритм может быть записан в псевдокоде следующим образом:
По теореме Менгера для любых двух вершин u и v связного графа G числа κ ( u , v ) и λ ( u , v ) могут быть эффективно определены с использованием алгоритма min-cut с максимальным потоком . Связность и граничная связность группы G затем могут быть вычислены как минимальные значения κ ( u , v ) и λ ( u , v ) соответственно.
В теории сложности вычислений, SL является класс задач лог-пространства приводимым к задаче определения , связаны ли две вершины в графе, что было доказано , чтобы быть равным L от Omer Рейнгольдом в 2004 году [9] Таким образом, неориентированного графа возможность подключения может быть решена в пространстве O (log n ) .
Проблема вычисления вероятности того, что случайный граф Бернулли связан, называется сетевой надежностью, а проблема вычисления, связаны ли две заданные вершины, проблемой ST-надежности. Оба эти #P -Жесткие. [10]
Количество различных связанных помеченных графов с n узлами табулировано в Он-лайн энциклопедии целочисленных последовательностей как последовательность A001187 . Первые несколько нетривиальных терминов:
п | графики |
---|---|
1 | 1 |
2 | 1 |
3 | 4 |
4 | 38 |
5 | 728 |
6 | 26704 |
7 | 1866256 |
8 | 251548592 |