Вершинная связность. Свойства и нахождение

Определение

Пусть дан неориентированный граф $G$ с $n$ вершинами и $m$ рёбрами.

Вершинной связностью $\lambda$ графа $G$ называется наименьшее число вершин, которое нужно удалить, чтобы граф перестал быть связным.

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

Говорят, что множество $S$ вершин разделяет вершины $s$ и $t$ , если при удалении этих вершин из графа вершины $u$ и $v$ оказываются в разных компонентах связности.

Ясно, что вершинная связность графа равна минимуму от наименьшего числа вершин, разделяющих две вершины $s$ и $t$ , взятому среди всевозможных пар $(s,t)$ .

Свойства

Соотношение Уитни

Соотношение Уитни (Whitney) (1932 г.) между рёберной связностью $\lambda$ , вершинной связностью $\kappa$ и наименьшей из степеней вершин $\delta$ :

$\kappa \le \lambda \le \delta.$

Докажем это утверждение.

Докажем сначала первое неравенство: $\kappa \le \lambda$ . Рассмотрим этот набор из $\lambda$ рёбер, делающих граф несвязным. Если мы возьмём от каждого из этих ребёр по одному концу (любому из двух) и удалим из графа, то тем самым с помощью $\le \lambda$ удалённых вершин (поскольку одна и та же вершина могла встретиться дважды) мы сделаем граф несвязным. Таким образом, $\kappa \le \lambda$ .

Докажем второе неравенство: $\lambda \le \delta$ . Рассмотрим вершину минимальной степени, тогда мы можем удалить все $\delta$ смежных с ней рёбер и тем самым отделить эту вершину от всего остального графа. Следовательно, $\lambda \le \delta$ .

Интересно, что неравенство Уитни нельзя улучшить: т.е. для любых троек чисел, удовлетворяющих этому неравенству, существует хотя бы один соответствующий граф. См. задачу "Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин".

Нахождение вершинной связности

Переберём пару вершин $s$ и $t$ , и найдём минимальное количество вершин, которое надо удалить, чтобы разделить $s$ и $t$ .

Для этого раздвоим каждую вершину: т.е. у каждой вершины $i$ создадим по две копии — одна $i_1$ для входящих рёбер, другая $i_2$ — для выходящих, и эти две копии связаны друг с другом ребром $(i_1, i_2)$ .

Каждое ребро $(u,v)$ исходного графа в этой модифицированной сети превратится в два ребра: $(u_2, v_1)$ и $(v_2, u_1)$ .

Всем рёбрам проставим пропускную способность, равную единице. Найдём теперь максимальный поток в этом графе между истоком $s$ и стоком $t$ . По построению графа, он и будет являться минимальным количеством вершин, необходимых для разделения $s$ и $t$ .

Таким образом, если для поиска максимального потока мы выберем алгоритм Эдмондса-Карпа, работающий за время $O (n m^2)$ , то общая асимптотика алгоритма составит $O (n^3 m^2)$ . Впрочем, константа, скрытая в асимптотике, весьма мала: поскольку сделать граф, на котором алгоритмы бы работали долго при любой паре исток-сток, практически невозможно.