Алгоритмы изоморфизма многогранного графа (плоского 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 |²) без больших скрытых констант.