Ориентированные графы

ЗАДАНИЕ

 

Тема 2. Ориентированные  графы 

 

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

1. Изучить  такие основополагающие понятия  теории графов, как ориентированный  граф. ориентированный маршрут, орцепь, орцикл и сильная связность, доказать теорему Роббинса об ориентируемом связном графе.

2. Рассмотреть  понятие эйлерова орграфа и доказать основною теорему о таких графах.

3. Рассмотреть  понятия гамильтонова орграфа  и проанализировать взаимосвязь  полугамильтоновых оргафов с турнирами.

• Разобрать приложение орграфов к теории цепей Маркова.

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

ЗАДАНИЕ 2

ВВЕДЕНИЕ 4

1 Понятия теории графа 6

2. Эйлеров орграф 13

3. Понятия Гамильтонова орграфа 18

ЗАКЛЮЧЕНИЕ 21

СПИСОК ЛИТЕРАТУРЫ 22

 

 

ВВЕДЕНИЕ

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

На тему изучения орграфов было написано много работ, например, Басанговой Е.О. и Ерусалимским Я.М. было введено понятие ориентированных графов с нестандартной достижимостью, т.е. орграфов, в которых на допустимые пути накладываются какие-либо ограничения. В обычном ориентированном графе, для того чтобы одна вершина была достижима из другой, необходимо существование пути, связывающего две эти вершины. В случае же орграфов с нестандартной достижимостью требуется, кроме того, чтобы этот путь удовлетворял некоторому условию (ограничению). Понятно, что в этом случае классические алгоритмы решения задач на графах непосредственно неприменимы.

В работах  Ерусалимского Я.М., Басанговой Е.О., Логвинова С.Ю., Скороходова В.А., Петросяна А.Г. описаны различные виды ограничений на достижимость. Так, Ерусалимским Я.М. и Басанговой Е.О. рассмотрено несколько видов достижимости на частично-ориентированных графах, на которых присутствуют ориентированные и неориентированные ребра. Введено понятие смешанной цепи, на дуги и звенья которой накладываются различные условия, в зависимости от вида ограничений. Например, рассмотрены случаи, когда в смешанной цепи два неориентированных ребра не могут следовать непосредственно друг за другом, или дуги и звенья строго чередуются.

Цель курсовой работы состоит в изучении ориентированных  графов и  их  свойств. Так же рассмотрение различных понятий и теорем, связанных с орграфами. Для достижения поставленной цели необходимо выполнить следующие задачи:

  1. Изучить такие основополагающие понятия теории графов, как ориентированный граф, ориентированный маршрут, орцепь, орцикл и сильная связность, доказать теорему Роббинса об ориентируемом связном графе.

2. Рассмотреть  понятие эйлерова орграфа и доказать основною теорему о таких графах.

3. Рассмотреть  понятия гамильтонова орграфа  и проанализировать взаимосвязь  полугамильтоновых оргафов с турнирами.

 

 

 

1 Понятия теории графа

 

