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