Помогите понять статью Фараджева И.А. по канонизации графов

[sqribner48]

Здравствуйте. В интересной статье
В. Л. Арлазаров, И. И. Зуев, А. В. Усков, И. А. Фараджев,
Алгоритм приведения конечных неориентированных графов к каноническому виду,Ж. вычисл. матем. и матем.физ., 1974, том 14, номер 3, 737–743, выложенной в Math-Net.Ru, (можно получить по ссылке http://mi.mathnet.ru/zvmmf6432) нашел несколько непонятных для меня мест. Прошу помочь в понимании.
В статье идет речь о приведении матриц смежности графов к каноничекому виду. При этом под каноническим видом имеется в виду лексикографически максимальная матрица (или матрица с максимальным двоичным кодом, полученным с помощью конкатенации строк матрицы). В статье это описано так:

Цитата:

Пусть $A = \{a_{ij}\}, B = \{b_{ij}\}$$ — две различные $(0, 1)$-матрицы порядка $n$.
Будем говорить, что $A$ больше $B(A \succ B)$, если $n^2$ -мерный вектор $(a_{11},\dots,a_{1n},a_{21},\dots, a_{2n},\dots, a_{nn})$ лексикографически старше вектора $(b_{11},..., b_{1n}, b_{21},\dots, b_{2n},\dots, b_{nn})$.
Матрицу

$$\tilde{A} = \max_{g \in Sym(n)} gAg^{-1}$$

где $Sym(n)$ — симметричная группа степени $n$, будем называть максимальным видом матрицы $A$.
Пусть $A$ — матрица смежности обыкновенного графа $G$. Граф $\tilde{G}$, матрицей
смежности которого служит $\tilde{A}$, очевидно, обладает всеми свойствами канонического вида.

Тут, вроде бы все понятно. Трудности начинаются приводе обозначений

Цитата:

Введем обозначения

$$Min_k(A) = \{a_{ij}\}, i, j =1,2,…,k,$$

Я так понимаю, что $Min_k(A)$ это квадратная $(k \times k)$- размерная подматрица главные диагонали которой, находятся на главной диагонали матрицы $A$ (по определению минимальное значение $k =1$).
Далее для любых $i,j = 1,2,\dots,n$ вводится некоторая (окаймляющая $Min_k(A)$) подматрица $Min_{k,r}(A)$, следующего вида:

$$ \begin{pmatrix} a_{11} & \cdots & a_{1k} & a_{1r} \\ a_{21} & \cdots & a_{2k} & a_{2r} \\ \cdots & \cdots & \cdots & \cdots \\ a_{k1} & \cdots & a_{kk} & a_{kr} \\ a_{r1} & \cdots & a_{rk} & a_{rr} \end{pmatrix} $$

В тексте не совсем ясно что там стоит на пересечении $r$-го столбца и $r$-той строки, но я поставил туда $a_{rr}$ (как мне кажется правильно).
Далее следует самое непонятное:

Цитата:

Матрица $A$ называется монотонной, если для любого $k=1, 2,..., n$

$$Min_k(A) = \max_{k \le r \le n} Min_{k-1,r} (A).$$

Монотонную матрицу $gAg^{-1}, g \in Sym(n)$, будем называть монотонным видом матрицы $A$.

Вопрос 1.
Непонятно как определяется $Min_{k-1,r}(A)$ при $k=1$?
По логике должно быть $Min_{0,r}(A)$, но ведь эта подматрица не определена, как и не определена подматрица $Min_0(A)$
Получается, что определение монотонной матрицы некорректно.
Если же, вопреки определению, принять что $Min_0(A)$ есть пустая матрица тогда $Min_{0,r}(A) = a_{1r} \in \{0,1\}$. Однако т.к. у матрицы $A$ все элементы главной диагонали нули, то $Min_{1}(A) = 0$ и следовательно в общем случае

$$Min_{1}(A) \not= \max_{1 \le r \le n} Min_{0,r} (A).$$

Вопрос 2.
Правильно ли я понимаю, что под $g$ имеется в виду подстановочная матрица, а группа $Sym{n}$ это группа подстановок (вопрос возник потому, что ранее эта $g$ использовалась и в контексте $gG$ при определении канонической формы графа $G$)?

Вопрос 3.
Еще одно темное место:
Аналогично, $Min_s(A)$ такой, что для $k=1, 2, \dots , s$

$$Min_k (A) = \max_{k \le r \le n} Min_{k-1,r} (A),$$

называется монотонным минором матрицы $A$.

Правильно ли я понимаю, что $Min_s(A)$ называется монотонным минором матрицы $A$ если для любого $k=1, 2, \dots, s$ справедливо

$$Min_k (A) = \max_{\substack{k \le r \le n}} Min_{k-1,r} (A).$$

[sqribner48]

По-видимому тема несколько занудная. Кому просто так захочется копаться в чужой статье?
Для меня она показалось интересной тем, что критерий монотонности матрицы можно было бы использовать как критерий максимальности кода матрицы! Однако, в п.3 статьи авторы пишут, что монотонных матриц много и матрица с максимальным кодом только одна из них. И для нахождения такой матрицы предлагается довольно сложный алгоритм.

Цитата:

Предлагаемый алгоритм нахождения максимального вида $\tilde{A}$ матри­цы $A$ и тем самым — канонического вида Canon(G) графа G, для которого $A$ служит матрицей смежности, заключается в построении всех монотонных видов матрицы $A$ и выбора из них максимального.

А жаль.

(Оффтоп)

...слеза катилась, слезой несбывшихся надежд...

Однако, продолжаю чтение дальше. Бросается в глаза тот факт, что для $k = n$ подматрица $Min_k(A) = Min_{k-1,r}(A)$, так как в этом случае $r=n$ (т. е. для любой матрицы $A$ фактически имеем $Min_n(A) = Min_{n-1,n}(A)=A.$
Видимо поэтому при доказательстве теоремы 1 от противного принимается $k< n$. А с учетом вышеуказанного "косяка" в определении монотонности матрицы нижний предел для $k$ вообще не указан (а надо бы наверно принять $2 \le k$).

Цитата:

Теорема 1. Если $A$ — симметрическая $(0, 1)$ -матрица с нулевой диагональю, то ее максимальный вид монотонен.
Доказательство. Предположим, что утверждение неверно. Пусть $Min_k(\tilde{A})$, $k < n$, — монотонный минор $\tilde{A}$, но $Min_{k,r}(\tilde{A}) \succ Min_{k+1}(\tilde{A})$, $k+1 < r$. Тогда ...

Таким образом, доказательство теоремы 1 надо еще проверить, принимая $2 \le k \le n -1.$
Прошу помочь мне разобраться в доказательстве теоремы 1.

[iifat]

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

Непонятно как определяется $Min_{k-1,r}(A)$ при $k=1$

Дык по вашей же формуле. Что есть последовательность $1,0$? Пустая последовательность, вестимо.

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

Правильно ли я понимаю

Видимо, да. От переписывания высказывания истинность его не меняется. Или это я не заметил кой-нить разницы формулировок?

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

слеза катилась, слезой несбывшихся надежд

Эх... Заслушался...

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

нижний предел для $k$ вообще не указан

Раз не указан — значит, совпадает с определениями. А определён минор, начиная с нулевого порядка.

[sqribner48]

Уважаемый iifat.
Вы наверно плохо прочитали мои сообщения и наверно совсем не читали статью по ссылке. Иначе бы так не писали:

iifat в сообщении #962084 писал(а):

sqribner48 в сообщении #961429
писал(а):
Непонятно как определяется $Min_{k-1,r}(A)$ при $k=1$ Дык по вашей же формуле.

Формула не моя, а авторов статьи. Поэтому повторно цитирую:

Цитата:

Введем обозначения

$$Min_k(A) = \{a_{ij}\}, i, j =1,2,…,k,$$

$$ Min_{k,r}(A) = \begin{pmatrix} a_{11} & \cdots & a_{1k} & a_{1r} \\ a_{21} & \cdots & a_{2k} & a_{2r} \\ \cdots & \cdots & \cdots & \cdots \\ a_{k1} & \cdots & a_{kk} & a_{kr} \\ a_{r1} & \cdots & a_{rk} & a_{rr} \end{pmatrix} $$

И еще

Цитата:

Матрица $A$ называется монотонной, если для любого $k=1, 2,..., n$

$$Min_k(A) = \max_{k \le r \le n} Min_{k-1,r} (A).$$

Где же тут видно, что миноры определены с 0? Все миноры в статье были определены, начиная с 1.
Дык поэтому я и написал, что не понятно как определяется $Min_{k-1,r}(A)$ при $k=1$.

iifat в сообщении #962084 писал(а):

sqribner48 в сообщении #961429
писал(а):
Что есть последовательность $1,0$? Пустая последовательность, вестимо.

А $\{0,1\}$ - это не последовательность, а множество, состоящее из 0 и 1 (у нас ведь $(0,1)$ - матрица, т.е. любой элемент, кроме диагональных (которые всегда равны 0), может принимать значение из этого множества.

iifat в сообщении #962084 писал(а):

sqribner48 в сообщении #961429
писал(а):
Правильно ли я понимаю Видимо, да. От переписывания высказывания истинность его не меняется. Или это я не заметил кой-нить разницы формулировок?

Рад за Вас. А я вот что- то не сразу понял (формулировка-то вывернута с конца).

iifat в сообщении #962084 писал(а):

sqribner48 в сообщении #961981
писал(а):
слеза катилась, слезой несбывшихся надежд Эх... Заслушался...

Да что Вы? Я же просто пошутил.

(Оффтоп)

Вы оказывается любитель старых песен.

Считаю, что разумных ответов я пока не получил

[iifat]

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

совсем не читали

А должен? Я отвечаю на заданный вами вопрос. Читать статью мне сейчас некогда.

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

повторно цитирую

Вот объясните мне логику, сделайте милость: первое письмо я прочёл, по-вашему, невнимательно, а если в следующем его же процитировать — тут-то мне деваться будет некуда, так? Вас ждёт ещё немало разочарований в жизни. (Сверчок из Буратино, цитирую, впрочем, по памяти)

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

Где же тут видно, что миноры определены с 0?

А где видно чего-нить другое? Если нет явного условия на $k$, то условие выводится из осмысленности текста, в данном случае — текста определения минора. А определение, как я уже сказал, имеет смысл и при $k=0$.

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

А $\{0,1\}$ - это не последовательность, а множество

Именно. А вон тот старый башмак — также не последовательность, а просто старый башмак. Так уж совпало, что я не писал ни про $\{0,1\}$, ни про старый башмак. От человека, желающего, чтобы его читали внимательнее, как-то ожидается несколько более внимательного чтения ответов.

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

Считаю, что разумных ответов я пока не получил

Ваше право.

[sqribner48]

iifat в сообщении #962391 писал(а):

sqribner48 в сообщении #962169
писал(а):
совсем не читали А должен?

Да, если хотите дать правильный ответ, а не писать нечто про пустую последовательность, Буратино и башмак...

iifat в сообщении #962391 писал(а):

Вот объясните мне логику, сделайте милость: первое письмо я прочёл, по-вашему, невнимательно, а если в следующем его же процитировать — тут-то мне деваться будет некуда, так?

Логика очень проста. Если кто-то плохо прочитал, то ему надо показать еще раз, может лучше прочтет со второй попытки. Кстати цитировал я не свое письмо, а определение, взятое из статьи.

iifat в сообщении #962391 писал(а):

Если нет явного условия на $k$, то условие выводится из осмысленности текста, в данном случае — текста определения минора. А определение, как я уже сказал, имеет смысл и при $k=0$.

А если лучше посмотреть.

$$Min_k(A) = \{a_{ij}\}, i, j =1,2,…,k,$$

$$Min_{k,r}(A)= \begin{pmatrix} a_{11} & \cdots & a_{1k} & a_{1r} \\ a_{21} & \cdots & a_{2k} & a_{2r} \\ \cdots & \cdots & \cdots & \cdots \\ a_{k1} & \cdots & a_{kk} & a_{kr} \\ a_{r1} & \cdots & a_{rk} & a_{rr} \end{pmatrix} $$

Где Вы тут увидели 0? Ясно видно, что миноры $Min_k(A)$, $Min_{k,r}(A)$ не определены при $k=0$.

Оставим Сверчок из Буратино и башмак. А Вы просто представьте пример минора $Min_{0}(A)$ и хоть пару миноров $Min_{0,r}(A)$ для какой-нибудь $(0,1)$-матрицы, являющейся матрицей смежности графа.

[iifat]

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

Да, если хотите дать правильный ответ

А я тут не даю правильных ответов. Я тут даю ответы на заданные вопросы. И таки да, это намёк.

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

Ясно видно

Если вам ясно видно то, чего нет,.. эээ... ну, придумайте что-нить.

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

Оставим Сверчок из Буратино и башмак

А ваше множество из рукава $\{0,1\}$ что ж постеснялись упомянуть в этом славном ряду?

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

А Вы просто представьте пример минора $Min_{0}(A)$

Представил. Вы счастливы? Или вы имели в виду — предоставить? Ну, минор нулевого порядка — он вообще ровно один-одинёшенек на этом свете. У него ноль строк, ровно столько же столбцов, и элементы в количестве, равном произведению этих двух славных числ.

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

хоть пару миноров $Min_{0,r}(A)$

Легко. Да вы на формулу свою (да, я знаю, что это цитата. Но я говорю с вами, а не с авторами статьи) посмотрите внимательно. Любой элемент на главной диагонали и будет таким минором. Точнее, матрица 1 на 1 с таким элементом в качестве единственного.

[sqribner48]

iifat в сообщении #962434 писал(а):

sqribner48 в сообщении #962427
писал(а):
Да, если хотите дать правильный ответ А я тут не даю правильных ответов. Я тут даю ответы на заданные вопросы.

А зачем тогда писать, если не давать правильные ответы на заданные вопросы?

iifat в сообщении #962434 писал(а):

sqribner48 в сообщении #962427
писал(а):
Ясно видно.
Если вам ясно видно то, чего нет,.. эээ... ну, придумайте что-нить.

Да это Вы мастер придумывать. А я цитировал определение миноров из которых видно, что индексы $i,j$ миноров определены как $i,j=1,2,\dots,k$.

iifat в сообщении #962434 писал(а):

sqribner48 в сообщении #962427
писал(а):
Оставим Сверчок из Буратино и башмак.
А ваше множество из рукава $\{0,1\}$ что ж постеснялись упомянуть в этом славном ряду?

Мое множество $\{0,1\}$ было к месту, как значения которые могут иметь элементы матрицы кроме диагональных.

iifat в сообщении #962434 писал(а):

sqribner48 в сообщении #962427

писал(а):
А Вы просто представьте пример минора $Min_{0}(A)$.
Представил. Вы счастливы? Или вы имели в виду — предоставить?

Бросьте ерничать. Предоставить это значит написать, используя знаки математической нотации или описать, используя известные математические термины.

iifat в сообщении #962434 писал(а):

Ну, минор нулевого порядка — он вообще ровно один-одинёшенек на этом свете. У него ноль строк, ровно столько же столбцов, и элементы в количестве, равном произведению этих двух славных числ.

Ну наконец-то разродились...

iifat в сообщении #962434 писал(а):

sqribner48 в сообщении #962427
писал(а):
хоть пару миноров $Min_{0,r}(A)$.
Легко. Да вы на формулу свою (да, я знаю, что это цитата. Но я говорю с вами, а не с авторами статьи) посмотрите внимательно. Любой элемент на главной диагонали и будет таким минором. Точнее, матрица 1 на 1 с таким элементом в качестве единственного.

(Оффтоп)

"Вот слышу я звуки божественной эллинской речи".

Спасибо. А не могли так сразу? Чего было тянуть?
И все-таки, в статье формально не были определены миноры при $k=0$.
Получается, Вы представили скрытые мысли авторов статьи.
P.S. Кстати, в своем первом посте я сделал попытку выйти за пределы определений, данных в статье

Цитата:

Если же, вопреки определению, принять что $Min_0(A)$ есть пустая матрица, тогда $Min_{0,r}(A) = a_{1r} \in \{0,1\}.$

Вы просто более уверенно выразились и указали, что $Min_{0,r}(A) = a_{rr}=0$.
Из всего этого следует, что при $k=1$ и при $k= n$ условия монотонности

$$Min_k(A) = \max_{k \le r \le n} Min_{k-1,r}(A)$$

выполняются для любой матрицы $A$ поэтому их можно не учитывать в доказательстве, что авторы и сделали.

[sqribner48]

Из любопытства реализовал критерий проверки монотонности матриц в Wolfram Mathematica. Проверил несколько сильно регулярных графов с количеством вершин $n=6,9,17,26$.
Для проверки использовал с.р. графы, выложенные на сайте Ted Spence «Strongly regular graphs on at most 64 vertices», представленные каноническими матрицами смежности.
Получил ожидаемые результаты:
1. Для графов с малым числом вершин программа четко определяет матрицу с максимальным кодом как монотонную, остальные матрицы определились как не монотонные.
2. Для графов с большим числом вершин все матрицы с кодами, относительно близкими к максимальному, определились как монотонные.
Было бы интересно доказать теорему 1, приняв более жесткий критерий монотонности типа:
Матрица $A$ называется монотонной, если для любого $k= 2,..., n-1$

$$Min_k(A) > \max_{ k < r \le n} Min_{k-1,r}(A).$$

[sqribner48]

Никто не ответил ни про ужесточение критерия монотонности, ни про теорему 1. Но я сам добил. Приведу здесь то, что получил по ужесточению критерия монотонности матриц. Может кому-то пригодится.
Я реализовал вышеуказанный критерий монотонности в системе Wolfram Mathematica. Получил отрицательный результат. Все матрицы идентифицировались как не монотонные. Такой же отрицательный результат был получен и при использовании критерия:
Матрица $A$ называется монотонной, если для любого $k= 2,..., n-1$

$$Min_k(A) = \max_{ k < r \le n} Min_{k-1,r}(A). \quad (1)$$

Единственным "работающим" критерием оказался критерий

$$Min_k(A) \ge \max_{ k < r \le n} Min_{k-1,r}(A), \quad (2)$$

для любого $k= 2,..., n-1$.
Который фактически совпадает с критерием, приведенным в статье.
Действительно, исходный критерий можно представить в следующем виде:

$$Min_k(A) = \max (Min_{k-1,k}(A),Min_{k-1,k+1}(A),\dots,Min_{k-1,n}(A)), \quad (3) $$

для любого $k= 1,2,..., n$.
Как было сказано выше при $k=1,k=n$ критерий $(3)$ выполняется для любой матрицы( в т.ч. и не монотонной), следовательно случаи когда $k=1,k=n$ можно не рассматривать.
Так как $Min_k(A) = Min_{k-1,k}(A)$, то критерий (3) принимает вид

$$Min_k(A) = \max (Min_{k}(A),Min_{k-1,k+1}(A),\dots,Min_{k-1,n}(A)), \quad (3a) $$

Нетрудно заметить, что равенство (3a) выполняется только тогда, когда для $Min_k(A)$ выполняется условие (2).
Критерий монотонности (2) определяет вид монотонной матрицы. В такой матрице все единицы в нескольких первых строках образуют "лестницу", что-то вроде

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

Образование таких "лестниц" можно объяснить тем, что если в некоторой строке после 0 следует 1, то минор $Min_k(A)$ будет не монотонен, и сама матрица $A$ будет не монотонной.
Остались не рассмотренными пп. 3-6 статьи (однако и из рассмотренного п. 2 ясно, что критерий монотонности матрицы не пригоден для определения матрицы с максимальным кодом)...
Буду признателен за любые замечания и предложения,

(Оффтоп)

особенно если они не используют терминологию iifat типа старого башмака и Сверчка Буратино.

P.S. Разумеется я никогда не думал, что результаты статьи более чем 30-ти летней давности помогут определить критерий максимальности матриц смежности графов (судя по индексу цитирования она была, как говорится, "изъезженна вдоль и поперек"). Может пригодится как упражнение?