ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexey Kruglov                       2:5015/70.5    04 Jun 2002  16:35:01
 To : Max Alekseyev
 Subject : матричные перестановки
 -------------------------------------------------------------------------------- 
 

 
 Понедельник 03 Июня 2002 03:58, Max Alekseyev wrote to All:
 
  MA> Дана матрица mxn. Hужно найти перестановку строк и перестановку
  MA> столбцов (одновременно не являющиеся тождественными) такие, что
  MA> примененные к данной матрице они не изменяют ее. Или определить, что
  MA> таких перестановок нет. Hасколько эта задача сложная?
 
 Hахождение автоморфизма графа сводится к этой задаче. Берем матрицу смежности
 графа, на диагонали ставим двойки, тогда перестановки строк и столбцов будут
 совпадать, т.к. диагональ должна перейти в себя. Эта перестановка будет
 нетождественной => она и будет подходящим автоморфизмом графа. Идею взял у
 Марины Молчановой. Если под тем, что задача с m=n и одинаковыми перестановками
 строк и столбцов является частным случаем исходной задачи, понимать, что первая
 сводится ко второй, например, прибавлением достаточно большого числа к
 диагонали, то это и есть решение MM.
 
 Т.е. эта задача не проще автоморфизма графов, насколько он сложен не знаю.
 
  MA> А что в случае, когда исходная матрица циклическая nxn:
  MA> [ a_1 a_2 ... a_{n-1}  a_n   ]
  MA> [ a_2 a_3 ...   a_n    a_1   ]
  MA> [ ... ... ...   ...    ...   ]
  MA> [ a_n a_1 ... a_{n-2} a_{n-1}]
  MA> где некоторые числа a_i равны между собой?
 
 Циклически сдвигаем строки вниз, столбцы влево. При этом матрица переходит в
 себя.
 
 nOkA. Alexey.
 
 --- GoldED+/386 1.1.4.7
  * Origin:  6DFA 1186 7576 DE60 6CCB  EB39 AD81 1733 EEBB 970A  (2:5015/70.5)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    матричные перестановки   Max Alekseyev   03 Jun 2002 04:58:12   матричные перестановки   Alexey Kruglov   04 Jun 2002 16:35:01