Эйлеровы и гамильтоновы графы

Содержание

Введение ………………………………………………………........................... 3

Глава 1. Основные  понятия теории графов.

1.1.Понятие графа …………………………………………...…………………. 4

1.2.Маршруты, пути  и циклы в графах ………………….  ………………….5

1.3.Подграфы ………………………………………………................................7

1.4.Степень вершины графа ………………………………………………….8

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

2.1.Эйлеров путь. Полуэйлеров граф. Эйлерова цепь …………………..10

2.2.Признак Эйлеровости графа …………………………...………………..12

2. 3.Решение задач о лабиринтах ………………………………………...…………………….14

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

3.1.Гамильтонов путь. Полугамильтонов граф …………………………..20

3.2. Задача о «Кругосветном путешествии» ………………………………..22

3.3.Необходимое условие гамильтоновости графа.

 Теорема     Дирака ………………………………………...............................28

Список литературы ……………………………………………...................... 30 
 
 
 
 
 
 
 
 

Введение.

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

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

Глава 1. Основные понятия теории графов

1.1.Понятие графа.

          Граф G – пара (V,X), где V конечное непустое множество, содержащее p вершин, а Х-множество,  содержее q неупорядоченных пар различных вершин из V.

Каждую пару X={u,v} вершин в Х называют ребром графа G и говорят, что Х соединяет u и v.Мы будем писать X=uv и говорить, что u и v – смежные вершины. Вершина u и ребро Х инцидентны, так же как v и Х. Если два различных ребра X и Y инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами  называется (p;q)- графом.

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

     

Рис. 1.

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

1.2.Маршруты, пути и циклы в графах.

         Маршрут в графе – это последовательность соседних (смежных) вершин.

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

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

      Рассмотрим примеры. 1)На рисунке 1 жирными линиями показан  путь из точки А в точку В, который мы можем записать так: (AEDB). Другой путь из А в В показан пунктирными линиями, его можно записать как (l₁l₂l₃). Заметим, что может существовать несколько путей из одной точки в другую.

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

На рисунке 1 циклами являются следующие пути: (AEFDA), (EFBCADE). 

     Контур  – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

Последовательности  вершин (рис. 2): 1–2–3–4–2–5 не простой  путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.

 рис 2.

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

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

       рис. 3

1.3.Подграфы

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

     Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

На рис.4 изображены граф G и три его подграфа H₁, H₂ и H₃, среди которых H₃ является остовным, a H₂ — порожденным.

Рис 4.

Важный класс  подграфов составляют подграфы, полученные в результате удаления вершин. Пусть v — вершина графа G. Граф G_v = G — v получается из графа G в результате удаления вершины v и всех инцидентных ей ребер. Очевидно, что         G_v = G(VG\v). На рис.5 изображен подграф G — 5, полученный из графа G, представленного на рис.4, удалением вершины 5. 

 рис 5.

1.4.Степень вершины графа.

      Степенью (или валентностью) вершины графа G называется число инцидентных ей ребер, т. е. число вершин в ее окружении. Будем обозначать степень вершины v через deg G_v (или deg v). Тем самым deg v= |N(v)|.

      Максимальная  и минимальная степени вершин графа G обозначаются символами ∆(G) и δ(G) соответственно:| 

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

      Вершина степени 0 называется изолированной, вершина степени 1 — концевой (или висячей).

        Ребро, инцидентное концевой вершине, также называется концевым.

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

      Рассмотрим  сумму степеней всех вершин графа. Каждое ребро вносит в эту сумму 2, поэтому верно

      Утверждение  («лемма о рукопожатиях»). Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер:

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

      Следствие. В любом графе число вершин нечетной степени четно.

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

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

2.1.Эйлеров путь. Полуэйлеров граф. Эйлерова цепь.

     Рассмотрим  известную задачу о Кёнигсберских мостах: город Кёнигсберг расположен на островах, можно ли совершить прогулку по городу, пройдя по каждому мосту только один раз?(на рисунке 6 приведена схема города.) В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

Рис 6.

На упрощённой схеме  части города (графе) мостам соответствуют  линии (рёбра графа), а частям города — точки соединения линий (вершины  графа).

  рис 7

   В ходе рассуждений  Эйлер пришёл к следующим выводам:

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

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

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

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

Примеры.

 рис 8.

2.2.Признак Эйлеровости графа.

          Теорема 1. Если граф G обладает эйлеровым циклом, то он является связным, а все его вершины — четными.                             Доказательство: Связность графа следует из определения эйлерова цикла. Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз эйлеров путь приведет конец карандаша в вершину, столько и выведет, причем уже по другому ребру. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: одно результат подсчета входов в вершину, другое — выходов.

     Верно и обратное утверждение.

Теорема 2. Если граф G связный и все его вершины четные, то он обладает эйлеровым циклом.

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

Пример.

 рис 9.

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

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

     На  рисунке путь L и направление его обхода показаны кривыми со стрелками.

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

       Если остались непройденные ребра,  то должна существовать вершина   , принадлежащая L и ребру, не вошедшему в L. Так как   — четная, то число ребер, которым принадлежит   и которые не вошли в путь L, тоже четно.