2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 16:17 
Здравствуйте.
"Как правильно поменять две вершины в матрице смежности неориентированных графов."
Этот вопрос возник у меня при чтении поста: «Мини/макси-код графа». (К сожалению тема «мини-макси кода» увяла, поэтому решил создать новую, связанную с ней тему).
Конкретно, вопрос возник при чтении следующего фрагмента:
Sender в сообщении #504826 писал(а):
l1pton17 в сообщении #504809 писал(а):
Вот теперь разобрался. Спасибо)
Тогда такой вопрос: как правильно поменять две вершины в матрице смежности неориентированного графа местами?

Очевидно, поменять местами соответствующие строки, а потом соответствующие столбцы(или сначала столбцы, а потом строки).

Вроде бы все просто. Оказывается, нет! Сделал программку в Mathematica и проверил на разных графах. В результате получил «странные результаты» - во многих случаях прямое решение «в лоб», т.е. простая замена строк и столбцов приводит к неверному результату (полученный граф не изоморфен исходному).
Заметил, что ошибки чаще всего возникают при перестановке вершин с номерами: $(1,  j),  (j,  n), (1, n)$ и $(j, j+1)$ где - $ i  <  j  $.
Нашел следующее простое решение этой проблемки: после перестановки строк и столбцов матрицы выполнить проверку следующих условий - $a^\prime_{ii } \not= 0$ и $a^\prime_{ij} \not= a_{ij} $
(где $a^\prime$ -- матрица после перестановки строк и столбцов, а $a$ -- исходная матрица до перестановки строк и столбцов). И в случае невыполнения хотя бы одного из вышеуказанных условий, выполнить «принудительные» присваивания: $a^\prime_{ii} := 0$, $a^\prime_{ij} := a_{ij} $ и $a^\prime_{ji} := a_{ij} $.
Возник вопрос: а почему такое возможно? и чем это можно объяснить?
Мне кажется, что это объясняется тем, что матрица смежностей графа - симметрическая матрица с нулями на главной диагонали, и следовательно должны выполняться следующие соотношения $a_{ij} = a_{ji}$ и $a_{ii} = 0$, которые иногда нарушаются при лобовой перестановке строк и столбцов.
Еще вопрос: Верны ли мои рассуждения?
И если я прав, то почему никто до этого не замечал такого «бревна в глазу»?
P.S. Если кому-то понадобится, готов выслать в личку файл с программками и примерами решения.

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 16:27 
Аватара пользователя
Видимо, у вас ошибка в программе. Не может быть такого.
Вам не кажется странным, что пара индексов $(1,n)$ ведет себя не так, как $(2,n)$? Какая между ними, в сущности, разница?

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 16:37 
Уважаемая provincialka
Не знаю, может в программе есть и ошибка. Я потому и обратился на сайт с вопросом. Надеюсь на помощь и конструктивную критику.

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 16:39 
Аватара пользователя
Хм... а что критиковать-то? Программы мы не видели (а я и смотреть не буду, не пользуюсь Mathematica). А вы без программы попробуйте. Руками.

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 17:14 
Уважаемая provincialka
А зачем тогда писать?.... Руками я пробовал, пробовал и в Excele. Получался такой же плохой результат. А для тех, кто может использовать Mathematica, выкладываю текст "плохой" программы, которая в лоб переставляет строки и столбцы.

Плохая функция
Код:
Badperm2Col[a_,j1_,j2_]:=
Module[{n,am,oldStr1,oldStr2,i1,i2,zz,mxa,mni},
am=a;n=Length[am];
oldStr1={ };oldStr2={  };
i1=j1;i2=j2;
Do[AppendTo[oldStr1,am[[i1,j]]];
AppendTo[oldStr2,am[[i2,j]]],{j,1,n}];
Print[oldStr1];Print[ oldStr2 ];
Do[am[[i1,j]]= oldStr2[[j]];am[[i2,j]]= oldStr1[[j]],{j,1,n}];
  Do[am[[i,j1]]= oldStr2[[i]];
      am[[i,j2]]= oldStr1[[i]],{i,1,n}]; am]


