Матрица расстояний

Матрица расстояний D(G) – квадратная матрица p*p, где p – количество вершин графа G: ,

Эксцентриситет e(v) вершины v графа G – длина максимальной геодезической, исходящей из вершины v:

.

Диаметр D(G) графа G – максимальный среди всех эксцентриситетов вершин графа G:

.

Радиус R(G) графа G – минимальный среди всех эксцентриситетов вершин графа G:

.

Периферия графа G – множество вершин графа G, у которых эксцентриситет равен диаметру.

Центр графа G – множество всех вершин графа G, у которых эксцентриситетравен радиусу.

Например: Граф G: вес каждого ребра равен 1.

Матрица расстояний D_G

Диаметр G: D(G) =2. Радиус G: R(G) =2.

Периферия графа G= {1, 2, 3, 4, 5, 6}.

Центр графа G = {1, 2, 3, 4, 5, 6}.

Обхват графа G = 3.

Окружение графа G = 6, максимальный простой цикл, который содержит все вершины графа G ( 1, 2, 3, 4, 6, 5, 1 ).