Ура!
Короче я вот
спросил на форуме TopCoder'a, и там
ulzha родил гениальную мысль.
Вот полученная им цепочка рассуждений:
1. Представим все возможные числа на доминошках - вершинами в графе, а сами доминошки - ребрами. Теперь перед нами стоит задача построения самого длинного замкнутого маршрута, проходящего через каждое ребро не больше 1 раза, а через каждую вершину - произвольное кол-во раз.
2. Пусть в графе n вершин и m ребер. Добавим к каждой вершине цикл длины m+1, т.е. m новых, фиктивных вершин.
Получится, что, если в начальном графе существовал замкнутый маршрут, проходящий через каждую вершину как минимум один раз, то в новом графе, дополненном циклами, обязательно существует маршрут длины большей, чем n*(m+1) - ведь из каждой вершины мы можем пройтись по ее дополнительному циклу.
Понятно, что верно и обратное утверждение: получить в новом графе маршрут длины большей, чем n*(m+1), можно *только* посетив каждую вершину оригинального графа как минимум один раз.
3. M. R. Garey, D. S. Johnson и R. Endre Tarjan
показали, что поиск гамильтонова цикла в планарном, кубическом, 3-связном графе является NP-полной задачей.
4.
Кубический граф - такой, у которого степень каждой вершины равна 3. Получается, замкнутый маршрут в таком графе не может побывать в какой-нибудь вершине больше одного раза - ведь это означало бы, что ее степень - как минимум 4.
5. Сведем это воедино.
- Рассмотрим кубический, планарный, 3-связный (n, m) граф. Добавим к каждой вершине цикл длины m+1.
- Найдя такой цикл, мы однозначно сможем определить (критерий - ребер в найденном цикле больше n(m+1)), существует ли в изначальном графе цикл, проходящий через каждую вершину как минимум 1 раз; если существует, то мы его уже построили - просто удаляем фиктивные ребра из ответа
- В кубическом графе никакой цикл не может проходить в какую-нибудь вершину больше 1 раза, поэтому фактически мы научились строить гамильтонов цикл (в случае его существования)
- Итак, мы свели NP-полную задачу к исходной, т.е. показали, что, умея решать задачу про доминошки за полиномиальное время, научимся решать за такое же время NP-полную задачу.
Браво,
ulzha!