Vovik » 17 мар 2005, 00:23
Никакого перебора! Эйлеров цикл строится по следующему алгоритму:
1. Проверяем критерий Эйлера (к-во слов начинающехся с данной буквы равно к-ву слов на эту букву заканчивающихся + от для любой буквы (из тех что стоят в начале какого-то слова) можно построить цепочку слов, заканчиваищююся в любой другой такой букве). Т.е. граф связный и в каждую вершину входит столько ребер, сколько выходит (граф ориентированный).
2. Если граф (слова) удовлетворяют критерию, то можно построить такой цикл! Всегда! (это знают не только студенты мехмата
). Делаем по следующему алгоритму:
а) любой буквы и идем в любую другую (не используя дважды одно слово), из той буквы в другую и т.д. пока не прийдем к начальной (обязательно прийдем, можно доказать !).
б) Получили некий цикл, если он включает все ребра, то он искомый, если нет, ищем в этом цикле вершину из которой выходят неиспользованые ребра (буква, с которой начинаются неисп. слов). Повторяем для нее п. а). новый получившийся цикл "подшиваем" к уже построенному, повторяем п. б)
Болие подробно см. в литературе про Эйлеров цикл. Для ответа на поставленный вопрос сам цикл строить не нужно, достаточно проверить критерий 1.
Никакого перебора! Эйлеров цикл строится по следующему алгоритму:
1. Проверяем критерий Эйлера (к-во слов начинающехся с данной буквы равно к-ву слов на эту букву заканчивающихся + от для любой буквы (из тех что стоят в начале какого-то слова) можно построить цепочку слов, заканчиваищююся в любой другой такой букве). Т.е. граф связный и в каждую вершину входит столько ребер, сколько выходит (граф ориентированный).
2. Если граф (слова) удовлетворяют критерию, то можно построить такой цикл! Всегда! (это знают не только студенты мехмата :) ). Делаем по следующему алгоритму:
а) любой буквы и идем в любую другую (не используя дважды одно слово), из той буквы в другую и т.д. пока не прийдем к начальной (обязательно прийдем, можно доказать !).
б) Получили некий цикл, если он включает все ребра, то он искомый, если нет, ищем в этом цикле вершину из которой выходят неиспользованые ребра (буква, с которой начинаются неисп. слов). Повторяем для нее п. а). новый получившийся цикл "подшиваем" к уже построенному, повторяем п. б)
Болие подробно см. в литературе про Эйлеров цикл. Для ответа на поставленный вопрос сам цикл строить не нужно, достаточно проверить критерий 1.