2014 dxdy logo

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

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




 
 Изоморфизм графов
Сообщение19.05.2013, 16:23 
Приветствую. Помогите разобраться. Нужно доказать что графы изоморфны, то есть привести матрицу $B_1$ к матрице $B_2$ или наоборот. Короче говоря, нужно подвигать столбцы/строки одной матрицы так, чтобы они (матрицы) были одинаковы.


B_1=$$
\begin{pmatrix}
0 & 1 & 0 & 1 & 1 & 0  \\
1 & 0 & 1 & 0 & 0 & 1  \\
0 & 1 & 0 & 1 & 1 & 0  \\
1 & 0 & 1 & 0 & 0 & 1  \\
1 & 0 & 1 & 0 & 0 & 1  \\
0 & 1 & 0 & 1 & 1 & 0  \\
\end{pmatrix}

B_2=$$
\begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1  \\
0 & 0 & 1 & 1 & 0 & 1  \\
0 & 1 & 0 & 1 & 1 & 0  \\
1 & 1 & 1 & 0 & 0 & 0  \\
1 & 0 & 1 & 0 & 0 & 1  \\
1 & 1 & 0 & 0 & 1 & 0  \\
\end{pmatrix}

 
 
 
 Re: Изоморфизм графов
Сообщение19.05.2013, 19:34 
Аватара пользователя
Но они неизоморфны!

 
 
 
 Re: Изоморфизм графов
Сообщение19.05.2013, 19:42 
Аватара пользователя
Эти графы не изоморфны. Первый - полный двудольный (три дома - три колодца). А второй - каркас треугольной призмы. В нем есть треугольники.

 
 
 
 Re: Изоморфизм графов
Сообщение20.06.2013, 12:43 
Опять попалось это задание. Графы изоморфны, так как кол-во 1 и 0 в обеих матрицах равное. Нужно просто двигать столбцы/строки так, чтобы обе матрицы получились одинаковы.

 
 
 
 Re: Изоморфизм графов
Сообщение20.06.2013, 14:06 
Аватара пользователя
Вы впадаете в большую ошибку.

 
 
 
 Re: Изоморфизм графов
Сообщение20.06.2013, 17:53 
Аватара пользователя
edw1n в сообщении #738711 писал(а):
Опять попалось это задание. Графы изоморфны, так как кол-во 1 и 0 в обеих матрицах равное. Нужно просто двигать столбцы/строки так, чтобы обе матрицы получились одинаковы.
Неправильно. Что такое изоморфизм графов?

 
 
 
 Re: Изоморфизм графов
Сообщение20.06.2013, 21:08 
edw1n в сообщении #738711 писал(а):
Нужно просто двигать столбцы/строки так, чтобы обе матрицы получились одинаковы.
Это как раз неосуществимо. А осуществимо тогда и только тогда, когда графы изоморфны. Советы посмотреть определение ведь неслучайны!

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


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