Теоретическая часть. 1. Построение эйлерова цикла1. Построение эйлерова цикла. Необходимым и достаточным условием существования эйлерова цикла в неориентированном графе является чётность степеней всех вершин графа. Если это условие выполнено, то построить эйлеров цикл можно с помощью следующего алгоритма, в котором используются обозначения: C – вспомогательный стек; CE – результирующий стек, содержащий эйлеров цикл; – начальная вершина цикла. Begin ; ; ; ; While do begin ; If then begin ; ; ; ;
End else begin ; End End end. После окончания работы алгоритма стек CE содержит эйлеров цикл. 2. Построение гамильтонова цикла. Так как не существует достаточного условия гамильтоновости графа, то вопрос о существовании гамильтонова цикла решается после попытки его построения. Для построения такого цикла воспользуемся вариантом алгоритма с возвратом. Данный алгоритм использует механизм рекурсии. Обозначим: x – массив, содержащий гамильтонов цикл; Dop – массив логических переменных, означающих возможность использования вершины в цикле. procedure Gamilt (k) Begin For do if () Ù () then вывод массива x и else if then begin ; ; Gamilt (k +1);
End end. Begin for do ; ; ; Gamilt (2) end. Данный алгоритм выводит все существующие гамильтоновы циклы графа.
|