Автор работы: Пользователь скрыл имя, 28 Апреля 2013 в 15:43, лекция
Пути и циклы Эйлера.
Пути и циклы Гамильтона.
Алгоритм Литтла.
Шаг 3. Ветвление.
На самом деле, дуга, соответствующая максимальной степени нуля, может, как входить в гамильтонов цикл, так и не входить в него. Поэтому дальше нужно рассмотреть сразу два случая.
Первый случай. Возможно, дуга вошла в гамильтонов цикл. Блокируем ее, полагая . Строку и столбец вычеркиваем. Если требуется, приводим полученную матрицу меньшего порядка с константой приведения .
Второй случай. Дуга не вошла в гамильтонов цикл. Полагаем . Если требуется, приводим полученную матрицу с константой приведения .
Если , то шаги 2, 3 повторяем с матрицей .
Если , то шаги 2, 3 повторяем с матрицей . И так до тех пор, пока не дойдем до матрицы второго порядка, содержащей два нуля:
где и – некоторые числа или . Эти нули соответствуют двум последним дугам гамильтонова цикла: , . При этом .
Если , где , то задача решена. Если же для некоторого получается , то всю процедуру следует провести с матрицей . На последнем этапе получим новое значение функции : . Это значение сравниваем с , то есть новый процесс продолжается до тех пор, пока новые .