Какие существуют алгоритмы проверки изоморфности 2х графов?

[tpc]

Если память не подводит, эффективные алгоритмы существуют, помимо графов конечной степени, также и для графов, вкладываемых в поверхность с небольшим числом ручек (bounded genus graphs).

[Alexey Romanov]

Woland в сообщении #25704 писал(а):

Но пока читаешь текст, действительно возникает впечатление ,что речь идёт именно о n! способов переобозначить вершины. (Как правильно читать, чтоб и у Вас возникло такое впечатление,
я отвечу по личной переписке).

Вот указанные мною строки:
.....
Однако для доказательства изоморфизма графов необходимо явно
указать биекцию множества вершин одного графа на множество
вершин второго, при которой сохраняется отношение смежности.
Поиск такой биекции весьма трудоёмок, так как может потребовать
ПОЛНОГО ПЕРЕБОРА ВСЕХ ВОЗМОЖНЫХ ВАРИАНТОВ.
Для доказательства неизоморфности достаточно показать принципиальную
невозможность установления требуемой биекции. (далее рассказывается о "тонких структурах циклов") .

Вообще же, теория графов занимает в этой книге страниц 200.
И весьма вероятно, что авторы предпологают, что если читатель
до этой страницы вообще до шел, то он с лёгкостью может доказать
это предложение.

Если они так считают (а я этого не вижу), то они не правы. Потому что известен c 1983 года алгоритм в $2^{O(\sqrt {(n \log n)}\;)}$: The Babai-Luks-Zemlyachenko algorithm for general GI

[Interloper]

незваный гость в сообщении #10548 писал(а):

Теперь мы можем повторить подсчет дуг, но уже считая, в какой или из какого класса эквивалентности они идут. Опять-таки сигнатуры должны совпасть. А количество классов - увеличиться.

Поясните, что имеется в виду.

[Leox]

Существуют чисто алгебраические методы - для labeled graph находится система полиномиальных инвариантов ( инварианты некоторой погруппы симметрической группы),которые вычисляются для каждого графа. Если все значения инвариантов свопадают то графы изоморфны. Правда явно система таких инвариантов полностью найдена лишь для графа из 5 вершин, их всего 57. Если граф простой то количество инвариантов можно значительно уменьшить,кажется до 4-5.