Первая итерация. Начнем с вершины 1 как начальной вершины строящейся цепи S, и попробуем добавить к S, например, вершину 6, так что цепь So будет {1, 6}.

Шаг 1 описанного метода удалит тогда из G дуги (1,2), (1,3), (1,10), (2,6).

Шаг 2 укажет теперь вершину 10, как имеющую полустепенб захода 1 и дающую возможную цепь S = {4,10}, после чего

Рис. 10.4. Граф из примера разд. 2.3.1.

удаляется дуга (4,2). Второе применение шага 2 дает вершину 2 с полустепенью захода 1 и возможную цепь 2 = {3,2}, после чего удаляются дуги (3,12), (3,5) и (3,4). Третье применение шага 2 даст вершину 4 с полустепенью захода 1 и приводит к продолжению цепи Si после добавления дуги (11,4), так что цепь Si есть теперь {11,4,10}. В силу шага 2 дуга (11,9) удаляется, и то же относится к дуге (10,11), замыкающей цепь Si. Четвертое применение шага 2 не приводит к дальнейшим удалениям, и первый редуцированный граф, получающийся в конце шага 3, показан на рис. 10.5а, где цепи So, Si и S2 изображены жирными линиями.

Вторая итерация. Так как существует более чем одна цепь и так как полустепени захода и исхода всех вершин ненулевые.

то мы продолжаем расширять цепь дальше. Пусть, например, из множества Г (е {S )) = {8,5,7} выбрана вершина 8, так что цепь So превратится в цепь {1, 6, 8}. Шаг 1 даст теперь вершину 5, обе полустепени которой равны 1, и вершину 1 с полустепенью захода, равной 1. Взяв сначала вершину 5 и сделав два раза шаг

Рис. 10.5а. Первый редуцированный граф Gf.

2, придем к добавлению дуг (2,5) и (5,13) для расширения цепи Si, которая превращается теперь в {3, 2, 5, 13}. Дуги (2, 13), (12,13) и дуга возврата (13, 3) удаляются ). Второе применение шага 2 дает вершину 3 с полустепенью захода 1, а также вершину 1 (с полустепенью захода 1), полученную на предыдущем этапе. Взяв вершину 3, добавим к 2 дугу (12, 3), после чего получим цепь {12, 3, 2, 5, 13} и удалим дугу (12, 11). Третье применение шага 2 все еще дает вершину 1 с полустепенью захода 1 и больше не дает никаких вершин. К цепи So добавляется дуга (9,1), цепь So превращается в {9, 1, 6, 8}, а дуги (9, 7), (9,14) и дуга возвра-

) Здесь термин дуга возврата используется в несколько ином смысле, чем на стр. 255: эта дуга замыкает не гамильтонову, а некоторую промежуточную цепь.- Прим. ред.

та (8,9) удаляются. Четвертое применение шага 2 укажет две вершины 9 и 7 с полустепенями захода 1. Взяв сначала вершину 9, добавим дугу (10,9), соединяюш;ую цепи Si п So ъ дающую новую цепь So = {И, 4, 10, 9, 1, 6, 8}. Дуга (10, 7) удаляется.

Рис. 10.56. Граф Gl после четвертого применения шага 2 на второй итерации.

Пятое применение шага 2 дает вершину 7 с полустепенью захода 0. Это говорит о том, что описанный поиск не может привести ни к какому гамильтонову циклу.

Граф Gj, получающийся в конце четвертого применения шага 2, показан на рис. 10.56. Теперь следует восстановить все удаленные во время второй итерации дуги, чтобы вернуться к графу Gi из рис. 10.5а, и произвести операцию возвращения, т. е. удалить из Sg вершину 8, заменить ее другой возможной вершиной (5 или 7) и продолжать применять шаги 1, 2, 3 и т. д.

Из приведенного примера видно, что это очень сильный метод поиска. После двух итераций он позволяет сделать вывод, что никакой гамильтонов цикл не может содержать в качестве своей части цепь {1, 6, 8}. Это 1/12 всех попыток поиска, поскольку полустепень исхода вершины 1 равна 4, а вершины 6 - 3. Конечно, указанный вывод относится только к части графа, изображенной на рис. 10.4, которая сама может принадлежать к намного большему графу. Можно поэтому ожидать, что при заданном