Как поменять две вершины в матрице смежности неориен. графов

[sqribner48]

Здравствуйте.
"Как правильно поменять две вершины в матрице смежности неориентированных графов."
Этот вопрос возник у меня при чтении поста: «Мини/макси-код графа». (К сожалению тема «мини-макси кода» увяла, поэтому решил создать новую, связанную с ней тему).
Конкретно, вопрос возник при чтении следующего фрагмента:

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. Если кому-то понадобится, готов выслать в личку файл с программками и примерами решения.

[provincialka]

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

[sqribner48]

Уважаемая provincialka
Не знаю, может в программе есть и ошибка. Я потому и обратился на сайт с вопросом. Надеюсь на помощь и конструктивную критику.

[provincialka]

Хм... а что критиковать-то? Программы мы не видели (а я и смотреть не буду, не пользуюсь Mathematica). А вы без программы попробуйте. Руками.

[sqribner48]

Уважаемая 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;
Остальное видно из текста программы

[provincialka]

Исходная матрица $\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 --

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

[sqribner48]

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

[provincialka]

Сильно сомневаюсь. То есть что программа работает плохо - это может быть. Но я уже столько раз применяла эту операцию в Excel... Да и чисто логически все верно.

[sqribner48]

Спасибо. У меня благодаря вам тоже появился большой "червячок" сомнения. Есть даже догадка о причинах плохой работы программы. Но надо еще проверить....

(Оффтоп)

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

[arseniiv]

sqribner48 в сообщении #937472 писал(а):

Позже я приведу пример, матрицы, на которой программа работает плохо.

Так вот же ж самое главное! А вы на последнее место поставили.

[provincialka]

sqribner48 в сообщении #937484 писал(а):

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

Я веду курсы по обработке данных. А там разные задачки с графами и матрицами встречаются.

[sqribner48]

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

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

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

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Программирование»
Пожалуйста

[sqribner48]

(Оффтоп)

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

[bin]

В дополнение к сказанному напомню классическое решение:

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

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