Начало теории графов часто ведут от 1736 года и  связывают с решением Эйлером знаменитой задачи о Кенигсбергских мостах. Жителям в те далекие времена, чтобы придать воскресному гулянию осмысленность, предлагалось выйдя из дома (на любом участке суши (А, В, С или D) пройти по всем мостам строго по одному разу и вернуться домой….

Следующий импульс  теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

 

Рис. 1 — Граф

 

На втором рисунке этот корявый план нарисован  в виде графа. Следует отметить некоторые  практические особенности теории графов. Слово граф однокоренное со словом графика. Поэтому не удивительно, что многие задачи теории графов представляются в виде специального рисунка – графа. Однако, это, как правило, возможно только для простейших вариантов задач. Рисовать графы для задач с сотнями вершин и тысячами дуг, если и возможно, то бессмысленно. Теряется главное преимущество рисунка – наглядность. Кроме того, сегодня при решении задач теории графов широко используется вычислительная техника, а для нее - решение задачи, заданной рисунком – одно из самых неудобных представлений, какие можно придумать. А наглядность компьютер понимает по-своему.

Граф G задается как совокупность двух сущностей: множества вершин V и множества соединений – множества дуг или ребер E . G = (V, E).

· {V}= (v1 ,v2 ,...,vn)   - конечное непустое множество;

· {E}= (e1,e2 ,...,em) = - конечное множество, каждый элемент которого соответствует паре не обязательно различных элементов множества V .

Элементы  множества V называются вершинами графа.

Если элемент  множества E соответствует неупорядоченной паре вершин, т. е. e_i ~ ( v_i1, v_i2), то он называется ребром, вершины v_i1 и v_i2 - концами этого ребра. Говорят, что ребро e_i= ( v_i1, v_i2), соединяет вершины v_i1 и v_i2. Ребро, для которого v_i1= v_i2, называется петлей.

Граф, содержащий только ребра, называется неориентированным графом. Если элемент множества E соответствует упорядоченной паре вершин, т. е. e_i ~ (v_i1, v_i2) , то он называется дугой, вершина v_i1- началом, а v_i2 - концом этой дуги. Говорят, что дуга e_i = ( v_i1, v_i2) исходит из вершины v_i1и заходит в вершину v_i2 . Дуга, для которой v_i1 = v_i2 , называется ориентированной петлей.

Граф, содержащий только дуги, называется ориентированным графом. Обычно рассматривают только ориентированные или неориентированные графы. Ребра (дуги), соответствующие одним и тем же парам (упорядоченным парам) вершин называются кратными. Граф, не содержащий кратных ребер (дуг) называется простым графом, иначе – мультиграфом.

Если e_i ~ { v_i1, v_i2} или e_i ~ ( v_i1, v_i2) , то вершины v_i1 и v_i2 называются

смежными, а ребро (дуга) e_i и вершины v_i1 и v_i2- инцидентными. Если конец ребра e_i совпадает с концом ребра e_j, то эти ребра называются смежными; если начало или конец дуги e_i совпадает с началом или концом дуги e_j , то эти дуги называются смежными.

Удобство  использования графов в значительной степени определяется наглядностью их геометрического изображения.

Вершины графа  обычно (но не обязательно всегда!) изображают

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

Рис. 2.1 — Неориентированный граф                       Рис.2.2 — Ориентированный граф

 

Предположим, что G = (V,E) простой или мультиграф.

Граф G’ = (V’,E’) называется частью графа G, если V’≤ V , E’≤  E .

Часть G” = (V”,E”) называется подграфом графа G, если в ней сохраняются все ребра или дуги между вершинами множества V” ≤ V .

Часть G”’ = (V”’,E”’) называется суграфом графа G, если V “’ =V .

Примеры.

Рис. 3 - Различные виды частей графа

 

Рассмотрим  некоторые наиболее часто встречающиеся  части графов.

Как было указано  выше, ребро, соединяющее вершину  саму с собой,

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

ориентированной петлей

Вершина, не имеющая  смежных вершин, называется изолированной.

Рис. 4 - Петли и изолированные  вершины

 

Последовательность  вершин и ребер (дуг) (не обязательно  различ-

ных) v₀, e₁, v₁,e₂, v₂,…v_n-1,e_n,v_n (1) такая, что соседние вершины и ребра (дуги) инцидентны, называется путем. Если граф G ориентированный и в v_i-1 и v_i - начало и конец дуги e_i , то путь называется ориентированным. Если путь не содержит повторяющихся вершин (кроме, может быть, первой и последней) и ребер или дуг, то он называется простым. Если первая и последняя вершины пути совпадают, то он называется циклом.

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

Подграф G’ графа G называется компонентой связности, если

1) между любыми  двумя его вершинами  G’существует путь,

2) G’ не является подграфом ни одного связного подграфа графа G ,

т.е. является максимальным по включению вершин связным  подграфом

графа G .

Если граф содержит одну компоненту связности, то он называется

связным, а если более одной – несвязным.

