Теоретическая часть. 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
Gamilt (2) end. Данный алгоритм выводит все существующие гамильтоновы циклы графа.
|
– начальная вершина цикла.
; 
; 
; 
;
;
;
;
;
;
; 
) Ù (
)
; 
;
do 
;
; 
;
