2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Полный инвариант графа?
Сообщение05.03.2014, 23:42 
Аватара пользователя
Пример из книги A. E. Brouwer, W. H. Haemers, Spectra of graphs.
Вложение:
tmp.png


У вас нет доступа для просмотра вложений в этом сообщении.

 
 
 
 Re: Полный инвариант графа?
Сообщение05.03.2014, 23:44 
Аватара пользователя
Спасибо вам! То, что нужно!

 
 
 
 Re: Полный инвариант графа?
Сообщение05.03.2014, 23:47 
особенно простых примеров нет, в самом маленьком пять вершин, можете тут посмотреть
впрочем, важнее понимать то, что изоморфизм графов - проблема существенно более сложная с точки зрения вычислений, чем характеристический многочлен
что как бы намекает на уровень знаний говорившего на дискретной математике

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

 
 
 
 Re: Полный инвариант графа?
Сообщение06.03.2014, 11:55 
Аватара пользователя
К сожалению, это только в одну сторону работает. У изоморфных графов с.з. совпадают, но есть неизоморфные, однако "изоэйгенные"...

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group