Метрические характеристики графов

Длиной маршрута называется количество ребер в нем (с повторениями). Если маршрут М = v ₀, e ₁, v ₁, e ₂, v ₂ ,..., e_k, v_k, то длина М равна k (обозначается | М | = k).

Расстоянием между вершинами u и v (обозначается d (u, v)) называется длина кратчайшей цепи , а сама кратчайшая цепь называется геодезической.

Однако если не существует цепи , то полагают d(u, v) = +¥.

Свойства расстояния d(u, v):

4. d(u, u) = 0;

5. d(u, v) ³ 0;

6. В неориентированном графе d(u, v) = d(v, u);

7. d(u, v) + d(v, w) ³ d(u, w).

Рассмотрим неориентированный граф G. Для фиксированной вершины v величина называется эксцентриситетом или отклоненностью вершины v. Минимальный из эксцентриситетов вершин графа G называется радиусом графа . Максимальный из всех эксцентриситетов вершин графа G называется диаметром графа .

Диаметр графа равен длине длиннейшей геоде­зической, т.е. длине длиннейшей кратчайшей цепи графа.

Множество вершин, находящихся на одинаковом расстоянии n от вершины v (обозначение D (v, n)), называется ярусом:

.