Как найти биекцию по заданным изоморфным графам?

Question

Предположим, что данные два мультиграфа изоморфны.
Как можно найти биекцию между ними?

Я знаю, что трудно найти граф изоморфизма, так как это проблема NP.
Но что, если они уже являются изоморфными графами?

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

Замечания:

1. ссылка: http://www.dharwadker.org/tevet/isomorphism/
2. multi-graph позволяет выполнять самоконтроль и multi-edge.

Answer 1

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

Доказательство от противоречия: Предположим, вы могли. Затем, учитывая любые два графика, предположим, что они изоморфны (даже если это не так), и запустите ваш алгоритм, чтобы найти биекцию. Затем проверьте, что вы действительно получили правильно сформированную биекцию (которая является линейным временем). Если вы сделали, то графики изоморфны; если нет, то это не так. Таким образом, вы решили проблему изоморфизма графов, то есть NP.

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