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

     Начнем  новый путь s из   и используем только ребра, не принадлежащие L. Этот путь кончится в  . На рисунке путь s обозначен прямыми линиями со стрелками.

       Объединим теперь оба цикла:  из   пройдем по пути L к  , затем по циклу s и, вернувшись в  , пройдем по оставшейся части пути обратно в  . Если снова найдутся ребра, которые не вошли в путь, то найдем новые циклы.

     Так как число ребер и вершин конечно, то процесс закончится.

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

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

3.3.Решение задач о лабиринтах

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

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

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

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

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

Приведём геометрическую постановку задачи о лабиринтах.

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

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

Решение:

         Правило 1. Отправляемся от выбранной вершины (первого перекрестка) и идем по любому ребру, пока не приходим или в тупик (к вершине), или к новому перекрестку (вершине).

     Тогда: Если окажется, что мы попали в тупик, возвращаемся назад и пройденное ребро должно быть уже отброшено, так как мы прошли его два раза (туда и обратно). Если приходим к  новому перекрестку, то направляемся по новому произвольному ребру, не забывая всякий раз отмечать путь, по которому прибыли, и путь, по которому отправились дальше. (Как показано на рисунке 10.) 
 
 

 Пример.

 рис 10.

Направление движения показано стрелкой  f. После прихода к пересечению путей выбирается направление, обозначенное стрелкой g. Оба пути помечаются черточкой. (Крестиками обозначаются черточки, поставленные при последнем прохождении через перекресток.)

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

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

 рис 11. 

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

 рис 12.

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

 рис 13. 

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

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

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

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

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

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

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

Пусть, наконец, мы будем  вынуждены закончить путь и вернуться  в начальный перекресток  ,. Обозначим это ребро  ( , ) , то есть оно ведет из перекрестка   в начальный  . Этот путь должен быть тем самым, которым мы отправлялись первый раз из  , иначе путь можно было бы продолжать. И если теперь мы принуждены этим же путем возвратиться в начальную точку (вершину), то это значит, что из перекрестка    нет никакого другого пути, который бы не был уже два раза пройден. Иначе это означало бы, что забыли применить первую часть правила 3, более того, это означало бы, что в    есть какой-то путь ( , ), пройденный только один раз по замечанию 4. Итак, при последнем возвращении в   все пути в   должны быть отмечены двумя черточками. Точно так же это можно доказать для предыдущего перекрестка  , и для всех остальных. Другими словами, предположение доказано, и задача решена. 
 
 

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

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

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

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

     На  рис. 14 изображены гамильтонов, полугамильтонов и не гамильтонов графы.

Рис 14.

Несмотря на сходство постановки задач для гамильтоновых  графов с эйлеровыми, “хорошего” решения  для гамильтоновых графов нет. Вообще, о гамильтоновых графах известно очень мало. В основном – это  теоремы типа “если в графе  достаточное число ребер, то он гамильтонов”. Ясно, что теоремы такого типа не могут дать критерия гамильтонова графа, (рис. 14,а), поскольку в графах такого типа вершин может быть очень много, а ребер сравнительно мало. 
 
 
 
 

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

       Рассмотрим известную задачу о «кругосветном путешествии».

В 1859 г. сэр Вильям Гамильтон, знаменитый ирландский математик, давший миру теорию комплексных чисел и кватерниона, предложил детскую головоломку, в которой предлагалось совершить «кругосветное путешествие» по 20 городам, расположенным в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b ... t (рис. 15).

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

Рис. 15.

     Если  путешествие начать из города a, то последними должны быть города b, e или h, иначе мы не сможем вернуться в первоначальный пункт a. Непосредственное исчисление показывает, что число таких замкнутых маршрутов равно 60.

     Можно потребовать посещения всех городов  строго по одному разу, включая и  первый, т.е. допускается окончание  путешествия в любом городе (например, предполагается, что в начальный  пункт можно будет вернуться самолетом). Тогда общее число цепных маршрутов увеличится до 162. В табл.1 перечислены все эти цепи, причем в специально организованной последовательности. Принцип организации цепей для додекаэдра выбран тот же, что и ранее для куба, т.е.принцип инверсии хвостовой последовательности вершин. Однорёберная замена касается 1, 4, 7, 10, 13 или 16 ребра каждой цепи. Таким образом, получается 11 циклов по 15 цепей в каждом и 3 цикла по 14 цепей.

                              Таблица 1. 
 
 
 
 
 
 
 
 

      Рассматривая табл.1, можно заметить, что ни один из предложенных дорожных маршрутов не заканчивается в пунктах c, d, f, g, i и j. В пункте t заканчиваются только 6 маршрутов, в пунктах m, p и s — по 8 для каждого пункта, в l, k, n, o, q, r — по 12 и в b, e, h — по 20.

     Это происходит потому, что для додекаэдра существует пять классов вершин и  семь классов ребер, которые в  табл.1 количественно разнесены по 11 циклам.

В столбце S табл.1 указана симметрия цепи, которая для додекаэдра определяется так же, как и для куба. Общее число цепей додекаэдра равно произведению 162 × 10 = 1620.  

  3.3. Достаточное условие гамильтоновости графа .Теорема     Дирака.