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

·

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

GD Star Rating
loading...

похожие публикации

  1. Какой материал отражает лучи?
  2. Какие есть тесты простых чисел общего вида?
  3. Какой сосуд тяжелее?
  4. На это существует какой–то стандарт?
  5. в какой университет поступить ?
Tagged with → •  

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

    1. Zz001:
      19/10/2011 в 12:26

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

      Полиномиальных алгоритмов не известно. Однако не известно принадлежит ли эта задача 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:
      21/10/2011 в 03:08

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

      Ответить
    3. Voev:
      21/10/2011 в 04:00

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

      Ответить
    4. Zz001:
      21/10/2011 в 18:32

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

      Ответить
    5. Zz001:
      21/10/2011 в 18:35

      не за что.

      Ответить

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