Деревья и разрезы

Сильная связность

Ориентированный граф называется сильно связным, если для каждой пары вершин v и w существует путь из v в w и из w в v. Очевидно, что сильная связность ориентированного графа означает связность соответствующего неориентированного графа. Обратное, вообще говоря, неверно. На рис. 6.3, граф D ₁ является сильно связным графом, а граф D ₂ не является таковым.

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

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

При использовании терминов «дерево», «лес», «разделяющее множество», «разрез» и «простой разрез» без специальной оговорки считается, что направления дуг не учитываются, и рассматривается соответствующий неориентированный граф. Однако, при учете направления дуг, возникает несколько дополнительных понятий.

Oриентированный граф является ориентированным деревом, растущим от корня v ₀, если:

(1) он образует дерево в неориентированном смысле и

(2) единственная цепь между v ₀ и любой другой вершиной w является путем из v ₀ к w.

Очевидно, что дерево может иметь самое большее один корень и что, вообще говоря, деревья в ориентированном графе могут быть неориентированными. На рис. 6.4, а, например, нельзя найти ориентированное дерево, покрывающее граф. С другой стороны, на рис. 6.5, b утолщенные дуги показывают ориентированное дерево с корнем в вершине v ₀, покрывающее изображенный ориентированный граф.

Напомним, что разрез и, в частности, простой разрез является множеством ребер, соединяющих W и W¢, где { W, W¢ } является разбиением вершин связного графа на два непересекающихся непустых множества. Удаление разреза разделяет граф точно на две компоненты.

В ориентированном графе дуги разреза могут быть разделены на два множества: дуги, направленные из W к W¢, и дуги, направленные из W¢ к W. Удаление первого множества разрывает все пути из W к W¢, в то время как удаление последнего разрывает все пути из W¢ к W. Назовем первое множество разрезом W ® W¢, а второе – разрезом W¢ ® W. На рис. 2.6, b и с представлены эти множества для разреза, изображенного на рис. 2.6, а. Заметим, что если D сильно связен, то оба ориентированных разреза для любого разбиения { W, W¢ } всегда будут непустыми.