Друзья, какой есть адекватный алгоритм определения изоморфизма графов?

GD Star Rating
loading...

5 Responses to Какой есть адекватный алгоритм определения изоморфизма графов?

  1. Zz001:

    А интересует теория или практика по данному вопросу? Если теория, то ситуация такова.

    Полиномиальных алгоритмов не известно. Однако не известно принадлежит ли эта задача NPC. Лучший точный алгоритм работает за e^{\sqrt{n * log(n)}}, и он довольно сложен.

    Существующие алгоритмы:
    1. O(n^2) – — работает для почти всех графов (он детерминированный, ошибка на некоторых входах).
    2. e^{\sqrt{n * log(n)}} – — кто автор точно не помню, идея основана на алгоритме Симса для изоморфизма групп.
    3. Алгоритм Вейсфейлера–Лемана, есть экспоненциальная нижняя оценка, но на практике работает не плохо.

    //logic.pdmi.ras.ru/csclub/courses/…
    Собственно здесь есть все, что я перечислил. В том числе и ссылки на некоторые практические алгоритмы.

  2. Voev:

    Оу, спасибо огромное бро! Не ожидал такого удовольствия!

  3. Voev:

    а тупо поиск с возвратом не подойдет?
    аля перебираем подстановки, и если какая–то часть подстановки не подходит, то не проверяем все подстановки с данной частью.

  4. Zz001:

    можно конечно, только работать скорее всего будет не очень быстро.
    Например на регулярных графах.

  5. Zz001:

    не за что.

Добавить комментарий