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

Длина пути – количество проходимых ребер (с повторениями). Пользуясь определением пути в графе, можно определить расстояние между вершинами как длину кратчайшего пути. При этом, если в графе не существует пути между вершинами, расстояние принимается равным бесконечности. Для взвешенного графа понятие расстояния обобщается: за длину ребра принимается его (положительный) вес. Введенное таким образом понятие расстояния d(u,v) между вершинами u и v удовлетворяет аксиомам:

А1. d(u,v)≥0, причём d(u,v)=0 тогда и только тогда, когда u = v.

А2. d(u,v)= d(v,u)

А3. d(u,v)+ d(v,w) ≥d(u,w)

Эксцентриситет вершины v – расстояние от v до максимально удаленной от v вершины.

Эксцентриситет графа = диаметр графа – максимальный из всех эксцентриситетов вершин. Соответствующие вершины называются периферийными (диаметральными).

Радиус графа – минимальный из всех эксцентриситетов вершин. Соответствующие вершины называются центрами графа (центральными вершинами). В дереве их 1 или 2.