Дискретная математика

154 Доказательство теоремы даёт и алгоритм нахождения эйлерового цикла. Для нахождения эйлерового цикла можно построить алгоритм в следующем виде; Алгоритм построения эйлерового цикла: Вход; эйлеров граф G(V,X), заданный списками смежности (i[v] - список вершин, смежных с вершиной v). Выход: последовательность вершин эйлерова цикла. S:~0 {стек для хранения вершин} selectv e F {произвольная вершина} V -> S {положить V в стек S} while8ф0 do V <- S; V->• S {v - верхний элемент стека} if L[v] = 0 then v<r- S; yield v else select и sL[v\ {взять первую вершину из списка смежности} u^S {положить и в стек} i[v];=i[v]\ {и}L[u]:= L[ii]\{v] {удалить ребро (v,u)} end if end while Можно поставить аналогичную задачу для отыскания цепи, начинающейся в некоторой вершине v и заканчиваюш;ейся в другой вершине и, причем содержащей каждое ребро один и только один раз. Теорема 5.18. Для того чтобы на связном графе имелась цепь S(v,u), содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы v я и были единственными вершинами нечетной степени для этого графа. Доказательство. Необходимость. Пусть имеется цепь S(v,u), проходящая по всем ребрам в точности по одному разу. Эта цепь начинается в верш,ине v, возможно, в дальнейшем снова заходит в v, и далее не один раз. Если цепь не заканчивается в v, то эта вершина должна иметь нечетную степень. Аналогично и для и, в то время как все остальные вершины графа должны быть четны. Достаточность. Пусть v я и - единственные вершины с нечётной степенью. Добавим к графу G ребро (v,u), тогда все вершины будут иметь четную степень и согласно теореме 5.17 граф обладает эйлеровым циклом; если из этого цикла удалить ребро (v,u), останется искомая цепь S(v,u). Что и требовалось доказать.