Условия, при которых граф эйлеров.

Теорема 4-1 (Эйлера). Конечный неориентированный граф G эйлеров тогда и только тогда, когда он связан и сте­пени всех его вершин четны.

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

Теперь нужно доказать достаточность этих условий. Пусть G — конечный неориентированный граф с четными степенями всех вершин. Начнем построение эйлерова цикла с произвольной вершины v графа G. Каждый раз, когда мы добавляем к маршруту новое ребро и приходим в новую вершину, число свободных ребер в этой вершине изменяется на единицу. Если до этого оно было четным, то теперь оно становится нечетным и не может оказаться нулем. После ухода из этой вершины число свободных инцидентных ей ребер уменьшается еще на единицу и вновь становится четным. Исключением является исходная вершина, у ко­торой после начала процесса число свободных ребер не­четно и остается нечетным после каждого возвращения в эту вершину и ухода из нее.

Описанный ранее процесс построения цикла может за­кончиться лишь в той вершине, откуда он начинался, но при этом не обязательно, чтобы он проходил через все ребра графа. Принадлежащие ему ребра порождают связ­ную часть Р графа G, в которой степени всех вершин четны. Значит, они четны и для разности G \ Р. Так как граф G связан, в дополнении G \ P существует хотя бы одна вер­шина v', принадлежащая также части Р. Начиная с этой вершины, можно провести, как и ранее, построение цикла Р' в G \ Р, кончающегося также в вершине v'.

Эта вершина, кроме того, разбивает цикл Р на два уча­стка: Р₁ с началом v и концом v' и Р₂ с началом v' и концом v. Тогда P₁ U Р' U P₂— также цикл, начинающийся и кон­чающийся в вершине v, но имеющий большее число ребер. Если и этот цикл не проходит через все ребра, этот процесс расширения цикла можно повторить. Каждый раз число ребер в цикле увеличивается не менее чем на два, значит, в конце концов, эйлеров цикл будет построен. D

В графе задачи о Кенигсбергских мостах (рис. 4-10) все вершины имеют нечетную степень. Следовательно, ее ре­шение невозможно.

Эйлеровы цепи. Так называется цепь, включающая все ребра данного конечного неориентированного графа G, но имеющая различные начало v' и конец v". Чтобы в графе существовала эйлерова цепь, необходимы его связность и четность степеней всех вершин, кроме начальной v' и ко­нечной v". Последние две вершины должны иметь нечетные степени: из v' мы лишний раз выходим, а в v" лишний раз входим. Эти условия достаточны для существования эйле­ровой цепи. Доказательство — то же самое, как и для условий, достаточных для существования эйлерова цикла.

Можно искать наименьшее число не пересекающихся по ребрам цепей, покрывающих конечный связный граф G. Пусть G не является эйлеровым графом, k — число его вер­шин нечетной степени. Ранее было доказано, что k — четно. Каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих цепей. Следовательно, число последних не меньше чем k/2. Но ограничиться k/2 цепями не так трудно. Соединим вершины нечетной степени попарно k/2 ребрами произвольным образом. Тогда степень каждой из этих вершин увеличится на единицу и станет четной. Получится эйлеров граф, в котором существует эйлеров цикл. Выбросим теперь обратно присоединенные ребра. При выбрасывании первого ребра эйлеров цикл превратится в эйлерову цепь, а при выбрасывании каждой следующей одна из возникших к этому моменту цепей разо­бьется на две части. Таким образом, общее число этих цепей станет равно k/2.

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

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

Алгоритм обхода ребер графа. Так называется алгоритм построения цикла, проходящего через каждое ребро по одному разу в каждом из двух направлений. Пусть все вершины графа G занумерованы и для каждой вершины i задан список E_i инцидентных ей ребер е_i,1, e_i,2,......, , причем число l_i ребер в этом списке также указано. Обход начинаем, например, с первой вершины и заводим счетчики v_i коли­чества обойденных уже ребер, указатели первого входа в каждую вершину i графа и указатели , соответствующие ребрам графа G. Если ребро еще не пройдено или пройдено только в одном направле­нии, то = 0, в противном случае = 1. Вначале v_i = = = 0. Пусть мы стоим в i-й вершине, по ребру пришли в нее и прошли

это ребро только в одном направлении, но остальным ребрам совершен обход в обоих направлениях, и для них указатели = 1. Кроме того, могут быть еще некоторые отмечен­ные и пройденные в обоих направлениях ребра , причем , также равны единице. Если v_i < l_i то проверяем, не отмечено ли ребро и прибавляем к счетчику v_i единицу.

Когда = 0, т. е, (v_i + 1)-е ребро списка E_i свободно, мы идем по нему вперед и попадаем во вторую инцидентную этому ребру вершину j. В противном случае пробуем пойти вперед по следую­щему ребру этого списка, т. е. снова проверяем, что v_i < l_i затем — свободно ли следующее (v_i + 1)-е ребро, прибавляем к счетчику v_i единицу и т. д.

Кроме того, все время надо проверять, не равно ли v_i + 1 , т. е. не стоит ли следующим в списке ребро, по которому мы первый раз пришли (в результате шага вперед) в вершину i. Хотя в этом случае тоже равно нулю, идти вперед по этому ребру не следует.

Его надо пропустить и перейти к следующему ребру. Таким образом обеспечивается единственность шага вперед по любому ребру. Когда v_i станет равно l_i, убеждаемся, что все инцидентные рассматриваемой вершине i ребра, кроме -го в списке E_i, были пройдены в обоих направлениях. По этому последнему ребру следует возвратиться в вер­шину h, из которой мы впервые попали в i-ю вершину — сделать шаг назад. При этом рассматриваемое ребро перестает быть свободным, т. е. делаем равным единице.

