Алгоритмы изоморфизма многогранного графа (плоского 3-связного графа)?

Question

Я провел некоторое исследование на тему изоморфизма графов для плоских 3-связных графов, но существует множество алгоритмов с различными ограничениями, теоретической сложностью и частотой использования, и у меня возникают проблемы с поиском подходящего алгоритма.

• Легко понять
• Может быть реализовано с максимальной наглядностью
• Хорошая практическая производительность на небольших графиках (вплоть до вершин в десятках)

Трудно понять, не понимая сами разные алгоритмы, лучше ли мне использовать один из более старых, более специализированных алгоритмов для этой проблемы или более новые, более общие. Из всех возможных кандидатов, какой / какие из них являются наиболее подходящими?

Answer 1

Я думаю, что алгоритм Вайнберга отвечает всем требованиям.

• Легко понять: вычислите системы вращения для G и H как побочные продукты алгоритма проверки планарности.Поскольку G и H 3-связны, эти системы вращения изоморфны с точностью до взаимной замены по часовой стрелке и против часовой стрелки тогда и только тогда, когда G и H изоморфны.Выберите дротик (= ребро с указанным направлением) d в G и попробуйте сопоставить его со всеми дротиками e в H (и повторите для другой ориентации H).Поскольку G подключен, все другие дротики d 'могут быть достигнуты из d, составив две операции системы вращения для G. Примените соответствующие операции к e и проверьте, существует ли изоморфизм.

• Максимальная ясность: помимо теста на плоскостность, выше приведена страница кода.Может быть, вы могли бы повторно использовать чужой тест на планарность?Например, в Boost есть один.Если нет, то я все еще думаю, что реализовать свой собственный легче, чем переписать nauty.

• Хорошая практическая производительность на небольших графах: после тестирования плоскостности алгоритм Вайнберга в основном представляет собой два синхронизированных обхода в глубину для каждогодротик.Общее время работы O (| V | ² ) без больших скрытых констант.