Лекция 5. Эйлеровы пути и циклы. Критерий существования. Оценки сложности (1162201)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Методы дискретной оптимизацииЭйлеровы пути и циклы. Критерийсуществования эйлеровых путей. Оценкисложности задачи построения эйлеровогоцикла1 / 17Эйлеровы циклы. Задача китайского почтальонаОпределение.Цикл, содержащий все ребра графа, называется эйлеровым. Графназывается эйлеровым, если в нем существует эйлеров цикл.Напомним, что цикл, по определению, не содержит повторяющихся ребер.Таким образом, эйлеров цикл проходит по всем ребрам графа ровно поодному разу. Именно о таком маршруте спрашивается в задаче окенигсбергских мостах.

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

Сейчас мыограничимся решением задачи китайского почтальона в частном случае, вкотором в качестве модели достаточно использовать обычный граф.Если граф эйлеров, то один из эйлеровых циклов является оптимальныммаршрутом китайского почтальона. В следующей теоремеустанавливается связь между степенями вершин связного графа иналичием эйлерова цикла в нем. Считаем, что при наличии петли степеньвершины учитывается дважды.3 / 17Теорема ЭйлераТеорема 1 (Эйлера)Граф без изолированных вершин является эйлеровым тогда и толькотогда, когда он связен и степени всех его вершин четны.Доказательство. Необходимость Пусть G – эйлеров граф безизолированных вершин, в нем существует цикл, проходящий через всеребра графа.

Тогда каждая вершина инцидентна хотя бы одному ребруэтого цикла, а значит, данный цикл проходит по всем вершинам.Следовательно, любые две вершины в G соединены маршрутом,являющимся частью эйлерова цикла, т. е. G связен. Осталось доказать,что степени всех вершин графа G четны. Пусть v – произвольнаявершина. Обходя граф по эйлерову циклу, мы зайдем в вершину v столькоже раз, сколько выйдем из нее. При этом каждое инцидентное v реброиспользуется либо только для захода в v, либо только для выхода из v, заисключением петель, которые используются и для захода, и для выхода.Поскольку при подсчете степени вершины каждая петля учитываетсядважды, а остальные ребра (учитываемые по одному разу) разбиваютсяна пары «входящее ребро – исходящее ребро», степень v должна бытьчетной.4 / 17Теорема ЭйлераПродолжение.Достаточность Возьмем связный граф G, в которомстепени всех вершин четны, и построим в нем эйлеров цикл.

Если в Gесть петли, то можно: либо удалить петли (связность графа и четностьстепеней вершин не нарушатся) и построить эйлеров цикл вполучившемся графе, либо встроить петли в построенный цикл, получаяэйлеров цикл в исходном графе. Поэтому в дальнейшем мы считаем, что вG нет петель. Пусть v0 произвольная вершина графа G. Так как v0 неизолированная, можно построить цепь с началом в v0 ; построим ее,выбирая ребра e1 , e2 , . . . произвольно и остановившись в момент, когдацепь нельзя продолжить (т.

е. все ребра, инцидентные вершине, в которуюмы попали, уже включены в цепь). Поскольку число ребер в графеконечно, мы остановимся через конечное число шагов. Пусть намипостроена цепь e1 , . . . , ek , проходящая по вершинам v0 , . . . , vk . Докажем,что vk = v0 , т. е. мы построили цикл. Предположим, что vk не совпадает сv0 . Тогда, проходя всю цепь от v0 к vk , мы сколько-то раз, скажем, l раз,входили в вершину vk и l − 1 раз из нее выходили, причем все ребра, покоторым мы входили и выходили, различны. Таким образом, впостроенной цепи ровно 2l − 1 ребер, инцидентных vk .

Поскольку степеньвершины vk четна, то существует инцидентное vk ребро, не входящее вцепь, что противоречит построению цепи. Следовательно, vk = v0 .5 / 17Теорема ЭйлераПродолжение. Обозначим цикл, образованный ребрами e1 , . . . , ek , черезC1 (см. рис. 1).Рис. 1Если он эйлеров, построение закончено. Пусть C1 не эйлеров, т. е. в графеG1 = G\{e1 , . . . , ek } есть ребра. Cреди этих ребер есть инцидентноевершине цикла C1 , так как в противном случае C1 – компонентасвязности графа G, не совпадающая со всем графом, что противоречитсвязности G. В графе G1 , так же как и в исходном графе G, степени всехвершин четны.

Действительно, при удалении ребер e1 , . . . , ek степенькаждой из вершин v0 , . . . , vk уменьшилась на четное число, а степениостальных вершин не изменились.6 / 17Теорема ЭйлераОкончание доказательства. Рассмотрим компоненту связности графаG1 , содержащую ребро f1 . Внутри этой компоненты связности можно,начав с вершины vi , построить цикл C2 , состоящий из ребер f1 , . . . , fm , темже способом, которым был построен цикл C1 . Тогда последовательностьребер e1 , .

