Алгоритмы изоморфизма полиэдрального графа (планарного трехсвязного графа)?

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

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

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


graph algorithm language-agnostic isomorphism polyhedra
person Mike Graham    schedule 14.03.2012    source источник
comment
Надеюсь, что немного лучше. Вы можете рассмотреть возможность перехода на один из наших других сайтов. Я не уверен, что это будет иметь большой оборот здесь ..   -  person    schedule 15.03.2012
comment
Я ценю заботу. Перед публикацией моего вопроса мне пришло в голову, что это может быть не лучший SE, но я не мог придумать более подходящего — мне кажется, что это не теоретическая информатика, это не концептуальный вопрос о разработке программного обеспечения, это не действительно математика и т. д. Можете ли вы посоветовать, на каком сайте, по вашему мнению, это работает лучше всего?   -  person Mike Graham    schedule 15.03.2012
comment
Твоя догадка так же хороша как и моя. Я действительно знаком только с большой тройкой (и программистами), так как это то, с чем я в основном имею дело...   -  person    schedule 15.03.2012

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

person rap music    schedule 17.03.2012
comment
Примечание: вполне возможно, что Хопкрофт и Тарьян |V|log|V| алгоритм сравнительно прост; У меня сейчас нет доступа к их статье. С другой стороны, разница между тестом планарности с линейным временем и тестом планарности с квадратичным временем заключается в некоторых причудливых структурах данных, поэтому, если вы пишете тест самостоятельно, вы можете согласиться и на квадратичное время. - person rap music; 18.03.2012