Расстояние в графах

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

p(x_i, x_j)³0;

р(x_i, x_i ) = 0 тогда и только тогда, когда x_i,=x_j;

p(x_j,x_i,) = p(x_i, x_j) (симметричность):

p(x_i, x_j)£p(x_i, x_k)+p(x_k, x_j) (неравенство треугольника).

Если X={x₁,x₂, …, x_n}, то матрица Р=(p_ij), в которой p_ij=p(x_i,x_j), называется матрицей расстояний. Заметим, что Р^T=Р, т. е. матрица Р симметрична.

Для фиксированной вершины x_i, величина е(x_i)= =max{p(x_i, x_j) | x_jÎ X} называется эксцентриситетом вершины x_i. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее. Если Р – матрица расстояний, то эксцентриситет е(x_i) равен наибольшему из чисел, стоящих в i-й строке.

Максимальный среди всех эксцентриситетов вершин назы­вается диаметром графа G и обозначается через d(G): d(G)=max{e(x_i) | x_i Î X}. Вершина x_i называется периферийной, если e(x_i)=d(G).

Пример. Найдем диаметр графа G, изображенного на рис. 4.21. Матрица расстояний Р имеет вид

отсюда е(1)=3, е(2)=2, е(3)=3, е(4)=2, е(5)=2 и, следовательно, d(G)=3. Вершины 1 и 3 являются периферийными.

Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r(G): r(G) = min{e(x_i) | x_iÎМ}. Вершина x_i называется центральной, если е(x_i)=r(G). Множество всех центральных вершин графа называется его центром.

Примеры.

1. Радиус графа, показанного на рис. 4.21, равен 2, а его центром является множество {2,4,5}.

2. В полном графе К_п все различные вершины смежны, и поэтому d(K_n) = r(К_n) = 1.

Задача нахождения центральных вершин возникает в практической деятельности людей. Пусть, например, граф представляет собой сеть дорог, т. е. вершины соответствуют населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т. п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной тем, что приходится учитывать и другие обстоятельства – расстояния между населенными пунктами, стоимость, время проезда и т. д. Для учета этих параметров используются взвешенные графы [4].

Пусть G = (X,V) –взвешенный граф, в котором вес каждой дуги (x_i,x_j) есть некоторое вещественное число m(x_i,x_j). Весом маршрута x₁, x₂, ... , x_n, x_n+1, называется число . Взвешенным расстоянием ( - расстаянием) p_v(x_i,x_j) между вершинами x_i и x_j называется минимальный из весов (x_i,x_j)-маршрутов. (x_i,x_j)-маршрут, вес которого равен расстоянию p_v(x_i,x_j), называется кратчайшим (x_i,x_j)-маршрутом в взвешенном графе G. Взвешенным эксцентриситетом e_v (x_i) вершины x_i называется число mах{p_v(x_i,x_j) | x_jÎМ}. Взвешенной центральной вершиной графа G называется вершина x_i, для которой е_v(x_i)=min{е_v(x_j) | x_jÎ М}. Взвешенный эксцентриситет центральной вершины называется взвешенным радиусом графа G и обозначается через r_v(G).

4.7. Графы с заданной последовательностью степеней

Степенной последовательностью графа называется список степеней его вершин. Часто по степеням вершин графа можно судить о его строении. Естественно возникают следующие вопросы. Как связать между собой степени вершин графа? Как по списку степеней графа судить о его строении? Какова связь между графами с совпадающими списками степеней вершин? Можно ли построить граф с заданным списком степеней вершин и предписанными теоретико-графовыми свойствами и как это сделать?

Последовательность неотрицательных целых чисел называется графической, если существует граф с такими вершинами , что вершина имеет степень . Этот граф называется реализацией последовательности .

Последовательность обозначается одной буквой D, т. е. D= . Очевидно, что порядок членов в графической последовательности несуществен, а каждый ее член удовлетворяет неравенствам . Часто удобно эти последовательности считать невозрастающими. Согласно лемме о рукопожатиях сумма всех членов графической последовательности является четным числом.

Назовем последовательность правильной, если выполняются два следующих условия:

1) , (4.1)

2) – четное число. (4.2)

Без ограничения общности графическую последовательность можно считать правильной.

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

Рассмотрим последовательность D=(2, 2, 2, 2, 1, 1, 1, 1). Существует ровно пять графов, являющихся реализациями последовательности D. Они имеют следующие компоненты: 1) С₄, К₂ и К₂, 2) К₃, Р₃ и К₂, 3) Р₆ и К₂, 4) Р₅ и Р₃, 5) Р₄ и Р₄. Здесь С₄ – простой цикл, содержащий 4 вершины, Р_n – простые цепи, содержащие n вершин (n=3,4,5,6).

Обоснуем алгоритм построения простого графа (если он существует), имеющего заданную последовательность степеней.

Рассмотрим графическую последовательность , упорядоченную по невозрастанию: . Пусть – степень вершины . «Изъять » означает соединить соответствующую вершину с вершинами , если , или с вершинами , если . Последовательность , если , или , если , называется остаточной последовательностью после изъятия или просто остаточной последовательностью.

Хакими и Гавел предложили алгоритм построения простого графа (если он существует), имеющего заданную последовательность степеней [3]. Этот результат основан на результате, являющимся частным случаем (при k=1) следующей теоремы.

Теорема 4.7.1. Если последовательность , , является последовательностью степеней простого графа, то этим свойством обладает и остаточная последовательность после изъятия .

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

Шаг 1. – последовательность степеней, упорядоченная по невозрастанию. Выберем произвольное ¹0 и «изымем» из последовательности, соединяя вершину с первыми вершинами, не считая саму вершину .

Шаг 2. Упорядочим остаточную последовательность в порядке невозрастания.

Шаг 3. Шаги 1–2 выполнять до тех пор, пока не возникнет одна из следующих ситуаций:

а) все остаточные степени равны 0. В этом случае последовательность степеней является графической. Искомый граф получается в результате выполнения шагов, соответствующих порядку изъятия степеней;

б) хотя бы одна из остаточных степеней отрицательна – это означает, что последовательность не является графической, т. е. не существует простого графа, который ее реализует.

Для иллюстрации описанного алгоритма рассмотрим пример последовательности

D=(4, 3, 3, 2, 2).

После изъятия (обведенной кружком), получим последовательность

D'=(3, 2, 0, 1, 2),

которая после переупорядочивания остаточных степеней принимает вид

D₁=(3, 2, 2, 1, 0).