рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Полный граф и формула его перечисления

Полный граф и формула его перечисления - раздел Математика, Смешанные графы Полный Граф И Формула Его Перечисления. Полный Орграф Имеет Для Каждой Пары В...

Полный граф и формула его перечисления. Полный орграф имеет для каждой пары вершин либо ориентированное ребро, либо симметричную пару ребер, соединяющих эти вершины.

Орграф на рис. 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 &#8800; &#8734;, и 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&#8804; l &#8804; n, то конец [в графе имеется отрицательный контур]. Иначе перейти к п. 4. 4. k:=k+1. Если k = n +1, то конец [Wn= || Wijn || —матрица весов кратчайших путей, определяемых с по¬ мощью матрицы Рп = || Pijn ||]. Замечание 3. Алгоритм будет применим к сме¬шанным графам, если каждое неориентированное ребро заменить на две дуги того же веса. При этом следует учесть, что неориентированное ребро отрицательного веса сразу приводит к отрицательному контуру. [2]

– Конец работы –

Эта тема принадлежит разделу:

Смешанные графы

Значительно возросла популярность теории графов – ветви дискретной математики.Графы встречаются во многих областях под разными названиями:… Для специалистов по вычислительной технике, информационным системам и системам… Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые —…

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Полный граф и формула его перечисления

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Смешенный граф и формула его перечисления
Смешенный граф и формула его перечисления. Смешанный граф может содержать как неориентированные ребра, так и ориентированные. Например, граф, изображенный на рис 1, является смешанным графом с двум

Библиографический список
Библиографический список. Харари Ф, Палмер Э. Перечисление графов. – Мн.: Мир, 1976 . – 326с. 2. Емеличев В.А Лекции по теории графов. – М.: Наука,1990. – 383с. 3. Берж К Теория графов и её примене

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги