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