- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Разрешимые и неразрешимые проблемы
- •Библиографический список
4.6. Метрические характеристики графа. Расстояние в графах
Пусть G=(X,V) – связный неорграф. xi, xj – две его несовпадающие вершины. Длина кратчайшего (xi, xj) –маршрута называется расстоянием между вершинами xi, и xj и обозначается через р(xi, xj). Положим р(xi, xi)=0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:
p(xi, xj)0;
р(xi, xi ) = 0 xi,=xj;
p(xj,xi,) = p(xi, xj) (симметричность):
p(xi, xj)p(xi, xk)+p(xk, xj) (неравенство треугольника).
Если X={x1,x2, …, xn}, то матрица Р=(pij), в которой pij=p(xi,xj), называется матрицей расстояний. Заметим, что РT=Р, т. е. матрица Р симметрична.
Для фиксированной вершины xi, величина е(xi)= =max{p(xi, xj) | xj X} называется эксцентриситетом вершины xi. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее. Если Р – матрица расстояний, то эксцентриситет е(xi) равен наибольшему из чисел, стоящих в i-й строке.
Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G): d(G)=max{e(xi) | xi X}. Вершина xi называется периферийной, если e(xi)=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(xi) | xiМ}. Вершина xi называется центральной, если е(xi)=r(G). Множество всех центральных вершин графа называется его центром.
Примеры.
1. Радиус графа, показанного на рис. 4.21, равен 2, а его центром является множество {2,4,5}.
2. В полном графе Кп все различные вершины смежны, и поэтому d(Kn) = r(Кn) = 1.
Задача нахождения центральных вершин возникает в практической деятельности людей. Пусть, например, граф представляет собой сеть дорог, т. е. вершины соответствуют населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т. п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной тем, что приходится учитывать и другие обстоятельства – расстояния между населенными пунктами, стоимость, время проезда и т. д. Для учета этих параметров используются взвешенные графы [4].
Пусть G = (X,V) – взвешенный граф, в котором вес каждой дуги (xi,xj) есть некоторое вещественное число (xi,xj). Весом маршрута x1, x2, ... , xn, xn+1, называется число . Взвешенным расстоянием (- расстаянием) p(xi,xj) между вершинами xi и xj называется минимальный из весов (xi,xj)-маршрутов. (xi,xj)-маршрут, вес которого равен расстоянию p(xi,xj), называется кратчайшим (xi,xj)-маршрутом в взвешенном графе G. Взвешенным эксцентриситетом e (xi) вершины xi называется число mах{p(xi,xj) | xjМ}. Взвешенной центральной вершиной графа G называется вершина xi, для которой е(xi)=min{е(xj) | xj М}. Взвешенный эксцентриситет центральной вершины называется взвешенным радиусом графа G и обозначается через r(G).
4.7. Графы с заданной последовательностью степеней
Степенной последовательностью графа называется список степеней его вершин. Часто по степеням вершин графа можно судить о его строении. Естественно возникают следующие вопросы. Как связать между собой степени вершин графа? Как по списку степеней графа судить о его строении? Какова связь между графами с совпадающими списками степеней вершин? Можно ли построить граф с заданным списком степеней вершин и предписанными теоретико-графовыми свойствами и как это сделать?
Последовательность неотрицательных целых чисел называется графической, если существует граф с такими вершинами , что вершина имеет степень . Этот граф называется реализацией последовательности .
Последовательность обозначается одной буквой D, т. е. D=. Очевидно, что порядок членов в графической последовательности несуществен, а каждый ее член удовлетворяет неравенствам . Часто удобно эти последовательности считать невозрастающими. Согласно лемме о рукопожатиях сумма всех членов графической последовательности является четным числом.
Назовем последовательность правильной, если выполняются два следующих условия:
-
, (4.1)
-
– четное число. (4.2)
Без ограничения общности графическую последовательность можно считать правильной.
В общем случае графическая последовательность имеет много реализаций и их число определить сложно. Иногда, хотя и редко граф определяется своей степенной последовательностью однозначно. Если все реализации графической последовательности изоморфны, то эта последовательность называется униграфической, а граф – униграфом.
Рассмотрим последовательность D=(2, 2, 2, 2, 1, 1, 1, 1). Существует ровно пять графов, являющихся реализациями последовательности D. Они имеют следующие компоненты: 1) С4, К2 и К2, 2) К3, Р3 и К2, 3) Р6 и К2, 4) Р5 и Р3, 5) Р4 и Р4. Здесь С4 – простой цикл, содержащий 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),
которая после переупорядочивания остаточных степеней принимает вид
D1=(3, 2, 2, 1, 0).