Ответы в темах
-
Сообщения
-
Да, обыкновенный граф – это неориентированный граф без петель и кратных ребер. Теорема вобщем-то ни при чем, просто это более точное условие гамильтоновости. Если все время надо искать полное паросочетание, то алгоритм Куна ищет его за O(n^3). Может быть, сделать какую-нибудь весовую функцию, которая делала бы одни пары более желательными, другие менее желательными, и искать полное паросочетание наименьшего веса? Или так и делают? Венгерский алгоритм делает это за O(n^4). (Все оценки из книги «Дискретная математика: матроиды, графы, алгоритмы» М.О. Асанов, В.А. Баранский, В.В. Расин, http://lib.mexmat.ru/)
Более точное достаточное условие — это теорема Хватала: Если G -обыкновенный граф и d1<= ... <= dn - последовательность степеней вершин графа, то если для всех k верно, что из
dk(т.е. d катое)<=k=n-k, то граф гамильтонов. А Вас, Александр, не удивляет, что системы линейных уравнений, если не ошибаюсь, 11-го порядка не под силу современной вычислительной технике?
Но ведь на решение надо O(n^3) операций умножения и деления, почему им не удается решить системы из 11 уравнений?
