Главная > Математика > Конечные графы и сети
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

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

Рис. 2.4.

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

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

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

Упражнения

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление