Теория графов

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

CОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………………….…..3-4

1. Глава 1. Граф и его элементы………………………………………..……6-11

           §1.1 Основные понятия…………………………………………………6-7

           §1.2  Ориентированный граф…………………….………………………..8

           §1.3   Неориентированный граф………………….…………………….…8 

           §1.4  Смежность………………………………….………………..……9-10

           §1.5  Маршруты и пути…………………………………….…………10-11

2. Глава 2.  Гамильтоновы  графы……………………………………...……12-19

           §2.1  Основные определения и результаты……………...…………..12-15

           §2.2  Условия существования гамильтонова цикла…………….…..16-17

           §2.3  Теорема Дирака…………………………………………………18-19

3. Глава 3.  Применение  гамильтоновых графов…………………………..20-30

          §3.1  Задачи коммивояжера: сущность и применение на практике..20-24

          §3.2 Методы решения задачи коммивояжера………………….....…24-26

          §3.3  Задачи и их решения………………………………..…………...27-30

ЗАКЛЮЧЕНИЕ……………………………………………………………….…31

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

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

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

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

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

Первая работа по теории графов, принадлежавшая Эйлеру, появилась в 1736 году и была связана  с решением задачи о Кёнигсбергских мостах. Однако, эта работа Эйлера была единственной в течение почти ста лет. Вначале теория графов казалась незначительным разделом математики, так как имела дело лишь с математическими развлечениями и головоломками, например, задача о расстановке ферзей на шахматной доске, задача о перевозках, задача о кругосветном путешествии и др. Развитие математики и ее приложений послужило сильным толчком к развитию теории графов. Уже в середине ХIХ века графы использовались при построении схем электрических цепей и молекулярных схем.

Впервые термин «граф» ввел в 1936г. венгерский математик  Денеш Кёниг. В его работе теория графов была представлена как отдельная  математическая дисциплина, находящая  в настоящее время широкое  применение в автоматике, телемеханике, кибернетике, электронике, физике, экономике, психологии, биологии и других областях науки.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цель:

1.  Ознакомление с основными понятиями, связанными с гамильтоновыми графами и циклами.  Рассмотреть задачи и методы отыскания гамильтоновых циклов в графах.

.

Задачи:

Для достижения поставленной цели необходимо решить следующие задачи:

-охарактеризовать понятие и особенности графов;

-ознакомиться с практическим применением графов;

-изучить основные понятия и результаты гамильтоновых и полугамильтоновых графов;

- рассмотреть условия существования гамильтонова цикла;

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

 

 

 

 

 

Глава 1. Граф и его элементы.

 

§1.1  Основные понятия.

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

Геометрически граф можно представить как набор  вершин (точек), определенные пары которых соединены линиями.  
 
Например, сеть дорог, соединяющая города Е1, Е2, Е3, Е4, Е5 можно представить в виде графа следующим образом: города обозначим точками (вершинами), а дороги неориентированными линиями (рис.1)  
 
Неориентированные линии означают наличие двустороннего движения между соответствующей парой городов. Пересечения линией не считаются вершинами.  
 

Рис.1. Граф сети дорог

 

Рассмотрим  другой пример: 
Пусть производственный участок изготовляет два вида изделий Е9 и Е10. Изделие Е9 собирается из узлов Е6, Е7 и детали Е2, а изделие Е10 – из узлов Е7, Е8 и детали Е5. В свою очередь узел Е6 собирается из двух деталей Е1 и одной детали Е2, узел Е7 – из деталей Е2, Е3 и Е5, а узел Е8 – из деталей Е4 и Е5. Применяемость узлов и деталей изобразим в виде графа. Вершинами графа поставим в соответствие узлы, детали и изделия, а связи между ними (вхождение деталей в узлы и изделия и узлов в изделия) изобразим ориентированными линиями (рис. 2.)  
 

Рис.2. Граф производственного участка

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

 
В зависимости от наличия или  отсутствия ориентации у пар элементов из множества V различают графы:

1. ориентированные,
2. неориентированные (реберные),
3. смешанные.

 

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

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

Рис.3. Ориентированный граф

 

§1.3  Неориентированный граф

В неориентированном графе отношения симметричны, то есть (u, v) = (v, u). В неориентированном графе нет дуг, связи называют ребрами.

                                           Рис. 4 Неориентированный граф

 

 

 

 

 

 

 

§1.4 Смежность

 

Пусть V1, V2 - вершины, е = (V1, V2) - соединяющее их ребро (рис.5.). Тогда вершина V1 и ребро е инцидентны , вершина V2 и ребро е также инцидентны.  
 
   

 Рис.5 Смежные вершины

 

Две вершины называются смежными, если они соединены ребром/дугой (рис.5)  

Два ребра называются смежными, если они соединены вершиной/узлом (рис.6).  
 

Рис.6. Смежные ребра

Смежные вершины - две вершины, инцидентные одному ребру.

 

Смежные ребра – два ребра, инцидентные одной вершине. 

Множество вершин, смежных с вершиной V, называется множеством смежности вершины V и обозначается Г+(V) (рис. 7).  
 

Рис.7. Множество смежности

 

§1.5 Маршруты и пути

 

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

 

Маршрут в графе – чередующаяся последовательность вершин и ребер.

 

Эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним (рис.8)  
 

Рис.8 Граф для иллюстрации маршрутов

Указанный маршрут  соединяет вершины Vo и Vn, и его можно обозначить Vo,V1,V2,..,Vn (наличие ребер подразумевается).  
Эта последовательность иногда называется (Vo-Vn) - маршрутом.  
Маршрут замкнут, если Vo = Vn, и открыт в противном случае.

Цепь  – маршрут с различными ребрами.

 

Простая цепь-маршрут с различными вершинами (а значит, и ребрами).

 

Цикл- замкнутая цепь.

 

В помеченном графе G на рис.1 V1,V2,V4,V5,V3 - маршрут, который  не является цепью, а V1,V2,V5,V4,V2,V3 - цепь, где V1,V2,V5,V4 - простая цепь и V2,V4,V5,V2 - простой  цикл.  
 
Обозначим через Gn граф состоящий из одного простого цикла с n вершинами, и через Pn простую цепь с n вершинами. Gn часто называют треугольником. 

 

 

 

 

 

 

 

 

 

 

 

Глава 2. Гамильтоновы графы

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

 

 

§2.1. Основные определения и результаты

 

 

Рис. 9

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

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

 

Замечание.

 

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,…, vp графа G добавить вершины u1, …, up и множество ребер {(vi, ui)} {(ui, vi+1)}.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Примеры:

 

Ясно, что такая  цепь должна быть циклом, исключая тривиальный  случай, когда   является графом  . Если такой цикл существует, то он называется гамильтоновым циклом (путем), а   называется гамильтоновым графом. Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым. Название "гамильтонов цикл" возникло в связи с тем, что Уильям Гамильтон занимался исследованием существования таких циклов в графе, соответствующем додекаэдру. Додекаэдр — это многогранник, гранями которого служат 12 правильных пятиугольников. У него   вершин и   ребер.

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

Критерий же существования гамильтонова цикла в произвольном графе еще не найден. Решение этой проблемы имеет практическую ценность, так как к игре Гамильтона близка известная задача о коммивояжере, который должен объехать несколько пунктов и вернуться обратно. Он обязан побывать в каждом пункте в точности по одному разу и заинтересован в том, чтобы затратить на поездку как можно меньше времени. А для этого требуется определить все варианты посещения городов и подсчитать в каждом случае затрату времени. По своей математической постановке игра Гамильтона близка к задаче о порядке переналадки станков, задаче о подводке электроэнергии к рабочим местам и т.д. (Подробнее об этом рассказывается, например, в книге В.И.Мудрова "Задача о коммивояжере" М.: Знание, 1969).

Рассмотрим  несколько достаточных условий существования гамильтоновых циклов в графе.

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

Пример.

 

Простой (гамильтонов) цикл выделен сплошной линией  ,  , ,  ,  . Заметим, что если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы.

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

 

§2.2 Условия существования гамильтонова цикла.

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

 

Теорема (Дирак, 1952) 1. Если в простом графе с n ≥ 3 вершинами p(v) ≥ n/2 для любой вершины v, то граф G является гамильтоновым.

 

Теорема (Оре) 2. Если число вершин графа G(V, E) n ≥ 3 и для любых двух несмежных вершин u и v выполняется неравенство:

d(u) + d(v) ≥ n и (u, v) E, то граф G — гамильтонов.

Граф G имеет гамильтонов цикл если выполняется одно из следующих условий:

Условие Бонди: из d(vi) ≤ i и d(vk) ≤ k => d(vi) + d(vk) ≥ n (k ≠ i)

Условие Хватала: из d(vk) ≤ k ≤ n/2 => d(vn-k) ≥ n - k.

Далее, известно, что почти все графы гамильтоновы, то есть

 

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