В математике и информатике , подключение является одним из основных понятий теории графов : он запрашивает для минимального числа элементов (узлы или ребер) , которые должны быть удалены , чтобы отделить остальные узлы в двух или более изолированных подграфы . [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 является:
- κ1 (G) = min {| X | : X - нетривиальное сечение}.
Аналогично определяются нетривиальная обрезка ребер и суперсвязность ребер λ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] Этот факт на самом деле является частным случаем теоремы о максимальном потоке и минимальном разрезе .
Вычислительные аспекты [ править ]
Проблема определения, связаны ли две вершины в графе, может быть эффективно решена с помощью алгоритма поиска , такого как поиск в ширину . В более общем плане легко определить с помощью вычислений, связан ли граф (например, с помощью структуры данных с непересекающимся набором данных ), или подсчитать количество связанных компонентов. Простой алгоритм может быть записан в псевдокоде следующим образом:
- Начнем с любого произвольного узла графа G
- Начните с этого узла, используя поиск в глубину или в ширину, подсчитывая все достигнутые узлы.
- После того, как граф был полностью пройден, если количество подсчитанных узлов равно количеству узлов G , граф соединяется; в противном случае он отключается.
По теореме Менгера для любых двух вершин 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 . Первые несколько нетривиальных терминов:
| п | графики |
|---|---|
| 2 | 1 |
| 3 | 4 |
| 4 | 38 |
| 5 | 728 |
| 6 | 26704 |
| 7 | 1866256 |
| 8 | 251548592 |
Примеры [ править ]
- Связности по вершинам и ребрам несвязного графа равны 0 .
- 1 -связность эквивалентна связности для графов не менее двух вершин.
- Полный граф на п вершинах имеет ребро-соединение , равный п - 1 . Любой другой простой граф с n вершинами имеет строго меньшую связность ребер.
- В дереве локальная связность ребер между каждой парой вершин равна 1 .
Границы подключения [ править ]
- Связность вершин графа меньше или равна его связности ребер. То есть κ ( G ) ≤ λ ( G ) . Оба они меньше или равны минимальной степени графа, поскольку удаление всех соседей вершины минимальной степени отсоединит эту вершину от остальной части графа. [1]
- Для вершины графа-транзитивной из степени д , мы имеем: 2 ( d + 1) / 3 ≤ К ( G ) ≤ Л ( G ) = d . [11]
- Для вершины-транзитивена графа из степени д ≤ 4 , или для любого (неориентированного) минимального графа Кэлей от степени д , или для любого симметричного графа из степени д , оба вид связности равен: κ ( G ) = λ ( G ) = d . [12]
Другие свойства [ править ]
- Связность сохраняется гомоморфизмами графов .
- Если G связна, то ее линейный граф L ( G ) также связен.
- Граф G является 2 -Станок соединенных тогда и только тогда , когда она имеет ориентацию , которая сильно связана.
- Теорема Балинского утверждает, что многогранный граф ( 1 - скелет ) k -мерного выпуклого многогранника является k- вершинно-связным графом. [13] Предыдущая теорема Стейница о том, что любой 3-связный плоский граф является многогранным графом ( теорема Стейница ), дает частичное обратное.
- Согласно теореме Г. А. Дирака , если граф является k -связным при k ≥ 2 , то для каждого набора из k вершин в графе существует цикл, который проходит через все вершины этого множества. [14] [15] Обратное верно, когда k = 2 .
См. Также [ править ]
- Алгебраическая связность
- Константа Чигера (теория графов)
- Динамическое соединение , несвязанная структура данных
- График расширителя
- Сила графика
Ссылки [ править ]
- ^ а б Дистель Р. (2005). «Теория графов, электронное издание» . п. 12.
- ↑ Глава 11: Орграфы: Принцип двойственности орграфов: Определение
- ^ Гросс, Джонатан Л .; Йеллен, Джей (2004). Справочник по теории графов . CRC Press . п. 335 . ISBN 978-1-58488-090-5.
- ^ Лю, Цинхай; Чжан, Чжао (01.03.2010). «Существование и верхняя граница двух типов ограниченного подключения» . Дискретная прикладная математика . 158 (5): 516–521. DOI : 10.1016 / j.dam.2009.10.017 .
- ^ Гросс, Джонатан Л .; Йеллен, Джей (2004). Справочник по теории графов . CRC Press . п. 338 . ISBN 978-1-58488-090-5.
- ^ Балбуэна, Камино; Кармона, Анхелес (2001-10-01). «О связности и сверхсвязности двудольных орграфов и графов». Ars Combinatorica . 61 : 3–22. CiteSeerX 10.1.1.101.1458 .
- ^ Гиббонс, А. (1985). Алгоритмическая теория графов . Издательство Кембриджского университета .
- ^ Nagamochi, H .; Ибараки, Т. (2008). Алгоритмические аспекты связности графов . Издательство Кембриджского университета.
- Перейти ↑ Reingold, Omer (2008). «Ненаправленное соединение в лог-пространстве». Журнал ACM . 55 (4): 1–24. DOI : 10.1145 / 1391289.1391291 . S2CID 207168478 .
- ^ Прован, Дж. Скотт; Болл, Майкл О. (1983). «Сложность подсчета сокращений и вычисления вероятности связности графа». SIAM Journal on Computing . 12 (4): 777–788. DOI : 10.1137 / 0212053 . Руководство по ремонту 0721012 . .
- ^ Годсил, С .; Ройл, Г. (2001). Алгебраическая теория графов . Springer Verlag.
- Перейти ↑ Babai, L. (1996). Группы автоморфизмов, изоморфизм, реконструкция . Технический отчет TR-94-10. Чикагский университет. Архивировано из оригинала на 2010-06-11.Глава 27 Справочника по комбинаторике .
- ^ Balinski, ML (1961). «О графическом строении выпуклых многогранников в n -мерном пространстве» . Тихоокеанский математический журнал . 11 (2): 431–434. DOI : 10.2140 / pjm.1961.11.431 .[ постоянная мертвая ссылка ]
- ^ Дирак, Габриэль Эндрю (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten . 22 (1–2): 61–85. DOI : 10.1002 / mana.19600220107 . Руководство по ремонту 0121311 . .
- ^ Фландрин, Эвелин; Ли, Хао; Марчик, Антони; Возняк, Мариуш (2007). «Обобщение теоремы Дирака о циклах через k вершин в k -связных графах». Дискретная математика . 307 (7–8): 878–884. DOI : 10.1016 / j.disc.2005.11.052 . Руководство по ремонту 2297171 . .
