дискретная-математика - Доказательство корректности алгоритма построения Эйлеровых путей

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

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

Другой способ основан вот на какой идее. Как вообще доказывается, что чётных валентностей в связном графе достаточно для эйлеровости? Полезно это вспомнить. В графе есть цикл (циклический подграф) 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), и так далее.