Пример 2.4. На рис. 2.9 изображен граф с одной точкой сочленения (вершина v).

На рис. 2.9 изображен граф с одной точкой сочленения (вершина v).

Расстояния в графе

Пусть G – связный граф, v и w – любые две его вершины. Тогда существует соединяющая их простая цепь: M = v, e₁ ,…, e_i ,…, e_k , w. Если количество k ребер этой цепи не минимальное из возможных, то существует простая цепь M¢ = v, e¢₁ ,…, e¢_i ,…, e¢_s , w с меньшим числом ребер (s < k), соединяющая вершины v,w. Если и в M¢ количество ребер не минимально, можно найти соединяющую v и w простую цепь с еще меньшим количеством ребер и т.д. Однако процесс уменьшения числа ребер можно повторить не более k раз, так как это число каждый раз уменьшается не меньше чем на единицу. Поэтому существует соединяющая v и w простая цепь M * = v, e * ₁ ,…, e * _i ,…, e * _d , w с минимальным количеством ребер d.

Минимальная длина из возможных длин простых цепей с началом v и концом w называется расстояниемd (v, w) между этими вершинами.

Понятие расстояния часто распространяют и на несвязные графы. При этом если вершины v и w несвязанны, то полагают: d (v, w)= ¥.

Утверждение 2.5. Введенное понятие расстояния между двумя вершинами связного графа удовлетворяет аксиомам метрики:

1) d (v, w) ³ 0, причем d (v, w) = 0 тогда и только тогда, когда v = w;

2) d (v, w) = d (w, v) ;

3) d (v, u) + d (u, w) ³ d (v, w) (справедливо неравенство треугольника);

4) d (v, w) < ¥.

Дата добавления: 2015-07-20