Связанность — Теория графов

Связность графа — это существование пути от любой вершины к любой другой. При этом некоторые графы более связны, чем другие. Например, дерево является минимально связным, потому что удаление любой вершины или ребра из дерева приводит к его разъединению. Обратный пример — это полный граф, потому что он очень хорошо связан.

Раз степень связанности может меняться, значит нам нужен способ ее измерить. Обычно смотрят, сколько вершин или ребер нужно удалить, чтобы разъединить граф.

Граф называется -связным, если для его рассоединения нужно удалить не менее вершин. Связность неполного графа обозначается как — это минимальное число вершин, которые нужно удалить, чтобы граф был разомкнут.

Граф называется -краевым связным, если для его рассоединения требуется удалить не менее ребер. В этом случае связность графа обозначается κак — это минимальное число ребер, которые нужно удалить, чтобы граф был разомкнут.

Связность полного графа — это особый случай. По условию, .

Есть разница между связностью и -связностью:

Вот несколько примеров связности графов:

В примере выше — это обозначение минимальной степени в графе.

Докажем следующую теорему:

В этой теореме , потому что граф разомкнется, если удалить ребра, инцидентных вершине минимальной степени.

Покажем, что :

Может оказаться, что состоит из всех ребер между и :

Рассмотрим множество, которое состоит из всех соседей в и всех соседей в . Если удалить вершины этого множества, то это разъединит граф, так как мы не сможем попасть из в . Поэтому у этого множеств размер не менее .

С другой стороны, ребра между двумя половинами этого множества исходят из , поэтому его размер не больше κ . Значит, мы получаем .

Наглядное доказательство этой теоремы:

Также подграфы могут быть не просто связными, но и двухсвязными. Посмотрим, что получится из этого.

Напомним, что компонента графа — это максимально связный подграф. Если мы заменим «связный» на «двухсвязный», то получим блок — это максимальный двухсвязный подграф графа.

Это подграф, который не содержит разрезанных вершин. Если добавить к нему любые другие вершины, из-за этого появится разрезанная вершина.

Мы можем разбить граф вокруг его разрезанных вершин на блоки:

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

Например, хроматическое число графа — это максимальное из хроматических чисел его блоков. В приведенном выше графе хроматическое число равно трем, так как для блока треугольника требуется три цвета, а для остальных — два.

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

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