Разделения графа

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

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

и (2.1)

.

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

и (2.2)

.

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

Рассмотрим в качестве примера ориентированный граф, изображенный на рис 2.1.

Рис. 2.1. Ориентированный граф G.

Матрица расстояний графа имеет вид:

с учетом вектора весов вершин получим матрицы и :

=		x1	x2	x3	x4	x5	x6
	x1	0	15	30	18	36	39	39
	x2	18	0	5	8	16	24	24
	x3	24	21	0	6	20	27	27
	x4	18	12	25	0	8	18	25
	x5	14	6	15	12	0	12	15*
	x6	6	24	45	24	40	0	45

=		x1	x2	x3	x4	x5	x6
	x1	0	10	12	18	18	26
	x2	27	0	3	12	12	24
	x3	60	35	0	15	25	45
	x4	18	8	10	0	4	12
	x5	28	8	12	24	0	16
	x6	9	24	27	36	30	0
		60	35	27*	36	30	42

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

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

(т.е.

.

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

,

то

.

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