Полный инвариант графа?

[kp9r4d]

Нам сегодня на дискретной математике сказали, что если A — матрица смежности гарфа, то графы изоморфны тогда и только тогда, когда многочлены $\det |A-\lambda E|$ совпадают. Я почти уверен, что это неправда, но перебор писать лень, а контрпример найти всё-таки хочется. Может кто поделится кодом на Mathematicу или маленьким контрпримером?

[Xaositect]

Пример из книги A. E. Brouwer, W. H. Haemers, Spectra of graphs.

Вложение:

tmp.png [ 2.32 Кб | Просмотров: 825 ]

[kp9r4d]

Спасибо вам! То, что нужно!

[patzer2097]

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

[kp9r4d]

patzer2097
И вам спасибо! Да, мне ещё в школе при подготовке к олимпиадам по информатике говорили, что полиномиального алгоритма не придумано, при этом вычисление определителя мы писать все умели за куб. А в ВУЗ попал я далеко не в самый топовый.

[Евгений Машеров]

К сожалению, это только в одну сторону работает. У изоморфных графов с.з. совпадают, но есть неизоморфные, однако "изоэйгенные"...