Входные переменные $a$ -- матрица графа; j1, j2 -- номера переставляемых строк и столбцов; $am$ -- выходная матрица после перестановки;
$n$ -- количество строк(столбцов) матрицы; $oldStr1$ -- старое(до перестановки) значение строки j1; $oldStr2$ -- старое(до перестановки) значение строки j2;
Остальное видно из текста программы

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 17:23 
Аватара пользователя
Исходная матрица $\begin{pmatrix}
0 & 1 & 1 & 0\\
1 & 0 & 1 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 0 & 0
\end{pmatrix}$
Переставляем первый столбец с четвертым $\begin{pmatrix}
0 & 1 & 1 & 0\\
0 & 0 & 1 & 1\\
0 & 1 & 0 & 1\\
0 & 0 & 0 & 0
\end{pmatrix}$
Переставляем первую строку с четвертой $\begin{pmatrix}
0 & 0 & 0 & 0\\
0 & 0 & 1 & 1\\
0 & 1 & 0 & 1\\
0 & 1 & 1 & 0
\end{pmatrix}$
Такой результат нормальный?

-- 28.11.2014, 17:24 --

Хм... Судя по обозначениям, вы только строки переставляете? А столбцы как же?

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 17:35 
Значения строк и столбцов одинаковы (т.к. матрица симметричная). Поэтому использовались обозначения oldStr1 и oldStr2. Из текста программы видно, что в третьей снизу строке программы производится замена элементов двух строк, в первой и второй снизу строках программы -- производится замена элементов двух столбцов.
Насчет Вашего примера я ответ дам чуть позже.
Кстати, плохая программа не всегда работает плохо, в некоторых случаях она работает хорошо, а в некоторых - работает плохо. Ваш пример уж очень "гладкий" (чего стоит полностью заполненная нулями 4-ая строка и 4-тый столбец).
Позже я приведу пример, матрицы, на которой программа работает плохо.

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 18:19 
Аватара пользователя
Сильно сомневаюсь. То есть что программа работает плохо - это может быть. Но я уже столько раз применяла эту операцию в Excel... Да и чисто логически все верно.

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 18:32 
Спасибо. У меня благодаря вам тоже появился большой "червячок" сомнения. Есть даже догадка о причинах плохой работы программы. Но надо еще проверить....

(Оффтоп)

А интересно, если не секрет, в какой области деятельности вы использовали Excel для перестановки строк и столбцов матрицы?

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 18:37 
sqribner48 в сообщении #937472 писал(а):
Позже я приведу пример, матрицы, на которой программа работает плохо.
Так вот же ж самое главное! А вы на последнее место поставили. :wink:

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение28.11.2014, 18:48 
Аватара пользователя
sqribner48 в сообщении #937484 писал(а):
А интересно, если не секрет, в какой области деятельности вы использовали Excel для перестановки строк и столбцов матрицы?
Я веду курсы по обработке данных. А там разные задачки с графами и матрицами встречаются.

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение29.11.2014, 14:05 
provincialka
Спасибо за ответ. Это интересно....
Я понял, почему программа плохо работала на некоторых данных. Все дело в том, что в программе дважды использовались первоначальные значения элементов строк(столбцов). Но после первой замены двух строк, надо уже использовать новые значения соответствующих элементов двух столбцов.

arseniiv
Согласен с вами.

Модераторам математики
Уважаемый модератор.
Мне кажется, что эту тему более целесообразно перенести в корень раздела Computer Sience, поскольку она относится к "обсуждению вопросов, связанных с программированием.... без привязки к языку программирования".
Я разместил ее в разделе "Математика. Общие вопросы", поскольку она была тесно связана с темой «Мини/макси-код графа».
После нескольких первых откликов у меня возникли сомнения по месту размещения этой темы. Но было уже поздно (т.к. ничего уже нельзя было изменить). А прошедшая небольшая дискуссия сильно убедила меня в необходимости переноса темы.

 
 
 
 Posted automatically
Сообщение29.11.2014, 15:58 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Программирование»
Пожалуйста

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение29.11.2014, 16:53 

(Оффтоп)

Deggial
Большое спасибо. А то мне было перед форумчанами неудобно.

 
 
 
 Re: Как поменять две вершины в матрице смежности неориен. графов
Сообщение01.12.2014, 19:28 
Аватара пользователя
В дополнение к сказанному напомню классическое решение:

$P^TAP$,
где $A$ -- $n\times n$ матрица смежности;
$P$ -- $n\times n$ матрица перестановки.

Подробности в любом учебнике по матричной алгебре, для начала можно воспользоваться и Википедией. Отмечу, что для реализации этой формулы, например, в Excel, стоит воспользоваться встроенными функциями матричного умножения и транспонирования матрицы.
Успехов!

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


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