3.04.2. Расстояния на графах

Пусть G – связный граф и U, V – его вершины. Длина кратчайшего (U,V)–маршрута (понятно, что он является простой цепью) называется расстоянием между U и V и обозначается d(U,V). По определению полагают, что d(U,U)=0 для всякой вершины U.

Легко видеть, что отображение d обладает обычными свойствами метрики:

1. d(U,V) ≥ 0, причём d(U,V), только если U=V.

2. D(U,V) = D(V,U).

3. d(U,V)+ D(V,W) ≥ D(U,W) (неравенство треугольника).

Удалённостью (или, по-другому, Эксцентриситетом) вершины V графа G называется наибольшее из расстояний от данной вершины до других вершин графа G:

Радиусом Графа G называется наименьшая из удалённостей его вершин:

Диаметром Графа G называется наибольшая из удалённостей его вершин:

Вершина V графа G, удалённость которой минимальная (и значит, равна радиусу), называется Центром Графа G. Точно так же, вершина, удалённость которой максимальная в графе (и значит, равна диаметру), называется Периферийным центром.

Центр графа не обязательно единственный. Так, например, в полном графе Kn или простом цикле Cn удалённости всех вершин равны, и значит, радиус равен диаметру. Поэтому в этих графах все вершины являются одновременно центрами и периферийными центрами.

Можно показать, что для связного графа G справедливы следующие соотношения:

1. ; 2. D(G) ≤ Rg G.

< Предыдущая		Следующая >