Войти
Этот график отключается, когда крайний правый узел в серой области слева удаляется 
Этот график отключается при удалении пунктирного края. В математике и информатике, связность является одним из основных понятий теории графов : он запрашивает минимальное количество элементов (узлов или ребер), которые необходимо удалить, чтобы разделить оставшиеся узлы на изолированные подграфы. Это тесно связано с теорией проблем сетевого потока. Связность графа - важная мера его устойчивости как сети.
С вершиной 0 этот граф разъединен. Остальная часть графа связана. В неориентированном графе G две вершины u и v называются связанными, если G содержит путь от u до v. В противном случае они называются отключенными . Если две вершины дополнительно соединены путем длины 1, то есть одним ребром, вершины называются смежным .
A графом называется соединенным, если каждая пара вершины в графе связны. Это означает, что между каждой парой вершин существует путь. Несвязанный неориентированный граф называется несвязным . Следовательно, неориентированный граф G является несвязным, если существуют две вершины в G такие, что ни один путь в G не имеет этих вершин в качестве конечных точек. Связен граф только с одной вершиной. Граф без ребер с двумя или более вершинами не связан.
A ориентированный граф называется слабо связным, если замена всех его направленных ребер неориентированными ребрами дает связный (неориентированный) граф. Он является односторонне связанным или односторонним (также называемым полусвязным ), если он содержит направленный путь от u к v или направленный путь от v к u для каждой пары вершин u, v. Он является сильно связанным или просто сильным, если он содержит направленный путь от u до v и направленный путь от v до u для каждой пары вершин u, v.
A компонент связности - это максимальный связный подграф неориентированного графа. Каждая вершина принадлежит ровно одному компоненту связности, как и каждое ребро. Граф связен тогда и только тогда, когда он имеет ровно одну компоненту связности.
сильные компоненты - это максимальные сильно связные подграфы ориентированного графа.
A vertex cut или разделяющее множество связного графа G - это набор вершин, удаление которых делает G несвязным. связность вершин κ (G) (где G не является полным графом ) - это размер минимального разреза вершины. Граф называется k-связным по вершине или k-связанным, если его связность вершин равна k или больше.
Точнее, любой граф G (полный или неполный) называется k-вершинно-связным, если он содержит не менее k + 1 вершин, но не содержит набора из k - 1 вершин, удаление которых разъединяет график; а κ (G) определяется как наибольшее k такое, что G k-связна. В частности, полный граф с n вершинами, обозначенный K n, вообще не имеет вершинных разрезов, но κ (K n) = n - 1.
A vertex cut для двух вершин 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.
Граф называется максимально связным, если его связность равна его минимальной степени. Граф называется максимально связным по ребрам, если его связность по ребрам равна его минимальной степени.
Граф называется сверхсвязным или сверхсвязным. κ, если каждая минимальная вершина сечения изолирует вершину. Граф называется гиперсвязным или гипер-κ, если удаление каждого минимального разреза вершины создает ровно две компоненты, одна из которых является изолированной вершиной. Граф является полусвязным или полу-гипер-κ, если любая минимальная вершина, разрезанная на разрезе, разделяет граф ровно на две компоненты.
Точнее: связный граф G называется сверхсвязным или сверхсвязным. κ, если все минимальные вершинные разрезы состоят из вершин, смежных с одной вершиной (минимальной степени). Связный граф AG называется супер-реберно-связным или супер-λ, если все минимальные реберные разрезы состоят из ребер, инцидентных некоторой вершине (минимальной степени).
Разрез X графа G называется нетривиальное сечение, если X не содержит окрестности N (u) ни одной вершины u ∉ X. Тогда сверхсвязность κ1 группы G равна:
Нетривиальное сечение ребра и сверхсвязность ребер λ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). Этот факт на самом деле является частным случаем теоремы о максимальном потоке и минимальном разрезе.
Проблема определения, связаны ли две вершины в графе, может быть эффективно решена с использованием алгоритм поиска, например поиск в ширину. В более общем плане легко определить с помощью вычислений, связан ли граф (например, с помощью структуры данных с непересекающимся набором данных ), или подсчитать количество связанных компонентов. Простой алгоритм может быть записан в псевдокоде следующим образом:
По теореме Менгера для любых двух вершин u и v связного графа G числа κ (u, v) и λ (u, v) могут быть эффективно определены с помощью max -поточный алгоритм min-cut. Связность и граничная связность группы G затем могут быть вычислены как минимальные значения κ (u, v) и λ (u, v) соответственно.
В теории сложности вычислений SL представляет собой класс задач лог-пространство, сводимое к проблеме определения того, связаны ли две вершины в графе, что было доказано быть равным L по Омеру Рейнгольду в 2004 году. Следовательно, связность неориентированного графа может быть решена в пространстве O (log n).
Проблема вычисления вероятности того, что случайный граф Бернулли связан, называется сетевой надежностью, а проблема вычисления, связаны ли две заданные вершины, проблемой ST-надежности. Оба они #P - жесткие.
Количество различных связанных помеченных графов с n узлами сведено в таблицу в On- Линейная энциклопедия целочисленных последовательностей как последовательность от A001187, до n = 16. Первые несколько нетривиальных терминов - это
| n | графики |
|---|---|
| 2 | 1 |
| 3 | 4 |
| 4 | 38 |
| 5 | 728 |
| 6 | 26704 |
| 7 | 1866256 |
| 8 | 251548592 |
