КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Расстояние в графах
Метрические характеристики графа.
Пусть 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) есть некоторое вещественное число m(xi,xj). Весом маршрута x1, x2,..., xn, xn+1, называется число . Взвешенным расстоянием ( - расстаянием) pv(xi,xj) между вершинами xi и xj называется минимальный из весов (xi,xj)- маршрутов. (xi,xj) -маршрут, вес которого равен расстоянию pv(xi,xj), называется кратчайшим (xi,xj) -маршрутом в взвешенном графе G. Взвешенным эксцентриситетом ev (xi) вершины xi называется число mах{ pv(xi,xj) | xj Î М}. Взвешенной центральной вершиной графа G называется вершина xi, для которой еv(xi)=min{еv(xj) | xjÎ М}. Взвешенный эксцентриситет центральной вершины называется взвешенным радиусом графа G и обозначается через rv(G).
4.7. Графы с заданной последовательностью степеней
Степенной последовательностью графа называется список степеней его вершин. Часто по степеням вершин графа можно судить о его строении. Естественно возникают следующие вопросы. Как связать между собой степени вершин графа? Как по списку степеней графа судить о его строении? Какова связь между графами с совпадающими списками степеней вершин? Можно ли построить граф с заданным списком степеней вершин и предписанными теоретико-графовыми свойствами и как это сделать?
Последовательность неотрицательных целых чисел называется графической, если существует граф с такими вершинами , что вершина имеет степень . Этот граф называется реализацией последовательности . Последовательность обозначается одной буквой D, т. е. D = . Очевидно, что порядок членов в графической последовательности несуществен, а каждый ее член удовлетворяет неравенствам . Часто удобно эти последовательности считать невозрастающими. Согласно лемме о рукопожатиях сумма всех членов графической последовательности является четным числом. Назовем последовательность правильной, если выполняются два следующих условия: 1) , (4.1) 2) – четное число. (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), которая после переупорядочивания остаточных степеней принимает вид
D 1=(3, 2, 2, 1, 0). Затем, изымая степень, соответствующую вершине , получим
D '1=(2, 1, 0, 1, 0). Переупорядочивая остаточные степени в D'1, получим
D 2=(2, 1, 1, 0, 0). Теперь, изымая степень, соответствующую вершине , получим
D '2=(0, 0, 0, 0, 0). Здесь алгоритм заканчивает работу. Поскольку все остаточные степени равны нулю, последовательность (4, 3, 3, 2, 2) графическая. Требуемый граф (рис. 4.22) получается в результате выполнения шагов, соответствующих порядку изъятия степеней: 1. Соединяем вершину с вершинами , и . 2. Соединяем вершину с вершинами и . 3. Соединяем вершину с вершинами и .
Рис. 4.22. Граф с последовательностью степеней (4, 3, 3, 2, 2) Замечание. Можно привести пример последовательности, например, (3, 3, 1, 1), для которой условия (4.1) – (4.2) выполняются, но она не является графической. Условия (4.1) – (4.2) не являются достаточными для того, чтобы последовательность была графической.
Дата добавления: 2014-12-27; Просмотров: 866; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |