Связность (теория графов) - Connectivity (graph theory)
В математике и информатике , подключение является одним из основных понятий теории графов : он запрашивает для минимального числа элементов (узлы или ребер) , которые должны быть удалены , чтобы отделить остальные узлы в двух или более изолированных подграфы . Это тесно связано с теорией задач сетевого потока . Связность графа - важная мера его устойчивости как сети.
Связанные вершины и графы
В неориентированном графе 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) любой вершину у ∉ х . Тогда 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 ) ≤ λ ( G ) . Оба они меньше или равны минимальной степени графа, поскольку удаление всех соседей вершины минимальной степени отсоединит эту вершину от остальной части графа.
- Для вершины графа-транзитивной из степени д , мы имеем: 2 ( d + 1) / 3 ≤ К ( G ) ≤ Л ( G ) = d .
- Для вершины-транзитивена графа из степени д ≤ 4 , или для любого (неориентированного) минимального графа Кэлей от степени д , или для любого симметричного графа из степени д , оба вид связности равен: κ ( G ) = λ ( G ) = d .
Прочие свойства
- Связность сохраняется гомоморфизмами графов .
- Если G связна, то ее линейный граф L ( G ) также связен.
- Граф G является 2 -Станок соединенных тогда и только тогда , когда она имеет ориентацию , которая сильно связана.
- Теорема Балинского утверждает, что многогранный граф ( 1 - скелет ) k -мерного выпуклого многогранника является k- вершинно-связным графом. Предыдущая теорема Стейница о том, что любой 3-связный плоский граф является многогранным графом ( теорема Стейница ), дает частичное обратное.
- Согласно теореме Г. А. Дирака , если граф является k -связным при k ≥ 2 , то для каждого набора из k вершин в графе существует цикл, который проходит через все вершины этого множества. Обратное верно, когда k = 2 .
Смотрите также
- Алгебраическая связность
- Константа Чигера (теория графов)
- Динамическое соединение , несвязанная структура данных
- График расширителя
- Сила графика