Выпускная квалификационная работа теория графов
 Скачать 0.56 Mb.
|
 Рис. 11 Из графа G, добавлением вершины 5 образуется граф G1, добавлением дуги (3, 1) - G2, удалением дуги (3, 2) - G3, удалением вершины 2 - G4, отождествлением вершин 1 и 4 - G5 , стягиванием дуги (2, 3) - G6. Добавлением графа без петель G = <V, U> называется граф  = <V, V2 \ (U u i av)>. Рис. 12 Объединением G1 u G2 называется граф <V1 u V2, U1 u U2>. Если V1 ∩ V2 ≠ Ø, то пересечением G1 ∩ G2 называется граф <V1 ∩ V2, U1 ∩ U2 >. Кольцевой суммой G1 + G2, называется граф <V1 u V2, (U1 \ U2) u (U2 \ U2). Соединением G1 + G2 называется <V1 u V2, U1 u U2 u {[Vi, Vj] | Vi є V2, Vi ≠ Vj}>. Произведением G1 x G2 называется граф <V1 x V2, U>. Композицией G1 [G2] называется граф <V1 x V2, U>, в котором ((V1j, V1j), (Vj2, Vj2)) є U, если 1) (Vj1, Vj2) є U1; 2) Vi1 = Vi2, (Vj1, Vj2) є U2. Рассмотрим специальный класс графов, имеющий важное практическое значение, представители которого именуются деревьями. Связный неориентированный граф называется деревом, если он не имеет циклов. В частности, дерево не имеет петель и кратных ребер. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф называется лесом. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов. Рис. 14 Рис. 15 Пример дерева показан на рис.14, здесь же показаны висячие вершины, на рисунке они выделены закрашенными кружками (вершина дерева, степень которой равна единице, называется висячей вершиной). Пример леса показан на рис.15. Постройте какое-нибудь дерево с пятью вершинами и подсчитайте число ребер в полученном графе. Оказывается, что в любом дереве с пятью вершинами всегда будет четыре ребра. Теорема: дерево с n вершинами имеет n-1 ребро. Для того, чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из Г одно ребро. Для образования трех деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с n вершинами можно получить n деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить n-1 ребро из дерева Г. Итак, действительно, в дереве с n вершинами n-1 ребро. Задача. Проводится эксперимент, при котором морскую свинку пускают в лабиринт (рис.16). Сколькими способами она может попасть к пище, если она ни в один тупик не заходит более одного раза, причем, попав в тупик, возвращается на перекресток, с которого свернула в этот тупик. Нарисуйте дерево всевозможных маршрутов морской свинки к пище. Рис. 16 Ответ: 8 способами Рис. 17 § 2. Расстояния в графах. Диаметр, радиус, центр графа Пусть G = <V, U> - связный неорграф, Vi, Vj - две его несовпадающие вершины. Длина кратчайшего (Vi, Vj)-маршрута называется расстоянием между вершинами Vi и Vj и обозначается через ρ (Vi, Vj). Положим ρ (Vi, Vj) = 0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики: 1) ρ (Vi, Vj) ≥ 0; 2) ρ (Vi, Vj) = 0 ↔ Vi = Vj 3) ρ (Vi, Vj) = ρ (Vi, Vj) - симметричность 4) ρ (Vi, Vj) ≤ ρ (Vi, Vj) + ρ (Vj, Vк) - неравенство треугольника. Если V = {V1, V2,…, Vn}, то матрица Р = (рi,j) = ρ (Vi, Vj), называется матрицей расстояний (где матрица Р симметрична). Для фиксированной вершины V величина Е (v) = мах { ρ (Vi, Vj) | Vj є V} называется эксцентриситетом вершины V. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее. Если Р-матрица расстояний, то эксцентриситет Е (Vi) равен наибольшему из числе, стоящих в i-й строке. Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d (G) : d (G) = vf[ {E(v) | v є V}. Вершина V называется периферийной, если Е (v) = d (G). Рассмотрим пример. Найдем диаметр графа G, изображенный на рис.18. Матрица расстояний Р имеет вид:  Рис. 18 Отсюда Е (1) = 3, Е (2) = 2, Е (3) = 3, Е (4) = 2, Е (5) = 2 и, следовательно, d (G) = 3. Вершины 1 и 3 являются периферийными. Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r (G) : r (G) = min {E (vi) | vi є V}. Вершина V называется центральной, если Е (v) = r (G). Множество всех центральных вершин графа называется его центром. Рассмотрим соответствующий пример. Радиус графа, показанного на рис.18, равен 2, а его центром является множество {2, 4, 5}. Задача нахождения центральных вершин возникает в практической деятельности людей. Пусть, например, граф представляет собой сеть дорог, т.е. вершины соответствуют населенным пунктам, а ребра - дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т.п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной темы, что приходится учитывать и другие обстоятельства - расстояния между населенными пунктами, стоимость, время проезда и т.д. Дерево - одно из наиболее часто встречающихся в теории графов понятий (рис.19). Ясно, что «особое место» в дереве занимают не только висячие вершины. Выделяются в этих деревьях и вершины, отмеченные двойным кружком. Такие вершины называют корневыми. Корневую вершину нетрудно также выделить у деревьев на рисунках 20, 21, 22. В первом случае корневой вершиной является единственная вершина графа А, во втором - вершина С, в третьем (такое дерево, все вершины которого, кроме одной, висячие, называют «звездой») - вершина А. Но какие вершины считать корневыми в графах, которые изображены на рисунках 23, 24 и 25? Естественно считать, что все эти три дерева имеют по две корневые вершины. У дерева на рисунке 23 - это А и В, у дерева на рисунке 24 - это С и Д, у дерева на рисунке 25 - это А и В. Расстоянием d (Vi, Vj) между вершинами Vi и Vj графа G называют длину кратчайшего пути, их соединяющего. (Если граф G-дерево, то путь соединяющий вершины Vi и Vj, единственный). Подсчитаем для каждой вершины дерева, изображенного на рисунке 26, наибольшее из расстояний до всех остальных его вершин и запишем эти числа на рисунке возле вершин (рис.27). Наибольшее из таких чисел называют диаметром графа (в данном случае дерева), наименьшее - радиусом графа. Вершины дерева, для которых максимальное из расстояний до других вершин равно радиусу, называются корневыми. Для дерева, изображенного на рисунке 26, диаметр равен 5, а радиус равен 3; корневые вершины - А и В. Задача. Подсчитайте диаметр и радиус графа, изображенного на рисунке: а) 18; б) 24; в) 25. Английский математик А.Кэли в 1875 году опубликовал первую работу по применению теории графов в органической химии. При этом он использовал понятие «висячая вершина» дерева для подсчета числа изомеров предельных (не имеющих циклов) углеводородов. Решим еще одну задачу по химии: «Насыщенным углеводородом называется соединение углерода С, имеющего валентность 4 и водорода Н, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Найдите формулу насыщенного углеводорода, содержащего n атомов углерода». Рассмотрим граф, в котором вершинами являются атомы, а ребрами - соответствующие валентные связи между ними. Покажем от противного, что в графе не существует цикла, т.е. возможности, переходя по ребрам графа из вершины в вершину, вернуться в исходную вершину. Если цикл есть, то должен быть составлен из атомов углерода, поскольку водород имеет валентность 1 и может соединяться только с одним атомом. В случае существования цикла разорвем связь между двумя атомами углерода и присоединим к каждому из них еще по одному водорода. Число атомов водорода увеличится, значит, исходный граф описывал не молекулу насыщенного углеводорода. В построенном графе можно перейти по ребрам от любой вершины к любой другой, и в нем нет циклов. Такой граф называется деревом. Пусть молекула содержит n атомов углерода и m атомов водорода, тогда граф будет содержать n + m вершин. Далее, при решении задачи воспользуемся легко доказываемым соотношением: в дереве число ребер на единицу меньше числа вершин. Следовательно, в графе n + m - 1 ребер. Из вершин графа, обозначающих атомы углерода, выходит по 4 ребра, а из вершин, обозначающих атомы водорода, - одно. Используя простой факт, что сумма степеней вершин, т.е. сумма числа ребер, можно написать соотношение: 4n + m = 2 (n + m - 1). Отсюда получаем, что m = 2n + 2. Следовательно, формула насыщенного углеводорода, имеющего n атомов углерода: Сn H2n+n. Т.е., можно получить формулу вещества с помощью математики, используя только определение и не проводя химических опытов. К числу предельных (не имеющих цикла) углеводородов относится, например пентан С5Н12. Его структурная формула изображена на рисунке 28. Этой формуле можно поставить во взаимно однозначное соответствие однокорневое дерево (рис. 29), показывающее взаимное расположение только атомов углерода в молекуле пентана. Но тем самым определяется однозначно и расположение атомов водорода в этой молекуле. На рисунке 30 представлена структурная формула молекулы одного из изопентанов, а на рисунке 31 соответствующее ей двукорневое дерево. По тем или иным причинам почти все работы по теории графов таят в себе семена возможных практических применений или по крайней мере потенциально полезны. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, в областях прикладной математики. §3. Нагруженные графы. Определение кратчайших маршрутов Пусть G = <V,U>- взвешенный граф, имеющий n вершин и матрицу весов W = (wij), wij € R, где вес каждой дуги (Vi, Vj) есть некоторое вещественное число μ(Vi, Vj). Весом маршрута V1, V2, Vn, Vn+1 называется число μ  .Взвешенным расстоянием (w-расстоянием) ρω(Vi,Vj) между вершинами Vi и Vj называется минимальный из весов Vi,Vj маршрутов. (Vi,Vj) - маршрут, вес которого равен расстоянию ρω(Vi,Vj) , называется кратчайшим (Vi,Vj) - маршрутом во взвешенном графе G. Взвешенным эксцентриситетом Eω(Vi) вершины Vi называется число max{ ρω(Vi,Vj)│Vj €V} Взвешенной центральной вершиной графа G, называется вершина Vj , для которой Eω(Vi)=min{ Eω(Vi)│Vj €V} Взвешенным эксцентриситет центральной вершины называется радиусом графа G и обозначается через rw(G). Опишем некоторые методы нахождения взвешенного расстояния от фиксированной вершины Vj €V (называемой источником) до всех вершин графа G. Т.е. G = <V,U>, μ(Vi, Vj) - вес дуги, Vi=Vj, μ(Vi, Vj)= 0. μ |