Если в вершину i мы вернулись в результате шага назад по некото­рому ребру, то стоим в этой вершине и начинаем описанный ранее процесс поиска ребра, по которому можно было бы сделать шаг вперед. Если же мы попали в рассматриваемую вершину в результате шага вперед, нужно еще проверить, не были ли в ней раньше. В последнем случае (v_i > 0) немедленно возвращаемся по тому же ребру и отмечаем его — делаем шаг назад.

Когда же в результате шага, вперед попадаем в вершину j, в которой не были раньше (такую вершину мы будем называть новой), то прежде всего находим ребро прихода в ее списке E_j, запоминаем его номер в этом списке и пытаемся сделать из нее шаг вперед, т. е. стоим в вер­шине j. В любом случае мы можем сделать следующий шаг вперед или назад, если только не выполняются условия i=1, v₁ = l₁. В этом последнем случае, как будет показано далее, обход ребер графа G закон­чен. Так как каждый шаг алгоритма — это шаг вперед или назад по свободному ребру, т. е. такому ребру, что до этого шага по нему не делался соответственно шаг вперед или назад, число ша­гов обхода конечно. Порядок обхода ребер графа показан на рис. 4-11.

Пусть мы впервые попали в вершину i. Множество шагов обхода после этого момента и до того, как из этой вершины будет сделан шаг назад по причине равенства v_i = l_i, или до конца обхода, если такой шаг назад не производится, будем называть i-й частью обхода ребер. Лабой шаг этой части — это либо шаг вперед из вершины i или вершины j, которая впервые рассматривается в i-й же части обхода, либо шаг назад по тому ребру, по которому только что был сделан шаг вперед, в вершину j, впервые рассматриваемую в i-й части обхода, либо, нако­нец, шаг назад в вершину i или вершину j, также впервые рассматриваемую в этой части обхода. Это доказывается при помощи индукции по числу k шагов i-й части рбхода.

При k = 0 утверждение справедливо, так как мы стоим в вершине i. Пусть оно справедливо на всех шагах, включая (k — 1)-й (k > 0). Если этот шаг был шагом назад из старой вершины, в которую мы только что попали, то по индуктивному предположению на (k — 2)-м шаге мы стояли в вершине i или в вершине j, впервые рассматриваемой в i-й части обхода. Действительно, (k — 2)-й шаг был шагом вперед, причем k 2 (перед первым шагом i-й части мы стоим в вершине i, причем попали в нее впервые). Следовательно, на k-м шаге мы стоим там же, где были и на (k — 2)-м, т. е. в вершине i или впервые рассмат­риваемой в i-й части обхода вершины j; k-й шаг будет шагом вперед или назад из этой вершины.

Если (k — 1)-й шаг был шагом вперед, то после него мы попадаем либо в новую вершину, либо в старую, из которой немедленно надо вернуться назад, и индуктивное предположение выполняется. Наконец, когда (k — 1)-й шаг был шагом назад из вершины j после того, как все

остальные инцидентные этой вершине ребра были пройдены в обоих направле­ниях, то по индуктивному предположению вершина j впервые рассматривалась в i-й части алгоритма и шаг вперед в нее был сделан из вершины i или некоторой вер­шины h, также впервые рассмотренной в этой части обхода. Значит, на k-м шаге мы стоим опять в вершине i или h и инду­ктивное предположение выполняется. Таким образом, оно выполняется на всех шагах i-й части обхода.

Рис. 4-11.

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

В конце обхода мы опять стоим в вершине 1 и не можем сделать шага вперед, т.е. пройдены в обоих направлениях все инцидентные ей ребра.

Рассмотрим множество вершин, в которых мы стояли по ходу алго­ритма. Из каждой из них был произведен шаг назад (кроме начальной вершины 1), значит, в этот момент все инцидентные ей ребра несвободны, т. е. пройдены в обоих направлениях. Кроме того, в другие вершины, инцидентные этим ребрам, мы когда-нибудь попадаем в ходе алгоритма. Следовательно, эти вершины также принадлежат рассматриваемому множеству, т. е. последнее состоит из всех вершин связного подграфа конечного графа G, содержащего вершину 1, а когда G — связный граф, — из всех его вершин. В этом случае все ребра графа G будут пройдены по одному разу в обоих направлениях, что и требовалось доказать.

Задача о выходе из лабиринта. В качестве примера при­менения описанного ранее алгоритма можно привести за­дачу о поиске выхода из лабиринта. Его дорожки можно рассматривать как ребра некоторого графа G, точки раз­ветвления этих дорожек, начальное положение попавшего в этот лабиринт и выход из него — как вершины этого графа (рис. 4-12).

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

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

Рис, 4-12.

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

На рис. 4-13 изображены граф с гамильтоновым циклом (рис. 4-13, а) и циклически связный граф, в котором нет гамильтонова цикла (рис. 4-13, б). В последнем, чтобы пройти через вершины, расположенные внутри сторон тре­угольника ABC, гамильтонов цикл должен содержать все лежащие на этих сторонах ребра. Но тогда он не проходит через расположенную в центре треугольника вершину 0.

Иногда можно построить проходящую через все вер­шины графа простую цепь с началом и концом в различных заданных вершинах v', v" G. Такая цепь тоже называется гамилыпоновой.

Дата добавления: 2015-07-08