. . , ei , f1 , f2 , . . . , fm , ei+1 , . . . , ek также образует цикл (обозначимего C2 ) и этот цикл содержит больше ребер, чем C1 . Если цикл C2эйлеров, построение закончено. В противном случае повторим описанноевыше рассуждение, расширив цикл C2 до цикла C3 , и т. д. Посколькучисло ребер в G конечно, на каком-то шаге очередной построенный циклокажется эйлеровым. Построение завершает доказательство.7 / 17ПримерПример.

В классической задаче Эйлера о Кенигсбергских мостахтребуется определить маршрут, который начинается и заканчивается водной и той же точке суши и проходит по каждому из семи мостов ровноодин раз (Рис. 2).Рис. 28 / 17ПримерГраф, соответствующий схеме мостов, определяется следующим образом:часть суши соответствует вершине, ребро соответствует мосту (Рис. 3).Построенный мультиграф не удовлетворяет условию теоремы 1, поэтомуискомый маршрут не существует.Рис.

3Приведенное доказательство достаточности в теореме Эйлера являетсяконструктивным, т. е. содержит алгоритм построения эйлерова цикла.Для практического нахождения эйлерова цикла часто пользуются немногодругим алгоритмом, формальное определение которого приведено ниже.9 / 17Алгоритм Флери1. Положить текущий граф равным G, а текущую вершину равнойпроизвольной вершине v ∈ V (G).2. Выбрать произвольное, с учетом ограничения (см. ниже) ребро eтекущего графа, инцидентное текущей вершине.3. Назначить текущей вторую вершину, инцидентную e.4.

Удалить e из текущего графа и внести в список.5. Если в текущем графе еще остались ребра, вернуться на шаг 2.Ограничение алгоритма: если степень текущей вершины в текущем графебольше 1, нельзя выбирать ребро, удаление которого из текущего графаувеличит число компонент связности в нем.10 / 17Алгоритм Флери. ПродолжениеДля учета указанного ограничения приведенного формального описаниянедостаточно для полной формулировки алгоритма. Данный алгоритм вболее подробном описании соответствует алгоритму поиска в глубину,отличие от поиска в глубину здесь состоит в том, что вместо вершин какпройденные помечаются ребра. Вершины могут посещаться несколько раз,но каждое ребро проходится не более одного раза, так что в полученноммаршруте ребра не будут повторяться.

Для учета ограничения алгоритмаопределим пару стеков S1 , S2 . Сначала исходя из начальной вершины x1последующие вершины пути накапливаются в первом стеке S1 слеванаправо в соответствии с последовательностью посещения вершин:S1 = {x1 , x2 , . . . , xk1 }. Последняя вершина xk1 стека является тупиковой –все ребра, инцидентные xk1 , уже пройдены. Так как степени всех вершинграфа четны, в этот момент пройденные ребра образуют цикл, но онможет включать не все ребра графа. Для обнаружения еще непройденных ребер возвращаемся по пройденному пути, перекладываявершины из стека S1 в стек S2 = {xk1 , xk1 −1 , .

. . , xp1 +1 }, пока не встретимвершину xp1 , которой инцидентно непройденное ребро. В стеке S1останутся вершины {x1 , x2 , . . . , xp1 }. Так как граф связен, такой номерp1 < k1 обязательно встретится.11 / 17Алгоритм Флери. ПродолжениеИсходя из точки xp1 движение вперед по непройденным ребрамвозобновляется, при этом в стеке S1 будут находиться вершины{x11 , x12 , ..., x1p1 , x21 , x22 , ..., x2k2 }, где x1l = xl , l = 1, 2, ..., p1 , точки x2l , l = 1, ..., k2не были пройдены ранее, точка x2k2 тупиковая. Далее повторяютсярассуждения проведенные выше и процесс заканчивается, когда вочередном тупике обнаруживается, что стек S1 пуст.

В этот момент встеке S2 находится последовательность вершин эйлерова цикла.Пример. Пусть V = {1, 2, 3, 4, 5},E = {(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (4, 5)}. Последовательность шагов:S1 = {(1, 2), (2, 3), (3, 1)} ⇔ S1 = {1, 2, 3, 1} ⇒ 1 – тупиковая вершина.Полагаем S2 = {1, 3, 2, 4, 5, 2}, S1 = ∅ ⇒ S2 – искомый эйлеров цикл.12 / 17Алгоритм Флери. Теорема о корректностиТеорема 2Алгоритм корректно определяет последовательность ребер и строитэйлеров цикл в эйлеровом графе.Доказательство. Из способа построения стеков следует, что во второйстек содержит только те вершины, из которых не выходят ребра.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций