Вершинная связность

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

Определение и обозначения

Пусть дан неориентированный граф \( G = (V, E) \), где \( V \) — множество вершин, а \( E \) — множество рёбер. Граф называется связным, если между любой парой его вершин существует путь (последовательность рёбер). Вершинная связность графа \( G \), обозначаемая \( \kappa(G) \) (от лат. connectivity — связность), — это наименьшее число вершин, удаление которых вместе с инцидентными им рёбрами делает граф несвязным или сводит его к единственной вершине.

Формально: \( \kappa(G) = \min\{ |S| : S \subseteq V, \; G - S \; \text{несвязен или тривиален} \} \), где \( G - S \) — граф, полученный удалением из \( G \) всех вершин множества \( S \) и всех инцидентных им рёбер.

Для полного графа \( K_n \) (где каждая пара вершин соединена ребром) удаление любого количества вершин, меньшего \( n-1 \), оставляет граф связным. Для \( K_n \) вершинная связность равна \( n-1 \), поскольку только удаление всех остальных вершин, кроме одной, приводит к тривиальному графу. Для несвязного графа вершинная связность по определению равна 0. Для графа, состоящего из единственной вершины, связность также принимается равной 0.

Соотношение с рёберной связностью и степенью

Вершинная связность тесно связана с двумя другими важными характеристиками графа: рёберной связностью \( \lambda(G) \) (минимальное число рёбер, удаление которых нарушает связность) и минимальной степенью вершины \( \delta(G) \) (наименьшее количество соседей у какой-либо вершины). Для любого связного графа \( G \) выполняется классическое неравенство Уитни (Х. Уитни, 1932):

\[ \kappa(G) \le \lambda(G) \le \delta(G). \]

Это неравенство показывает, что вершинная связность всегда не превосходит рёберную связность, а та, в свою очередь, не превосходит минимальную степень вершины. Например, для цикла \( C_n \) (при \( n \ge 3 \)) вершинная связность \( \kappa = 2 \), рёберная связность \( \lambda = 2 \), минимальная степень \( \delta = 2 \). Для графа-звезды \( K_{1,n-1} \) вершинная связность \( \kappa = 1 \) (удаление центральной вершины разрывает граф), рёберная связность \( \lambda = 1 \), а минимальная степень \( \delta = 1 \) (листовые вершины имеют степень 1).

Существуют графы, для которых все три величины равны (например, полные графы и циклы), а также графы, где разница между \( \kappa \) и \( \delta \) может быть сколь угодно велика. Пример — «граф-гребёнка», состоящий из длинного пути и множества висячих вершин, присоединённых к каждому узлу пути: \( \kappa = 1 \) (удаление одной вершины пути может разорвать граф), но \( \delta = 1 \), при этом рёберная связность также равна 1.

Виды и классификации

По величине вершинной связности

• 0-связный граф (несвязный граф): \( \kappa(G) = 0 \). Граф состоит из двух или более компонент связности.
• 1-связный граф (связный, но не двусвязный): \( \kappa(G) = 1 \). Удаление некоторой единственной вершины (называемой точкой сочленения или шарниром) нарушает связность. Большинство простых деревьев являются 1-связными.
• k-связный граф (k-вершинно-связный): \( \kappa(G) \ge k \). Для удаления такого графа до несвязного состояния требуется не менее \( k \) вершин. Наименьшее \( k \), для которого граф является \( k \)-связным, равно его вершинной связности. Например, 2-связный граф (двусвязный) не имеет точек сочленения; 3-связный граф — минимальное количество вершин, удаление которых может нарушить связность, равно трём.

По структуре

• Двусвязные графы: графы с вершинной связностью не менее 2. Они не содержат точек сочленения. Важный класс — блоки, максимальные двусвязные подграфы.
• Трёхсвязные графы: обладают высокой структурной целостностью. Теорема Стейница (1894) устанавливает, что трёхсвязные планарные графы в точности соответствуют выпуклым многогранникам.

Теоремы и результаты

Теорема Менгера (1927)

Центральная теорема, связывающая вершинную связность с количеством непересекающихся путей. В вершинном варианте: Вершинная связность графа \( G \) равна наибольшему числу \( k \), такому что для любой пары несмежных вершин \( u \) и \( v \) существует \( k \) вершинно-непересекающихся (внутренне непересекающихся) путей, соединяющих \( u \) и \( v \). Это означает, что граф \( k \)-связен тогда и только тогда, когда между любыми двумя его несмежными вершинами есть хотя бы \( k \) путей, не имеющих общих промежуточных вершин.

Теорема Менгера является частным случаем более общей теоремы о максимальном потоке и минимальном разрезе и служит основой для многих алгоритмов проверки связности.

Критерий Уитни

Теорема Уитни (1932) обобщает неравенство \( \kappa \le \lambda \le \delta \). Она утверждает, что граф является \( k \)-связным по вершинам тогда и только тогда, когда он является \( k \)-связным по рёбрам и его минимальная степень не меньше \( k \). Однако на практике это не всегда так — существуют графы, где \( \kappa < \lambda \).

