Реферат Курсовая Конспект
Полный граф и формула его перечисления - раздел Математика, Смешанные графы Полный Граф И Формула Его Перечисления. Полный Орграф Имеет Для Каждой Пары В...
|
Полный граф и формула его перечисления. Полный орграф имеет для каждой пары вершин либо ориентированное ребро, либо симметричную пару ребер, соединяющих эти вершины.
Орграф на рис. 3 является полным ориентированным графом с пятью вершинами, тремя парами симметричных дуг и семью ориентированными ребрами. Рис. 3 Полный орграф пятого порядка. Пусть cpqr — число полных орграфов с р вершинами, имеющих в точности q ориентированных ребер и г симметричных пар. Многочлен сp(х, у), который перечисляет полные орграфы с р вершинами в соответствии и с числом ориентированных ребер, и с числом симметричных пар, определяется формулой (10), где. Рис.4 Полные орграфы третьего порядка.
Из рис. 4 следует, что при р = 3 формула имеет вид с3(х, у) = 2х3 + Зх2у + ху2 + у3. Перечислительная формула для ср(х, у) легко получается путем модификации формулы для смешанных графов. Число 1 в каждом из двух перечисляющих рядов для фигур и отражает возможность отсутствия ребра, соединяющего пару вершин.
Но в полном орграфе всегда существует либо ориентированное ребро, либо симметричная пара, соединяющие пару вершин. Поэтому подходящими перечисляющими рядами для фигур являются ряды и. Следствие. Перечисляющий многочлен для полных орграфов с р вершинами дается формулой ср(х, y) = (11), Из этого следствия немедленно выводим, что число турниров с р вершинами равно (12). Используя (12) и (5), с помощью несложных преобразований получаем в явной форме формулы, и Общее число ср полных орграфов, если не фиксировать число ориентированных ребер и симметричных пар, есть ср = ср(1,1) (13). Например, рис. 4 показывает, что с3 = 7. Используя формулу (5), получаем следующее выражение для ср. [6] Теорема.
Число полных орграфов порядка р есть (14), где (15). [4] Первые пять значений величины ср таковы: p 1 2 3 4 5 cp 1 2 7 42 582 Кратчайшие пути Пусть G=(V, A)—ориентированный взвешенный граф. Задача о кратчайшем пути состоит в отыскании пу¬ти минимального веса, соединяющего заданные началь¬ную и конечную вершины графа G при условии, что хо¬тя бы один такой путь существует.
Начальную и конеч¬ную вершины обозначим соответственно через s и t; (s, t)-путь минимального веса будем называть кратчай¬шим (s, t)-путем. Вначале рассмотрим случай, когда веса всех дуг гра¬фа неотрицательны, т. е. w(e) ≥ 0 для каждой дуги е € А. В этом случае решение задачи о кратчайшем пути явля¬ется существенно менее трудоемким, чем в общем случае.
Первый эффективный алгоритм построения кратчайшего пути в графе с неотрицательными весами дуг предложил Е. Дийкстра в 1959 г. На каждой итерации этого алгоритма всякая вершина и графа G имеет метку l(v), которая может быть посто¬янной либо временной. В первом случае l(v) — вес кратчайшего (s, v)-пути. Если же метка l(v) временная, то l(v)—вес кратчайшего (s, v)-пути, проходящего только через вершины с постоянными метками. Таким образом, временная метка l(v) является оценкой сверху для веса кратчайшего (s, v) -пути, и став на некоторой итерации постоянной, она остается такой до конца работы алгорит¬ма. Кроме l(v), с каждой вершиной v графа G, за исклю¬чением s, связывается еще одна метка— θ(v). На каждой итерации θ(v) является номером вершины, предшествую¬щей v в (s, v) -пути, имеющем минимальный вес среди всех (s, v) -путей, проходящих через вершины, получив¬шие к данному моменту постоянные метки.
После того как вершина t получила постоянную метку, с помощью меток θ(v) легко указать последовательность вершин, со¬ставляющих кратчайший (s, t)-путь. Перед началом первой итерации алгоритма вершина s имеет постоянную метку l(s)=0, а метки l всех осталь¬ных вершин равны ∞ и эти метки временные.
Общая итерация алгоритма состоит в следующем. Пусть р — вершина, получившая постоянную метку l(р) на преды¬дущей итерации. Просматриваем все вершины v € Г(р), имеющие временные метки, с целью уменьшения (если это возможно) этих меток.
Метка l(v) вершины Г(p) заменяется на l(p)+w(p, v), если оказалось, что l(v)>l(p)+ w(p, v). В этом случае говорим, что вершина v получила свою метку l из вершины p, и полагаем θ(v) = p. Если же l(v) ≤ l(p)+ w(p, v), то метки θ и l вер¬шины v не изменяются на данной итерации. Алгоритм заканчивает работу, когда метка l(t) становится постоян¬ной. Как уже говорилось выше, l(t)—вес кратчайшего (s, t)-пути, который будем обозначать через Р*. Этот путь определяется с помощью меток θ так: где для любой вершины v € VG. Будем считать, что граф G задан матрицей весов ли¬бо списками смежности. Алгоритм A5 Дийкстры поиска кратчайшего пути. 1. Положить l(s): = 0 и считать эту метку постоян¬ной. Положить l(v):=∞ для всех v € VG, v≠s, и считать эти метки временными.
Положить р := s. 2. Для всех v € Г(p) с временными метками выполнить: если l(v)> l(p)+ w(p, v), то l(p):= l(p) + w(p, v) и θ(v) := p. Иначе l(v) и θ(v) не менять. 3. Пусть V’ — множество вершин с временными мет¬ками l. Найти вершину v*, такую что Считать метку l(v*) постоянной меткой вершины v*. 4. p:=v*. Если p = t, то перейти к п. 5 [l(t)—вес кратчайшего пути]. Иначе перейти к п. 2. 5. P*:=(s, θ3(t), θ2(t), θ(t), t) [P*- кратчай¬ший путь]. Конец. Прежде чем перейти к обоснованию алгоритма, сде¬лаем три полезных замечания.
Замечание 1. Как легко видеть, алгоритм A5 применим к смешанным и, в частности, к неориентиро¬ванным графам.
Для этого достаточно каждое неориенти¬рованное ребро uv графа, имеющее вес w(u, v), рассмат¬ривать как пару дуг (и, v) и (v, и) того же веса. Замечание 2. Если п. 4 модифицировать так, чтобы алгоритм заканчивал работу только после получения всеми вершинами постоянных меток, то он будет строить кратчайшие пути из s в каждую из остальных вершин. Если к тому же вместе с превращением метки вершины v* в постоянную (п. 3 алгоритма) заносить дугу (θ(v*), (v*) в множество А*, то после окончания работы алгоритма граф D=(VG, А*) будет корневым ориентированным остовным деревом.
Это дерево называют деревом кратчайших путей из s графа G. Для любой вершины v € VG единственный (s, v)-путь в дереве D является кратчайшим (s, v) -путем в графе G. Алгоритм A6 отыскания кратчайших путей между всеми парами вершин. 1. W0:=W, k:=1, P°:= ||Pij0|| где Pij0=i если Wij ≠ ∞, и Pij0 =0 в противном случае. 2. Выполнить для всех (i, j)=1,n если Wijk-1< Wikk-1 + Wkjk-1, то Wijk = Wijk-1 , Pijk= Pijk-1. Иначе Wijk := Wikk-1 + Wkjk-1, Pijk := Pkjk-1 . 3. Если для некоторого l, 1≤ l ≤ n, то конец [в графе имеется отрицательный контур]. Иначе перейти к п. 4. 4. k:=k+1. Если k = n +1, то конец [Wn= || Wijn || —матрица весов кратчайших путей, определяемых с по¬ мощью матрицы Рп = || Pijn ||]. Замечание 3. Алгоритм будет применим к сме¬шанным графам, если каждое неориентированное ребро заменить на две дуги того же веса. При этом следует учесть, что неориентированное ребро отрицательного веса сразу приводит к отрицательному контуру. [2]
– Конец работы –
Эта тема принадлежит разделу:
Значительно возросла популярность теории графов – ветви дискретной математики.Графы встречаются во многих областях под разными названиями:… Для специалистов по вычислительной технике, информационным системам и системам… Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые —…
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Полный граф и формула его перечисления
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов