Гамильтонов цикл Докажите: если есть эффективный алгоритм для определения существования H C, то есть эффективный алгоритм поиска

Question

Пусть G (V, E) - неориентированный граф. Гамильтонов цикл - это цикл, который посещает каждую вершину v из G ровно один раз (кроме первой вершины, которая также является последней вершиной в цикле).

Предположим: существует эффективный алгоритм, который определяет, имеет ли граф гамильтонов цикл (возвращает True \ False). Давайте назовем это alg ' D для Определить .

• Доказать: существует эффективный алгоритм, который возвращает гамильтонов цикл.

Моя попытка ответа

Assume D(G) = true

Let G'=G (Define G' a copy of G).

For each edge e in E:

    G' = G' \ {e}           // Remove e from G.

    d_boolean = D(G')       // Run D alg' on the new Graph.

    if d_boolean = false
        then G' = G' U {e}  // restore e to graph (because e must be in the Hamiltonian Cycle)

    // else d_boolean=true we do nothing because e is not an edge on the Hamiltonian Cycle

Return G'

Мой вопрос

Как видите, у меня есть идея алгоритм, чтобы показать, что он существует. Я чувствую, что это правильное направление ... Но как мне доказать, что этот алгоритм действительно возвращает гамильтонов цикл?

Answer 1

В вашем псевдокоде отсутствует только один элемент: не гарантируется, что цикл G имеет цикл Гамильтона.

Так что вам нужно пройти первую проверку, прежде чем делать что-либо еще, что гарантирует, что он имеет цикл Гамильтона.

If not D(G):
    Return No_Hamilton_Cycle!

Во-вторых, алгоритм возвращает a цикл Гамильтона (не ) : в G может быть много альтернативных циклов Гамильтона, но порядок, в котором вы пытаетесь удалить ребра, определяет, какой из этих конкурирующих циклов Гамильтона вы, наконец, получите.

С помощью указанного выше дополнения вы можете быть уверены, что в начале и в конце каждой итерации G 'имеет цикл Гамильтона: либо итерация удалит ребро и подтвердит, что G' все еще имеет цикл Гамильтона, либо что удаление отменено, так что состояние G 'такое же в конце, как и в начале этой итерации.

Когда l oop завершится, вы знаете, что:

1. G 'имеет цикл Гамильтона, потому что это было верно в конце последняя итерация
2. Нет ребра, которое вы можете удалить из G ', и у вас все еще есть цикл Гамильтона, потому что вы пытались удалить все эти ребра без успеха. Конечно, иногда у G 'все еще были другие ребра в этот момент попытки, но это не имеет значения: если ребро необходимо для наличия цикла Гамильтона в G', то оно все еще важно после того, как вы удалили некоторые другие существенные ребра.
3. Этот алгоритм не добавил и не удалил ни одного узла: G 'имеет те же узлы, что и G
4. Этот алгоритм не добавил никаких ребер: набор ребер G' является подмножество ребер G (возможно, равное ему).

Из этих пунктов можно сделать вывод, что если G имеет цикл Гамильтона, то G ' является циклом Гамильтона группы G.

Answer 2

Я не эксперт в формальных доказательствах, поэтому я просто приведу некоторые замечания, которые могут быть полезны.

• Инвариант для вашего для l oop - это то, что G 'всегда содержит гамильтонов цикл гамильтониана l oop равен V + 1. Так что, если вы можете доказать, что в конце l oop есть ровно V + 1 ребер, все готово. (Я не думаю, что это легко с предоставленным вами алгоритмом, но, возможно, это может быть с некоторой незначительной модификацией)

• Если вы можете формально доказать факт восстановления грани тогда и только тогда, когда необходимо для наличия гамильтонова цикла, чем сразу же, что в конце l oop не будет ребер, не являющихся частью цикла