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

задан 28 Дек '16 17:54

изменен 28 Дек '16 18:36

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

Вообще, если здесь имеется в виду алгоритм Флёри построения эйлерова цикла в графе, то он очень понятно изложен в популярной книге Р.Уилсона "Введение в теорию графов".

(28 Дек '16 18:17) falcao

@falcao , добавил ссылку на источник

(28 Дек '16 18:36) explicit

@explicit: я сейчас попробую разобраться, но хочу сказать об одной вещи. Вы в прошлый раз поместили формулировку леммы, где говорится про "напечатанный путь P". Он печатается конкретной программой, которая описана в цитируемой статье. Ясно, что вне контекста никто даже в страшном сне не предположит, что такое P, что печатается, и так далее. Поэтому такие вещи надо пояснять сразу же, и чувствовать, что без этих пояснений никто ничего не поймёт.

(28 Дек '16 21:00) falcao
10|600 символов нужно символов осталось
2

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

Есть достаточно классический алгоритм Флёри, который описан в литературе. Если мы вручную строим цикл, то это удобная вещь. Но при машинной реализации там надо хранить в памяти кое-какие данные. Напомню, что принцип алгоритма такой: идём по графу как угодно, стирая пройденные рёбра. Граф всё время должен оставаться связным. Для этого мы не должны ходить по "мостам" текущего графа, если есть другая возможность. Проверка того, что этот способ приводит к успеху, изложена в литературе. Недостаток в том, что на каждом шаге надо проверять ребро на предмет того, будет ли оно мостом, что не слишком удобно.

Другой способ основан вот на какой идее. Как вообще доказывается, что чётных валентностей в связном графе достаточно для эйлеровости? Полезно это вспомнить. В графе есть цикл (циклический подграф) C, и если его удалить, то чётность валентностей сохранится, но граф может перестать быть связным. Допустим, он как-то разбит на связные компоненты Г(1), ... , Г(m), где m>=1. Каждая такая компонента эйлерова по предположению индукции. Кроме того, каждая компонента имеет хотя бы одну общую вершину с циклом. Выберем по одной такой вершине v(i) для каждого i, и перенумеруем компоненты так, чтобы в цикле эти вершины шли по порядку номеров. Тогда цикл в исходном графе Г строится так: идём по рёбрам C, пока не попадём в v(1). После этого обходим Г(1), и далее идём из v(1) в v(2). И так далее, пока не придём "домой".

Нетрудно заметить, что это стандартное рассуждение работает и тогда, когда циклический подграф C заменить на любой цикл, в котором вершины могут повторяться. Тогда возможен тот алгоритм, который описывается по ссылке: мы запоминаем в стеке проходимые вершины, а пройденные рёбра удаляем. Может так оказаться, что мы пришли куда-то, откуда выйти не можем. Тогда это начальная вершина v, что ясно из соображений валентности. Если мы обошли все рёбра, то конструкция готова. Допустим, что мы обошли не все рёбра. Тогда в какой-то момент мы не туда свернули, досрочно придя "домой". Надо это место отыскать. Из сказанного выше мы знаем, что существует эйлеров цикл, который оканчивается путём из v(m) в v по рёбрам C. Эти переходы у нас хранятся в стеке, и мы оттуда их можем постепенно извлекать, печатая последние сделанные ходы справа налево. При этом нам надо найти момент, где у нас была та вершина, которая в описании значится как v(m). Это сделать легко, потому что это самая верхняя из вершин стека, в которой у нас имелась альтернатива.

Найдя эту вершину, мы начинаем обходить Г(m). Это эйлеров граф, и мы по рекурсии можем сделать вывод, что тот же алгоритм даст нам эйлеров цикл в этом графе. А именно, рано или поздно мы вернёмся в v(m), когда у нас из этой вершины не будет выхода. Тогда извлекаем вершины из стека до тех пор, пока не встретим вершину, в которой мы могли пойти ещё по какому-то ребру. Всё, что было до неё, допечатываем справа налево как "окончательное", а потом продолжаем делать то же самое.

То, что этот алгоритм корректен, следует из построения, а также из ссылки на рекурсию. Граф Г(m) эйлеров, алгоритм даст нам его обход. Мы при этом снова окажемся в v(m), и далее идём назад по рёбрам цикла C, доставая вершины из стека и допечатывая их, пока не окажется в v(m-1), и так далее.

ссылка

отвечен 28 Дек '16 23:39

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,068
×655
×396
×166
×99

задан
28 Дек '16 17:54

показан
502 раза

обновлен
28 Дек '16 23:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru