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

Содержание

Введение 1

Смешенный граф и формула его перечисления. 2

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

Кратчайшие пути 10

Заключение 14

Библиографический список 15

Введение

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

Значительно возросла популярность теории графов – ветви дискретной математики. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" – в электронике, "социограммы" – в социологии и экономике, "молекулярные структуры" – в химии, "дорожные карты", электрические или газовые распределительные сети и т. д. [8]

Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов – это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться. [7]

В данной работе я рассмотрю понятие смешанного графа. Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G := (V, E, A), где V - это множество вершин или узлов, E - это множество пар (неупорядоченных) различных вершин, называемых рёбрами и A - это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами. Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.

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

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

Рис. 1 Смешанный граф четвертого порядка.

Неориентированный граф можно трактовать как смешанный граф, не имеющий ориентированных ребер. Далее орграф можно рассматривать как смешанный граф, заменяя для этого каждую симметричную пару ориентированных ребер неориентированным ребром. [5]

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

Рис. 2 16 смешанных графов третьего порядка.

Пусть m_pqr — число смешанных графов с р вершинами, q ориентированными ребрами и г неориентированными ребрами. Тогда многочлен m_p(х,у), перечисляющий смешанные графы с р вершинами в соответствии как с числом неориентированных, так и числом ориентированных ребер, определяется формулой

 (1),

где q+1 ? .

Из рис. 2 следует, что при р = 3 эта формула имеет вид

 (2).

Чтобы вывести формулу для m_p(х,у), мы воспользуемся слабо модифицированной формой теоремы Пойа. В этой модификации оба вида перечисляющих рядов для фигур применяются совместно со специальным цикловым индексом, зависящим от переменных двух.

Получаем равенство

.

Таким образом, Z (; S_k, t_k) является цикловым индексом редуцированной упорядоченной парной группы , в котором переменные S_k используются для пар взаимно обратных циклов, а переменные t_k — для самообратных циклов. Мы увидим, что, подставляя в это выражение вместо каждой переменной S_k функцию

,

а вместо каждой переменной t_k функцию

,

получим многочлен m_p(х,у). [1]

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

(4),

где

В качестве примера приведем некоторые детали для случая p=3. Сначала получаем формулу для циклового индекса:

 (6).

Подставляя перечисляющие ряды для фигур:



и

,

приходим к выражению

 (7), которое полностью согласуется с формулой (2), а соответствующие ему смешанные графы показаны на рис. 2.

Соотношение (5) не требует комментариев, кроме замечания о том, что оно получается из формулы

с помощью ее модификации в соответствии с той частью доказательства формулы

,

где показывается, что каждый четный цикл подстановки из S_p индуцирует самообратный цикл.

Здесь представлен краткий набросок доказательства формулы (4). Причем, степенная группа  действует на функциях из множества. Так как каждая такая функция f представляет орграф, скажем, с q ориентированными ребрами и г симметричными парами дуг, то f можно также трактовать как смешанный граф с q ориентированными и г неориентированными ребрами. Очевидно, что любые две функции из множества  принадлежат одной и той же орбите степенной группы тогда и только тогда, когда соответствующие им смешанные графы изоморфны. Наконец, функциям обычным образом приписываются веса и, применяя взвешенный вариант леммы Бернсайда, получают соотношение (4).

Идея использования выражения 1+2x+y состоит в следующем: слагаемое 1 соответствует парам несмежных вершин, в то время как 2х указывает на две возможные ориентации, а у — на неориентированное ребро. Радикал в выражении

,

исчезает в m_p(х,у), потому что каждая переменная S_k встречается только в четной степени, ибо взаимно обратные циклы обязательно появляются парами. Аналогично двучлен 1+y отражает, как обычно, отсутствие ребра и наличие неориентированного ребра (ориентированные ребра просто запрещены для самообратных циклов). Радикал в

,

также исчезает в m_p(х,у), ибо, как показано в формуле (5), в единственном ее произведении, содержащем t_k, индексы к — четные. Это в свою очередь справедливо потому, что каждый самообратный цикл имеет четную длину.

Перечисляющие многочлены g_p(x) и d_p(x) для графов и орграфов будем считать выведенными. Многочлен о_р(х) для направленных графов найден Харари. Заметим, что каждый из этих многочленов легко получается из m_p(х,у), который является, таким образом, одновременным обобщением всех трех указанных перечислительных формул:

d_p(x) = m_p(x, ), о_р(х) = m_р(х,0), g_p(y) = m_p(0, у) (8).

Для р = 3 находим, используя соотношение (7):

d₃(x) = m₃(x, ) = 1 + x + 4

о₃(х) = m₃(х,0) = 1 + x + 

g₃(y) = m₃(0, у) = 1 + y + 

Правильность этих выражений легко установить с помощью рис. 2. [3]

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

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

Рис. 3 Полный орграф пятого порядка.

Пусть c_pqr — число полных орграфов с р вершинами, имеющих в точности q ориентированных ребер и г симметричных пар. Многочлен с_p(х,у), который перечисляет полные орграфы с р вершинами в соответствии и с числом ориентированных ребер, и с числом симметричных пар, определяется формулой

 (10),

где

.

Рис.4 Полные орграфы третьего порядка.

Из рис. 4 следует, что при р = 3 формула имеет вид

с₃(х,у) = 2х³ + Зх²у + ху² + у³.

Перечислительная формула для с_р(х,у) легко получается путем модификации формулы для смешанных графов. Число 1 в каждом из двух перечисляющих рядов для фигур



и

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

и

.

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

с_р(х,y) =  (11),

Из этого следствия немедленно выводим, что число турниров с р вершинами равно

 (12).

Используя (12) и (5), с помощью несложных преобразований получаем в явной форме формулы

,

и

Общее число с_р полных орграфов, если не фиксировать число ориентированных ребер и симметричных пар, есть

с_р = с_р(1,1) (13).

Например, рис. 4 показывает, что с₃ = 7. Используя формулу (5), получаем следующее выражение для с_р. [6]

Теорема. Число полных орграфов порядка р есть

 (14),

где

 (15). [4]

Первые пять значений величины с_р таковы:

Кратчайшие пути

Пусть 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.

1. Для всех 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*.

1. p:=v*. Если p = t, то перейти к п. 5 [l(t)—вес кратчайшего пути]. Иначе перейти к п. 2.

2. P*:=(s, ..., ?³(t), ?²(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. W⁰:=W, k:=1, P°:= ||P_ij⁰|| где P_ij⁰=i если Wij ? ?, и P_ij⁰ =0 в противном случае.

2. Выполнить для всех (i, j)=1,n если W_ij^k-1< W_ik^k-1 + W_kj^k-1, то W_ij^k = W_ij^k-1 , P_ij^k= P_ij^k-1. Иначе W_ij^k := W_ik^k-1 + W_kj^k-1, P_ij^k := P_kj^k-1 .

3. Если для некоторого l, 1? l ? n, то конец [в графе имеется отрицательный контур]. Иначе перейти к п. 4.

4. k:=k+1. Если k = n +1, то конец [Wⁿ= || W_ijⁿ || —матрица весов кратчайших путей, определяемых с по­ мощью матрицы Р^п = || P_ijⁿ ||].

Замечание 3. Алгоритм будет применим к сме­шанным графам, если каждое неориентированное ребро заменить на две дуги того же веса. При этом следует учесть, что неориентированное ребро отрицательного веса сразу приводит к отрицательному контуру. [2]

Заключение

В настоящем реферате рассмотрены смешанные графы, области их применения, решены задачи с помощью смешных графов, рассмотрены теоремы и следствия из них. Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом, поэтому очень важно знать, что это такое. Данный реферат можно использовать для объяснения материала студентам, а также включить некоторые его части в курсовую работу по графам.

Библиографический список

1. Харари Ф, Палмер Э. Перечисление графов. – Мн.: Мир, 1976 . – 326с.

2. Емеличев В.А., Лекции по теории графов. – М.: Наука,1990. – 383с.

3. Берж К., Теория графов и её применение. Перевод с французского Зыков А.А., под редакцией Вайнштейна И.А. – М.: Издательство иностранной литературы, 1962. – 320с.

4. Оре О., Графы и их применение. Перевод с английского Головиной Л.И., под редакцией Яглома И.М. – М.: Мир, 1965. – 175с.

5. Уилсон Р., Введение в теорию графов. Перевод с английского Никитиной И.Г., под редакцией Гаврилова Г.П., - М.: Мир, 1977. – 208с.

6. Татт У., Теория графов, перевод Гаврилова Г.П., - М.: Мир, 1988. – 424с.

Интернет источники:

1. http://www.intuit.ru/department/algorithms/ingrth/1/

2. http://www.math.mrsu.ru/text/method/%EE%F1%ED%EE%E2%ED%FB%E5_%EF%EE%ED%FF%F2%E8%FF_%F2%E5%EE%F0%E8%E8_%E3%F0%E0%F4%EE%E2.htm