Теорема Дирака (для гамильтоновых графов)

Для 2-связных графов существует связь с наличием гамильтоновых циклов. Теорема Дирака (1952) гласит: если в графе с \( n \ge 3 \) вершинами степень каждой вершины не меньше \( n/2 \), то граф гамильтонов. Однако вершинная связность сама по себе не гарантирует гамильтоновость, хотя 2-связность является необходимым условием для существования гамильтонова цикла.

Вычисление

Определение вершинной связности \( \kappa(G) \) является NP-сложной задачей в общем случае. Однако для большинства практических случаев (графы умеренного размера) используются полиномиальные алгоритмы, основанные на потоковых алгоритмах:

1. Сведение к задаче о максимальном потоке: Для каждой упорядоченной пары несмежных вершин (\( u \), \( v \)) строится вспомогательная сеть, где каждая вершина (кроме \( u \) и \( v \)) заменяется парой вершин, соединённых ребром единичной пропускной способности. Максимальный поток между \( u \) и \( v \) в такой сети равен максимальному числу вершинно-непересекающихся путей между ними. Минимальный из этих потоков по всем парам несмежных вершин равен вершинной связности графа (согласно теореме Менгера).
2. Алгоритм Эдмондса — Карпа или алгоритм Диница применяются для поиска максимального потока за время \( O(V \cdot E^2) \) или \( O(V^2 \cdot E) \).
3. Улучшенные методы: Использование алгоритма Стокмейера — Стоуна или алгоритма, основанного на рандомизированном сокращении (contraction) вершин (алгоритм Кайгера — Стейна для рёберной связности имеет аналоги для вершинной, но сложнее).

На практике для небольших графов (до нескольких тысяч вершин) применяют полный перебор пар вершин с потоковым алгоритмом. Для больших разреженных графов существуют специализированные структуры данных.

Применение

Надёжность сетей

Вершинная связность является прямой мерой отказоустойчивости сети. В компьютерной сети, моделируемой графом, вершины представляют узлы (маршрутизаторы, серверы), а рёбра — каналы связи. Значение \( \kappa \) показывает, какое количество узлов может выйти из строя (или быть выведено из строя злоумышленником) до того, как сеть распадётся на изолированные части. Например, сеть с \( \kappa = 3 \) останется связной при выходе из строя любых двух узлов. Это критически важно для проектирования интернет-магистралей, военных систем связи и распределённых вычислений.

Транспортные и коммуникационные системы

В транспортных сетях (метро, автодороги, авиалинии) узлами являются станции или перекрёстки. Минимальное число узлов, блокирующих движение, равно вершинной связности. Планировщики стремятся обеспечить \( \kappa \ge 2 \), чтобы избежать ситуаций, когда закрытие одной станции парализует всю линию. Для авиасети (граф с хабами) \( \kappa \) может быть низким, что делает уязвимыми центральные аэропорты.

Социальные сети и анализ групп

В анализе социальных сетей вершинная связность используется для оценки сплочённости сообщества. Высокая связность между членами группы означает, что для разрушения группы (прекращения информационного обмена) необходимо удалить много участников. Понятие k-ядра (k-core) в социальных сетях тесно связано с вершинной связностью подграфов.

Криптография и распределённые системы

В системах с распределённым реестром (блокчейн) и протоколах консенсуса (например, алгоритм Византийской отказоустойчивости) вершинная связность сети узлов влияет на способность системы противостоять атакам, направленным на отключение части участников (сивилла-атаки). Обеспечение высокой вершинной связности — одно из требований к безопасной топологии.

Интересные факты

• Графы с максимальной связностью: Полные графы и графы, являющиеся произведениями (\( G \square H \)) полных графов, достигают максимальной вершинной связности, равной минимальной степени вершины. Такие графы называются максимально связными.
• Точки сочленения в деревьях: Любое дерево, имеющее хотя бы одну вершину степени больше 1, содержит точки сочленения. В дереве \( T \) вершинная связность \( \kappa(T) = 1 \).
• Теорема о планарности: Для планарных графов (которые можно изобразить на плоскости без пересечения рёбер) вершинная связность ограничена: любой планарный граф имеет хотя бы одну вершину степени не более 5, поэтому \( \kappa(G) \le 5 \).
• Связь с хроматическим числом: Для любого графа \( G \) вершинная связность не превосходит его хроматического числа \( \chi(G) \) (минимальное количество цветов для вершинной раскраски). Однако это неравенство не является строгим: существуют графы с большой связностью и малым хроматическим числом (например, чётные циклы имеют \( \kappa = 2 \), \( \chi = 2 \)).

См. также

• Рёберная связность
• Двусвязный граф
• Точка сочленения
• Теорема Менгера
• k-ядро графа

Источники

• Дистель Р. Теория графов. — Новосибирск: Издательство Института математики, 2002.
• Оре О. Теория графов. — М.: Наука, 1980.
• Уитни Х. Non-separable and planar graphs. — Transactions of the American Mathematical Society, 1932, 34 (2), 339–362.