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

). Матрицы получить не хитро, и даже переставляьть ничего не надо -- достаточно иметь таблицу переиндексации. Но вот проверять

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