2. Разделения

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

Рис. 5.1.

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

Таким образом,

и

Для каждой вершины определим следующие два числа:

и

Числа называются соответственно числом внешнего разделения и числом внутреннего разделения вершины Следует отметить, что является наибольшим числом в строке матрицы полученной в результате умножения каждого столбца матрицы расстояний на является наибольшим числом в столбце матрицы полученной после умножения каждой строки матрицы расстояний на .

Рассмотрим в качестве примера ориентированный граф, изображенный на рис. 5.1, и предположим, что все веса вершин и дуг графа равны единице. Матрица расстояний графа имеет вид

Числа внешних и внутренних разделений приведены в присоединенных к матрице столбце и строке соответственно.

Если наименьшая длина такая, что для вершины

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

Аналогично, если такая наименьшая длина что

то

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