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

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

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

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

Теорема 4.4. Если граф $$G$$ связный и $$v_{a}$$ и $$v_{b}$$ единственные нечетные вершины его, то граф $$G$$ обладает эйлеровым путем с концами $$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. Если связный граф $$G$$ имеет $$2k$$ нечетных вершин, то найдется семейство из $$k$$ путей, которые в совокупности содержат все ребра графа в точности по одному разу.

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

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

Пример.

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

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

Лабиринты

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда:

Пример.

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

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

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

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

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

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

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

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