Вершина v называется точкой сочленения, если ее исключение из графа G увеличивает количество его компонент связности. Ребро или дуга e называется мостом, если его исключение из графа G увеличивает количество его компонент связности.

Как легко  видеть через не один простой цикл не может содержать точек сочленения и мостов.

Подграф G’ориентированного графа G называется кликой, если

1) любые две  вершины G’ смежны,

2) G’ не является подграфом ни одного подграфа графа G, обладающего свойством, т.е. является максимальным по включению вершин сильно связным подграфом графа G.

Рис. 4 - Граф G и все его клики

 

Графы, не содержащие циклов, называются лесами. Связные графы, не содержащие циклов, называются деревьями. Легко видеть, что компонентами связности лесов являются деревья.

Рис. 5.1 - Ориентированный лес                                    Рис.5.2 — Неориентированное дерево

 

Граф G называется пустым, если он не содержит вершин. Неориентированный простой граф G называется полным, если

1) любые две  различные его вершины являются  смежными;

2) он не  содержит петель.

Ориентированный простой граф G называется полным, если

1) для любой  его вершины есть дуга, концом  которой являются любая другая  вершина;

2) он не  содержит ориентированных петель.

Полный граф, как ориентированный, так и неориентированный, содержащий n вершин, обозначают K n .

Граф G = (V,E) называется дополнительным к графу G = (V,E) с

тем же множеством вершин V , если он содержит все ребра или дуги, которые содержатся в полном графе и не содержатся в графе G.

Граф On , дополнительный к полному графу Kn , называется 0- графом. Легко видеть, что 0-граф O n состоит из n изолированных вершин.

Ориентированный маршрут длины k  в орграфе из v в w в орграфе G=(V,E) – последовательность дуг вида (v,w 1), (w 1, w 2), (w 2, w 3), …, (w k-1,w), т.е. конец каждой дуги, кроме последней, совпадает с началом следующей. Для упрощения маршрут удобно представлять последовательностью вершин, которые его представляют, однако следует помнить об одинаковом направлении дуг, входящих в маршрут: v, e1, e2, e3, …, ek-1,e.

Ориентированная цепь (путь) – это ориентированный маршрут, в котором все дуги различны.

Маршрут называется циклическим, если его начало и конец совпадают.

Циклический путь называется контуром.

Для орграфов понятие связности является более содержательным, чем для  графов. Различают три важных типа связности орграфа:

а) G сильно связный, если для каждой пары различных вершин v,w in V существует маршрут из v в w и обратно.

Б) G односторонне связный , если для каждой пары различных вершин v, w in V существует маршрут из v в w или обратно.

В) G слабо связный, если граф F(G) связный.

 

Теорема Роббинса:

Пусть G— связный граф; он ориентируем тогда и только тогда, если каждое его ребро содержится, по крайней мере, в одном цикле.

Доказательство:

Необходимость условия очевидна. Чтобы доказать достаточность, выберем любой цикл C и ориентируем его ребра в направлении какого-либо обхода этого цикла. Если каждое ребро из G содержится в C, то доказательство завершено; если нет, то возьмем любое ребро e , не принадлежащее C, но смежное некоторому ребру из C. По предположению, ребро e содержится в каком-то цикле C1. Ребрам цикла C1  можно приписать ориентацию в направлении какого-либо обхода этого цикла (за исключением тех ребер, которые уже были ориентированы, то есть тех ребер из C1, которые принадлежат также C). Нетрудно убедиться в том, что описанная процедура за конечное число шагов приведет к сильно связному орграфу.

2. Эйлеров орграф  

Пусть G = (V,E) - связный ориентированный мультиграф. Эйлеровым циклом называется цикл в графе G, который содержит все ребра в графе и каждое только один раз. Эйлеровым графом называется граф, содержащий эйлеров цикл. Эйлеровым путем называется путь в графе G, не являющийся циклом, который содержит все ребра в графе и каждое только один раз. Полуэйлеровым графом называется граф, содержащий эйлеров путь.