Введение

Основная концепция теории графов

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

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

Соединенный компонент — это максимальный связный подграф неориентированного графа. Каждая вершина принадлежит ровно одному соединенному компоненту, как и каждое ребро. Граф связен тогда и только тогда, когда он имеет ровно один соединенный компонент. Сильные компоненты — это максимальные сильно связанные подграфы ориентированного графа. Разрез вершин или разделяющее множество связного графа G — это множество вершин, удаление которых делает G несвязным. Связность вершин κ(G) (где G не является полным графом) — это размер минимального разреза вершин. Граф называется k-вершинно связным или k-связным, если его вершинная связность равна k или больше. Более точно, любой граф G (полный или нет) называется k-вершинно связным, если он содержит по крайней мере k + 1 вершин, но не содержит множества из k − 1 вершин, удаление которых делает граф несвязным; и κ(G) определяется как наибольшее k, такое что G является k-связным. В частности, полный граф с n вершинами, обозначаемый Kn, не имеет разрезов вершин вообще, но разрез вершин для двух вершин u и v — это набор вершин, удаление которых из графа делает u и v несвязными. Локальная связность κ(u, v) — это размер наименьшего разреза вершин, разделяющего u и v. Локальная связность симметрична для неориентированных графов; то есть, кроме того, за исключением полных графов, κ(G) равно минимуму κ(u, v) по всем несмежным парам вершин u и v. 2-связность также называется бисвязностью, а 3-связность также называется трисвязностью. Граф G, который связен, но не 2-связен, иногда называют разделимым. Аналогичные понятия могут быть определены для ребер. В простом случае, когда удаление одного конкретного ребра делает граф несвязным, это ребро называется мостом. В более общем случае, разрез ребер G — это набор ребер, удаление которых делает граф несвязным. Связность ребер λ(G) — это размер наименьшего разреза ребер, а локальная связность ребер λ(u, v) двух вершин u и v — это размер наименьшего разреза ребер, разделяющего u и v. Опять же, локальная связность ребер симметрична. Граф называется k-реберно связным, если его реберная связность равна k или больше. Граф называется максимально связным, если его связность равна его минимальной степени. Граф называется максимально реберно связным, если его реберная связность равна его минимальной степени.

Супер- и гиперсвязь

Граф называется суперсвязным или супер-κ, если каждый минимальный вершинный разрез изолирует вершину. Граф называется гиперсвязным или гипер-κ, если удаление каждого минимального вершинного разреза создает ровно два компонента, один из которых является изолированной вершиной. Граф называется полугиперсвязным или полугипер-κ, если любой минимальный вершинный разрез разделяет граф ровно на два компонента. Более точно: связный граф G называется суперсвязным или супер-κ, если все минимальные вершинные разрезы состоят из вершин, смежных с одной вершиной (минимальной степени). Связный граф G называется суперреберным связным или супер-λ, если все минимальные реберные разрезы состоят из ребер, инцидентных некоторой вершине (минимальной степени). Разрез X графа G называется нетривиальным разрезом, если X не содержит окрестность N(u) любой вершины u ∉ X. Тогда суперсвязность 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) могут быть эффективно определены с использованием алгоритма поиска максимального потока и минимального разреза. Связность и рёберная связность G могут быть вычислены как минимальные значения κ(u, v) и λ(u, v) соответственно. В теории вычислительной сложности SL – это класс задач, логарифмически сводимых к задаче определения, соединены ли две вершины в графе, что было доказано Омером Рейнгольдом в 2004 году. Следовательно, задача о связности неориентированного графа может быть решена в пространстве O(log n). Задача вычисления вероятности того, что случайный граф Бернулли связен, называется надёжностью сети, а задача определения, соединены ли две заданные вершины, называется задачей надёжности ST. Обе эти задачи являются #P-трудными.

Примеры

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

Ограничения на подключение

Связность вершин графа не превышает его связность по ребрам. То есть, κ(G) ≤ λ(G). Связность по ребрам для графа с не менее чем двумя вершинами не превышает минимальную степень графа, поскольку удаление всех ребер, инцидентных вершине минимальной степени, отсоединит эту вершину от остальной части графа. Для вершинно-транзитивного графа степени d справедливо следующее: для вершинно-транзитивного графа степени d ≤ 4, или для любого (неориентированного) минимального графа Кейли степени d, или для любого симметричного графа степени d, оба вида связности равны: .

Другие свойства

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