Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
о применению теории графов в органической химии. При этом он использовал понятие висячая вершина дерева для подсчета числа изомеров предельных (не имеющих циклов) углеводородов.
Решим еще одну задачу по химии: Насыщенным углеводородом называется соединение углерода С, имеющего валентность 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 = - взвешенный граф, имеющий 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 = , ?(Vi, Vj) - вес дуги, Vi=Vj, ?(Vi, Vj)= 0. ? - вес маршрута. W = (wij) - матрица весов, (wij)= ?(Vi, Vj), если Vi, Vj€ U; (wij)=00, если (Vi, Vj ) U
Предположим, что в G отсутствуют контуры с отрицательным весом, поскольку, двигаясь по такому контуру достаточное количество раз, можно получить маршрут, имеющий вес, меньший любого заведомо взятого числа, и тем самым задача нахождения расстояния становиться бессмысленной.
Определим алгоритм Форда-Белмиана.
Зададим строку полагая В этой строке есть вес дуги , если существует, и если
Определим строку полагая dj(2) = min {dj(1), dk(1) + ?kj}k=1,…n
Нетрудно заметить, что dj(2) - минимальный из весов (Vi, Vj) - маршрутов, состоящий не более, чем из двух дуг (рис. 35).
Продолжая процесс, на шаге S определим строку Д(s) = (d1(s), d2(s),…, dn(s)), полагая dj(s)= min { dj(s-1), dk(s-1) + ?kj}k=1,…n
Искомая строка ?-расстояний получается при s = n - 1 : dj(n-1)= ?? (Vi, Vj). Действительно, на этом шаге из всех весов (Vi, Vj) -маршрутов, содержащих не более (n-1) дуг, выбирается наименьший, а каждый маршрут более чем с (n-1) дугами содержит контур, добавление которого к маршруту не уменьшает ?-расстояния, т.к. было предположение отсутствия контуров отрицательного веса.
Работу алгоритма можно завершить на шаге к, если Д(к) = Д(к+1).
Пример: Продемонстрируем работу алгоритма Форда-Беллмана. На примере взвешенного графа, показанного на рис.36 с матрицей весов.
В качестве источника выберем Т - {1}, тогда
Д(1) = (0, 1, ? , ?, 3),min маршрут сост. 1 дуги
Д(2) = (0, 1, 4, 4, 3),не более 2 дуг
Д(3) = (0, 1, 4, 4, -1),3 дуг
Д(4) = (0, 1, 4, 3, -1).4 дуг
Таким образом, ?? (1, 1) = 0, ?? (1, 2) = 1, ?? (1, 3) = 4, ?? (1, 4) = 3, ?? (1, 5) = -1.
Зная расстояние от ?/p>