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

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

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

Вершина 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 и

v1, v2, ..., vd+1 (1)

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

— клеточная матрица, в левом верхнем углу которой расположена матрица смежности A порожденного подграфа G(v1, v2, ..., vd+1). Этот подграф является простой цепью, следовательно,

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

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

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

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

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

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