Также однозначно определяет структуру графа.

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

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

(1.13.6)

называется эксцентриситетом вершины . Максимальный из всех эксцентриситетов вершин называется диаметром графа и обозначается , т. е.

. (1.13.7)

Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через :

. (1.13.8)

Вершина называется периферийной, если ее эксцентриситет равен диаметру графа, т. е. . Простая цепь, расстояние между концами которой равно , называется диаметральной цепью.

Вершина называется центральной, если . Множество всех центральных вершин графа называется его центром. Центром может быть единственная вершина графа или несколько вершин (см. рис. 1.15). Здесь , ,

. Таким образом, . Периферийные вершины и , диаметральные цепи: и , центральная вершина .