Замкнутый и незамкнутый варианты задачи

В замкнутом варианте задачи коммивояжёра требуется посетить все вершины графа, после чего вернуться в исходную вершину. Незамкнутый вариант отличается от замкнутого тем, что в нём не требуется возвращаться в стартовую вершину.

Незамкнутый вариант задачи сводится к замкнутому путём замены весов дуг, входящих в стартовую вершину, на число 0. Оптимальный замкнутый маршрут коммивояжёра в таком графе соответствует оптимальному незамкнутому маршруту в исходном графе.

Чтобы свести замкнутый вариант к незамкнутому, нужно определить число , строго превосходящее вес любого маршрута коммивояжёра в заданном графе (например, в качестве можно взять сумму максимальных по весу дуг, выходящих из каждой вершины, увеличенную на 1). Затем нужно добавить к графу новую вершину (предполагаем, что вершины исходного графа пронумерованы числами от 0 до , при этом стартовая вершина имеет номер 0). Стоимости дуг, выходящих и входящих в вершину , определяются следующим образом:

• 

• 

• при от до

Оптимальный незамкнутый маршрут коммивояжёра в таком графе соответствует оптимальному замкнутому маршруту коммивояжёра в исходном графе и имеет стоимость на больше.

Вопросы:

1. Какие задачи на графы вы знаете?

2. Что такое задача о Кёнигсбергских мостах?

3. Кто первый предложил решение этой задачи?

4. Возможно ли пройти по всем мостам не посетив ни один из них дважды?

5. Что такое задача о четырех красках?

6. Есть ли формальное доказательство того, что требуемая задачей раскраска возможна?

7. Правда ли, что на основе задачи были разработаны игры?

8. Что такое задача о коммивояжере?

9. Сколько вариантов задачи вы знаете?

10. К какому классу задач она относится (по временной сложности)?