В работе «Эффективный алгоритм изоморфизма графов » Корнейла и Готлиба, 1970 г. была высказана гипотеза, на которой основывался алгоритм для решения GI за полиномиальное время. А именно:
что репрезентативные графы демонстрируют автоморфизм разбиения данного графа
Очевидно, что эта гипотеза не доказана до сих пор (иначе мы бы знали, что GI находится в P). Мой вопрос заключается в том, было ли это доказано, что оно было ложным, и, возможно, был дан контрпример?
graph-isomorphism
automorphism
Джон Д.
источник
источник