Друзья, какой есть адекватный алгоритм определения изоморфизма графов?
GD Star Rating
loading...
loading...
5 Responses to Какой есть адекватный алгоритм определения изоморфизма графов?
Добавить комментарий Отменить ответ
Обсуждения в блоге
- ДОБРО ПОЖАЛОВАТЬ В НАУКУ!
- блогерс, кто может дать радиометр погонять на денёк?
- про IR лазеры теперь, чтоб те долго жили.
- Не уверен, что чисто алгебраические задачи будут тут уместны, но всё же.
- Швейцарские и грузинские археологи обнаружили в ходе раскопок человеческий череп, который доказывает, что уже 1,8 миллиона лет назад все люди, живущие на земле, принадлежали к одному и тому же виду приматов —
- Суббота.
- Господа, у меня своеобразный вопрос.
- Пару недель назад мы с каналом «Наука 2.
- Друзья, объясните мне пожалуйста, чем отличается альфа частица 3.
- Байты и биты.
А интересует теория или практика по данному вопросу? Если теория, то ситуация такова.
Полиномиальных алгоритмов не известно. Однако не известно принадлежит ли эта задача NPC. Лучший точный алгоритм работает за e^{\sqrt{n * log(n)}}, и он довольно сложен.
Существующие алгоритмы:
1. O(n^2) – — работает для почти всех графов (он детерминированный, ошибка на некоторых входах).
2. e^{\sqrt{n * log(n)}} – — кто автор точно не помню, идея основана на алгоритме Симса для изоморфизма групп.
3. Алгоритм Вейсфейлера–Лемана, есть экспоненциальная нижняя оценка, но на практике работает не плохо.
//logic.pdmi.ras.ru/csclub/courses/…
Собственно здесь есть все, что я перечислил. В том числе и ссылки на некоторые практические алгоритмы.
Оу, спасибо огромное бро! Не ожидал такого удовольствия!
а тупо поиск с возвратом не подойдет?
аля перебираем подстановки, и если какая–то часть подстановки не подходит, то не проверяем все подстановки с данной частью.
можно конечно, только работать скорее всего будет не очень быстро.
Например на регулярных графах.
не за что.