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

 

Теорема Эйлера

1) Граф G является эйлеровым тогда и только тогда, когда все вершины графа имеют четную степень.

Доказательство. Необходимость. Пусть G— эйлеров граф. Эйлеров цикл этого графа, проходя через каждую его вершину, входит в нее по одному ребру, а выходит по-другому. Это означает, что каждое прохождение вершины по циклу вносит слагаемое 2 в ее степень. Поскольку цикл содержит все ребра графа, то степени всех вершин будут четными. 
 Достаточность. Предположим, что степени всех вершин связного графа  G четные. Начнем цепь G1 из произвольной вершины v1, и будем продлевать ее, выбирая каждый раз новое ребро. Так как степени вершин четные, то, попав в некоторую вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро. Таким образом, построение цепи Р1обязательно закончится в вершине v1, и Р1будет циклом. Если Р1содержит все ребра графа G, то построен эйлеров цикл. В противном случае, удалив из G ребра Р1, получим граф G2. Так как степени всех вершин графов G и Р1 были четными, то и G2 будет обладать этим свойством. В силу связности G графы Р1 и G2 должны иметь хотя бы одну общую вершину v2. Теперь, начиная из v2, построим в G цикл Р2 подобно тому, как построили Р1. 
 Объединим циклы Р1 и Р2 следующим образом: пройдем часть Р1 от вершины v1 до вершины v2, затем пройдем цикл Р2, затем — оставшуюся часть Р1 от v2 до v1 (см. рис. 7). 
 

 

Рис. 7 — Связной граф G

 

2) Граф G является полуэйлеровым тогда и только тогда, когда все вершины графа, кроме двух, имеют четную степень. При этом путь начинается в одной вершине с нечетной степенью и заканчивается в другой.

Доказательство этой теоремы начнем с так называемой леммы о рукопожатиях. Название этой леммы связано с тем, что эта лемма отвечает на следующий вопрос: У Вас собрались гости. Некоторые из них здороваются друг с другом посредством рукопожатий. Какими свойствами обладает число таких людей? Ответ дается следующей достаточно простой леммой.

Лемма о рукопожатиях. Число вершин в графе (или мультиграфе без петель), имеющих нечетную степень, четно.

Доказательство  леммы. Заметим, что сумма степеней всех вершин в графе (или мультиграфе без петель) должна быть четной. Это следует из того, что если взять вершины, вообще не связанные друг с другом, то сумма степеней этих вершин равна нулю. Прибавляя любое ребро, которое связывает две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна. Удаляя из этой суммы степени четных вершин, получим, что сумма степеней нечетных вершин, должна быть четной. Это значит, что само число таких вершин должно быть четным. Лемма доказана.

С точки зрения задачи о рукопожатиях это означает, что число гостей, которые поздоровались за руку нечетное число раз, должно быть четным. Перейдем к доказательству теоремы Эйлера.

А) Пусть граф является эйлеровым. Тогда в нем имеется эйлеров цикл, который должен прийти в вершину по одному ребру и покинуть его по другому, так как каждое ребро должно использоваться только один раз (т. е. каждый “заход” в вершину и “выход” из нее дает 2 степени вершины). Таким образом, сумма степеней всех вершин должна быть четной (и равна удвоенному числу “заходов” в эту вершину при обходе эйлерова цикла).

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

 

Рис. 8 – Мультиграф

 

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

Заметим, что по лемме 1 в этом графе есть контур (степень всех вершин больше или равна 2). Если этот контур содержит все ребра, то этот контур сам является эйлеровым циклом (а граф эйлеровым). Удалим все эти ребра из графа и те вершины, которые после удаления ребер стали иметь нулевую степень. Тогда получим новый граф (который может быть несвязным), но в этом новом графе все вершины обязательно имеют четную степень (так как при удалении ребер контура степень каждой вершины, входящей в этот контур, уменьшается на 2). Новый граф распадается на “компоненты связности”, каждая из которых должна иметь общую вершину с удаленным контуром (иначе первоначальный граф не был бы связным), степени всех вершин каждой компоненты связности четны и число вершин в ней строго меньше п, т. е. по индукционному предположению эта компонента имеет эйлеров цикл. Теперь можем построить эйлеров цикл в данном графе следующим образом. Обходим последовательно ребра удаленного контура. Если мы пришли в вершину, общую для контура и какой-то компоненты связности, то обходим по эйлерову циклу эту компоненту, возвращаемся при этом в вершину контура и идем по этому контуру дальше. Тем самым все ребра будут пройдены и каждое только один раз (все это схематично изображено на рис. 9: сначала начинаем обходить контур АВСDEА. Пройдя ребро АВ, проходим “верхний” граф, затем возвращаемся в т. В и далее идем по ребру АС, обходим “правый” граф и т. д.). Утверждение Б доказано.

 

 

 

 

 

 

 

Рис. 9 — Полученный новый  граф

 

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

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

 

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

 

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

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

Гамильтонов цикл не обязательно содержит все  ребра графа. Ясно, что гамильтоновым  может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v₁,…,v_p графа G добавить вершины u₁,…,u_p и множество ребер {(v_i,u_i)}{(u_i,v_i+1)}.

Степенью  вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) — по входящим.

В отличии от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла оказывается NP-полной. Большинство известных фактов имеет вид: «если граф G имеет достаточное количество ребер, то граф является гамильтоновым». 

Теорема Дирака. Если в графе G(V,E) c n вершинами (n ≥ 3) выполняется условие d(v) ≥ n/2 для любого vV, то граф G является гамильтоновым.

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

От противного. Пусть G — не гамильтонов. Добавим к G минимальное количество новых вершин u₁, … ,u_n, соединяя их со всеми вершинами G так, чтобы G’:= G + u₁ + … + u_n был гамильтоновым.

Пусть v, u₁, w, … ,v — гамильтонов цикл в графе G’, причем vG, u1G’, u1G. Такая пара вершин v и u₁ в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда wG, w  {u₁,…,u_n}, иначе вершина u₁ была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u₁ была бы не нужна.

Далее, если в  цикле v,u1,w, … ,u’,w’, … ,v есть вершина w’, смежная с вершиной w, то вершина v’ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v’, … ,w,w’, … ,v без вершины u1, взяв последовательность вершин w, … ,v’ в обратном порядке. Отсюда следует, что число вершин графа G’, не смежных с v, не менее числа вершин, смежных с w. Но для любой вершины w графа G d(w) ≥ p/2+n по построению, в том числе d(v) ≥ p/2+n. Общее число вершин (смежных и не смежных с v) составляет n+p-1. Таким образом, имеем:

n+p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p.

Следовательно, 0 ≥ n+1, что противоречит тому, что n > 0.

Турниром называется орграф, в котором любые две вершины соединены ровно одной дугой.

Рис. 10 — турнир

Основанием для выбора такого названия служит то, что подобные орграфы  можно использовать для записи результатов  теннисных или любых других турниров, в которых не разрешены ничьи. Например, на (рис. 10) представлены результаты турнира, в котором команда Z нанесла поражение команде U , но проиграла команде V, и т.д.

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

ЗАКЛЮЧЕНИЕ

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

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

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

 

 

 

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

1. Дискретная математика: учебно-методическое пособие для слушателей факультета заочного обучения / В.В. Меньших. - Воронеж: ВИ МВД России, 2010. – 155 с.
2. Специальная математика: конспект лекций /А.Е. Соловьев – Пермь: ПГТУ, 2001г.

3. Дискретная математика: булевые функции и элементы теории графов методические указания и контрольные задания./ Е.Л Рабкин,  Ю.Б. Фарфоровская - Санкт-Петербург. Статья Эйлеровы и полуэйлеровы графы, <http://dvo.sut.ru/libr/himath/w163rabk/10.htm >

4. Статья Эйлеровы и гамильтоновы графы,

< http://bestreferat.ru/referat-54029.html#__RefHeading__336_1441090104>