5.4. Все задачи

Задача 5.1: Эйлеровым циклом в графе называется цикл, который проходит по каждому ребру ровно один раз. Что вы можете сказать о задаче поиска минимального по весу эйлерова цикла в полном взвешенном графе? Сводится ли к ней задача поиска (какого-нибудь) эйлерова цикла в произвольном графе, и, если сводится, то как?

Задача 5.2: (Не имеет отношения к теории сложности) Попробуйте придумать и написать геометрическое решение задачи про муравьёв. Оно не требует знания ничего, кроме основных геометрических идей, даже выпуклую оболочку писать не надо уметь :)

Задача 5.3: Докажите, что все эти три задачи сводятся друг к другу.

Дополнительное задание 5.4: (если делать нечего): Напишите переборные решения всех, особенно \(NP\)-трудных, обсуждавшихся выше задач.