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

Question

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

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

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

Answer 1

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

.

• Легко понять: вычислить Системы вращения для g и h в виде побочных продуктов Алгоритм тестирования нормальной связи. Поскольку G и H являются 3-контактными, эти системы вращения изоморфны до взаимодействия по часовой стрелке и против часовой стрелки, если и только тогда, когда G и H являются изоморфными. Выберите DART (= EDGE с указанным направлением) D в G и попробуйте отобразить его на все дротики E в H (и повторите для другой ориентации H). Поскольку G подключен, все остальные DARTS D 'могут быть достигнуты из D, составив две операции системы вращения для G. Примените соответствующие операции на E и проверьте, есть ли изоморфизм.

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

• Хорошие практические характеристики на небольших графиках: после аналории тестирования алгоритм Weinberg в основном два синхронизированных обхода глубины для каждого дротика. Общее время работы равно (| v | ^{2 ) без крупных констант, скрываемых.}