INTUIT.ru::Интернет-Университет Информационных Технологий

Интернет-Университет Информационных Технологий

http://www.INTUIT.ru

Графы и их применение

4. Лекция: Эйлеровы графы
Эйлеровы графы. Лабиринты. Геометрическая постановка задачи о лабиринтах. Решение задачи о лабиринтах.

Эйлеровы графы

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

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

Примеры.

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

Задачи с эйлеровыми графами часто встречаются в книгах по занимательной математике — например, можно ли нарисовать какую-нибудь диаграмму, не отрывая карандаша от бумаги и не проходя никакую линию дважды. Название "эйлеров" возникло в связи с тем, что Эйлер первым решил знаменитую задачу о Кенигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на рисунке, эйлерову цепь (не имеет!).

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

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

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

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

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

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

Пример.

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

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

Так как число ребер конечно, этот путь должен окончиться, причем в вершине $v_{a}$ . На рисунке путь и направление его обхода показаны кривыми со стрелками.

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

Если остались непройденные ребра, то должна существовать вершина $v_{b}$ , принадлежащая и ребру, не вошедшему в .

Так как $v_{b}$ — четная, то число ребер, которым принадлежит $v_{b}$ и которые не вошли в путь , тоже четно. Начнем новый путь из $v_{b}$ и используем только ребра, не принадлежащие . Этот путь кончится в $v_{b}$ . На рисунке путь обозначен прямыми линиями со стрелками. Объединим теперь оба цикла: из $v_{a}$ пройдем по пути к $v_{b}$ , затем по циклу и, вернувшись в $v_{b}$ , пройдем по оставшейся части пути обратно в $v_{a}$ .

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

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

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

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

Теорема 4.3. Если граф обладает эйлеровым путем с концами $v_{a}$ и $v_{b}$ $(v_{a}$ не совпадает с $v_{b})$ , то граф является связным, и $v_{a}$ и $v_{b}$ — единственные нечетные его вершины.

Доказательство Связность графа следует из определения эйлерова пути. Если путь начинается в $v_{a}$ , а заканчивается в другой вершине $v_{b}$ , то $v_{a}$ и $v_{b}$ — нечетные, даже если путь неоднократно проходил через $v_{a}$ и $v_{b}$ . В любую другую вершину графа путь должен был привести и вывести из нее, то есть все остальные вершины должны быть четными.

Верно и обратное.

Теорема 4.4. Если граф связный и $v_{a}$ и $v_{b}$ единственные нечетные вершины его, то граф обладает эйлеровым путем с концами $v_{a}$ и $v_{b}$ .

Доказательство Вершины $v_{a}$ и $v_{b}$ могут быть соединены ребрами в графе.

Пример.

А могут быть и не соединены.

Если $v_{a}$ и $v_{b}$ соединены ребром, то удалим его. Тогда все вершины станут четными. Новый граф, согласно предыдущей теореме, обладает эйлеровым циклом, началом и концом которого может служить любая вершина. Начнем эйлеров путь в вершине $v_{a}$ и закончим его в вершине $v_{a}$ . Добавим ребро ( $v_{a}\,v_{b}$ ) и получим эйлеров путь с началом в $v_{a}$ и концом в $v_{b}$ .

Если $v_{a}$ и $v_{b}$ не соединены ребром, то к графу добавим новое ребро ( $v_{a}$ , $v_{b}$ ), тогда все вершины его станут четными. Новый граф, согласно предыдущей теореме, обладает эйлеровым циклом. Начнем его из вершины $v_{a}$ по ребру ( $v_{a}$ , $v_{b}$ ). Закончится путь тоже в вершине $v_{a}$ . Если теперь удалить из полученного цикла ребро ( $v_{a}$ , $v_{b}$ ), то останется эйлеров путь с началом в $v_{b}$ и концом в $v_{a}$ или с началом в $v_{a}$ и концом в $v_{b}$ .

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

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

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

Половину нечетных вершин обозначим $v_{1}, v_{2}\dts v_{k}$ , а другую половину — $w_{1}, w_{2}\dts w_{k}$ .

Пример.

Если вершины $v_{i},w_{i}$ $(1\le i\le k)$ соединены ребром, то удалим из графа ребро ( $v_{i},w_{i}$ ). Если вершины $v_{i}, w_{i}$ не соединены ребром, то добавим к ребро ( $v_{i},w_{i}$ ). Все вершины нового графа будут четными, то есть в новом графе найдется эйлеров цикл. При восстановлении графа цикл разобьется на отдельных путей, содержащих все ребра графа.

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

Лабиринты

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

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

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

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

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

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

Разработаны алгоритмы, позволяющие обойти любой лабиринт, не пользуясь его схемой.

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

Геометрическая постановка задачи о лабиринтах

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

Но еще раньше, чем приступить к этому доказательству, можно выполнить довольно интересное математическое построение, которое поможет понять все вышеизложенное и будет весьма полезно для усвоения самого доказательства. На листе бумаги возьмите произвольно несколько точек и соедините их по две столько раз, сколько хотите, произвольным числом прямых или кривых линий, но так, чтобы ни одна точка системы не осталась изолированной. Итак, получается граф. Если нарисовать сеть трамваев или троллейбусов города, сеть железных дорог страны, сеть рек и каналов и т.д., прибавить к ним, границы страны — опять получается граф, или лабиринт. В данном лабиринте нужно выбрать какую-то вершину $v_{a}$ и обойти все ребра два раза (пройти каждое ребро вперед и назад) и возвратиться в точку $v_{a}$ .

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

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

Тогда:

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

Пример.

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

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

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

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

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

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

Выходя из точки отправления $v_{a}$ , ставим начальный знак (поперечную черточку).
Прохождение через перекресток по одному из предыдущих трех правил каждый раз добавляет два знака (две поперечные черточки) на линиях, которые сходятся в этой точке.
В любой момент прохождения лабиринта, перед прибытием на какой-либо перекресток или после отправления из него, начальный перекресток (пункт отправления) имеет нечетное число знаков (черточек), а всякий другой перекресток имеет их четное число.
В любой момент, до или после прохода через перекресток, начальный перекресток имеет только один путь, обозначенный только одной черточкой. Любой другой из посещенных уже перекрестков может иметь только два пути, обозначенных одной черточкой.
После полного обхода лабиринта у всех перекрестков все пути должны иметь по две черточки. Это, впрочем, входит в условие задания.

Приняв во внимание все вышеизложенное, убеждаемся, что если кто-либо отправляется из начального перекрестка, скажем $v_{a}$ , и прибывает в какой-либо иной перекресток $v_{m}$ , то он не может встретить таких трудностей задачи, которые могли бы остановить его дальнейшее путешествие. В самом деле, в это место он приходит или новым путем, или путем, который уже один раз пройден. В первом случае прилагается первое или второе из приведенных выше правил. Во втором случае вход на перекресток $v_{m}$ и остановка здесь дала бы нечетное число знаков около него, следовательно, за неимением нового пути надо пойти по уже пройденному один раз пути, и около перекрестка будет четное число знаков (если он не начальный) по замечанию 3.

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