Работаю над новой публикацией по теории графов. Для ее написание мне потребовался алгоритм проверки изоморфизма деревьев. Слышал, что существует не просто полиномиальный алгоритм для этой цели, но еще обладающий линейной временной сложностью. Я забил в google «изоморфизм деревьев» и одной из первых ссылок, была следующая: http://dhmmstu.narod.ru/nir/konf/3/hm2.html.
Вроде бы все просто там написано. Размешаем вершины по уровням в зависимости от расстояния от корневой вершины. Далее считаем для каждой вершины ее «отцовый» уровень, т. е. длину максимальной линии потомков, как сказано в статье. И помимо этого считаем список «отцовых» уровней ее сыновей. Для двух деревьев, которые надо проверить на изоморфизм, собирает всю такую информацию о каждой вершины в массив и сравниваем. Если упорядоченные массивы совпали, то деревья изоморфны, если нет, то «не судьба».
В конце, как положено, указан список литературы, где только одна ссылка на известную книгу Ахо, Хопкрофта и Ульмана. Написав код и начав тестировать алгоритм для очередной статьи, прихожу к мнению, что источник неграмотно переписан. Построил такие массивы для двух неизоморфных деревьев, изображенных на рисунке https://pp.vk.me/c636219/v636219902/1dc04/bBdewWZcNVs.jpg.
Ребра первого дерева: (0 1), (0 2), (1 3), (1 4), (2 5), (3 6), (3 7), (4 8), (4 9), (5 10).
Ребра второго дерева: (0 1), (0 2), (1 3), (1 4), (2 5), (3 6), (3 7), (4 8), (5 9), (5 10).
Для каждой вершины указаны соответствующие числа. Массивы совпали, а деревья на самом деле неизоморфны! Их структура действительно разная, это видно невооруженным глазом. Массив следующий: {3, 3, {2, 2}}, {2, 2, {1, 1}}, {2, 2, {1}}, {1, 1, {0, 0}}, {1, 1, {0, 0}}, {1, 1, {0}}, {0, 0, {}}, {0, 0, {}}, {0, 0, {}}, {0, 0, {}}, {0, 0, {}}. Любой желающий может повторить вычисления. Тоже самое мне выдала программа. При этом в книге из списка литературы, из которой якобы был взял алгоритм, никаких «отцовых» уровней не рассматривается. Проделав вычисления по алгоритму из первоисточника результат получил корректный, деревья оказались неизоморфны.
Любопытно, что статья висит в интернете с 2000 года без редактирования, и набрала достаточно высокий рейтинг в поисковиках. Теперь всегда буду пользоваться первоисточниками, которые проходят тщательную рецензию)
