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

Пусть G — связный граф, а u и v — две его несовпадающие вершины. Длина кратчайшего (u, v)-маршрута (он, естественно, является простой цепью) называется расстоянием между вершинами u и v и обозначается через d (u, v). Положим еще d (u, u) =0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

1) d (u, v) >= 0,

2) d (u, v) = 0 тогда и только тогда, когда u = v,

3) d (u, v) = d (v, и),

4) d (u, v) +d (v, w) >= d (u, w)(неравенство треугольника).

Понятие расстояния между вершинами в связном графе позволяет определить k -ю степень графа. Пусть G — связный граф, k — натуральное число. Граф G^k имеет то же множество вершин, что и G; несовпадающие вершины u и v смежны в графе G^k тогда и только тогда, когда для графа G верно неравенство d (u, v) <=k. Очевидно, что если k >= | G| — 1, то G^k — полный граф.

Для фиксированной вершины u величина

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

Вершина v называется периферийной, если e (v) =d (G). Простая цепь длины d (G), расстояние между концами которой равно d (G), называется диаметральной цепью.

Для иллюстрации обратимся к графу на рис. 8.1. Здесь d (1, 2)=1, d (1, 3)=2; e (1)=2; d (G) =2. Все вершины, кроме вершины 2, являются периферийными, (1, 2, 3) — диаметральная цепь.

Утверждение 8.1. Для всякого связного графа G верно неравенство d (G) <=rank G.

> Пусть d (G) = d и

v ₁, v₂,..., v_d+1 (1)

— одна из диаметральных цепей графа G. Рассмотрим матрицу смежности A (G), причем выберем нумерацию вершин так, чтобы вершины (1) имели номера 1, 2,..., d + 1 соответственно. Очевидно, что

— клеточная матрица, в левом верхнем углу которой расположена матрица смежности A порожденного подграфа G (v ₁, v ₂,..., v_{d +1}). Этот подграф является простой цепью, следовательно,

— симметрическая матрица порядка d+1, все элементы которой, за исключением двух ближайших к диагонали полос единиц, равны нулю. Минор порядка d матрицы A, остающийся после устранения первого столбца и последней строки, равен 1. Следовательно, rank A (G) >= rank А >= d. <

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

Очевидно, что радиус графа не больше его диаметра.

Вершина v называется центральной, если e (v) = r (G). Множество всех центральных вершин графа называется его центром. Граф может иметь единственную центральную вершину или несколько центральных вершин. Наконец, центр графа может совпадать с множеством всех вершин. Например, центр простой цепи P_n при четном числе вершин n состоит ровно из двух вершин, а при нечетном — из одной; для цикла же C_n все вершины являются центральными.

Задача нахождения центральных вершин графа постоянно возникает в практической деятельности людей. Пусть, например, граф представляет сеть дорог, т. е. вершины его соответствуют отдельным населенным пунктам, а ребра — дорогам между ними. Требуется оптимально разместить больницы, магазины, пункты обслуживания. В подобных ситуациях критерий оптимальности часто заключается в оптимизации «наихудшего» случая, т. е. в минимизации расстояния от места обслуживания до наиболее удаленного пункта. Следовательно, местами размещения должны быть центральные вершины графа.

Реальные задачи (их называют минимаксными задачами размещения, см. [27]) отличаются от этой идеальной тем, что приходится еще учитывать другие обстоятельства — фактические расстояния между отдельными пунктами, стоимость, время проезда и прочее. Для того чтобы учесть это, используют понятие «взвешенный граф». Пусть G — граф, w: EG -> R⁺ — вещественно-значная функция, ставящая в соответствие каждому ребру e положительное (или неотрицательное) число w (e) — вес ребра e. Пару (G, w)назовем взвешенным графом. Под длиной (или весом)любого подграфа взвешенного графа будем понимать сумму весов его ребер. В остальном все определения сохраняются.