Вопрос по теории графов

[Stasyara]

Подскажите алгоритмы распознавания изоморфизма двух ориентированных графов

[juna]

Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одновременными перестановками строк и столбцов (т.е. переставляется $i$-я и $j$-я строка и $i$-й и $j$-й столбец).

[незваный гость]

Вообще-то это скорее из раздела Computer Science. И если не полениться и поискать, то можно найти достаточно длинное обсуждение.

[juna]

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

[V.V.]

Артамонов Ю.Н. писал(а):

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

Можно я отвечу?

Программа, все переставляющая, будет работать ОЧЕНЬ долго.

В той теме я уже писал, что некоторые граждане из Сибири анонсировали полиномиальный алгоритм. Он основан на изучении спектра матрицы.

[незваный гость]

Артамонов Ю.Н. писал(а):

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

Вычислительной сложностью (${\rm O(n^2 n!)}$). Матрицы получить не хитро, и даже переставляьть ничего не надо -- достаточно иметь таблицу переиндексации. Но вот проверять $n!$ перестановок -- тяжко. это даже не экспонента, это намного хуже.

Артамонов Ю.Н. писал(а):

По указанной Вами ссылке, после дискуссии тоже самое порекомендовали.

Я бы не сказал, что рекомендовали именно это. Во-первых, были и другие рекомендации, хотя BlackSem, по-видимому, ими и не воспользовался. Во-вторых, обсуждение, как это не странно, и серьезные рекомендации были в начале, а не в конце... Консенсуса не было, дисскурсия затухла за отсутсвием интереса. Не считать же пример программы рекомендацией, правда? Это очень честная и трудоемкая попытка помочь.