задача про домино, поиск наибольшей замыкающейся последовательности Опции

[Zenon]

Здравствуйте.
Поставили перед нами такую задачe. Дано n кубиков домино, как известно они имеют номера с двух сторон, но в задаче сказано, что для данного случая они не ограничены цифрой 6, т.е. значения с обеих сторон могут быть боле 6, например 16 и 12 и т.п. (какие - то разумные пределы конечно есть, но просто больше чем в настоящих, т.е. чем 6). Задние состоит в том, чтобы найти самую длинную замкнутую цепочку.... Если честно теряюсь в догадках и по вопросу алгоритма и по вопросу реализации....
Надеюсь на Вашу помощь.

[Michael_Rybak]

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

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

При этом, если граф изначально несвязный, рассматриваем каждую компоненту связности отдельно.

EDIT: удалил неправильные мысли

Сообщение отредактировано: Michael_Rybak - 9.10.2006 10:31