Полиномиальный алгоритм изоморфизма графов

[bin]

whitefox
Спасибо. Учту Ваше замечание.

[bin]

whitefox
посоветовался с коллегами о Вашем предложении:

whitefox в сообщении #739061 писал(а):

Определение 1. Будем говорить, что вершина $v$ графа $G$ и вершина $v'$ графа $G'$ подобны, если они подобны как вершины графа $G\cup G'$.

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

Цитата:

Определение изоморфизма, которым я пользуюсь, следующее: обыкновенные $n$-графы $G$ и $H$, с матрицами смежности $A $ и $B$ соответственно, изоморфны, если существует такая матрица перестановки $P$, что $B=PAP^T$. В указанном случае изоморфизмом будет матрица $P$. Изоморфное отображение графа на себя называется автоморфизмом. Так матрица перестановки $Q$ задает автоморфизм, если $QAQ^T=A$. Из этой записи автоморфизма видно, что автоморфизм частный случай изоморфизма. В чем же их различие? Чтобы это выяснить, возьмем два различных изоморфизма $P_1$ и $P_2$ и два различных автоморфизма $Q_1$ и $Q_2$. Рассмотрим произведение автоморфизмов $Q_2Q_1$ (или $Q_1Q_2$). Это произведение будет снова автоморфизмом, ибо $Q_2Q_1AQ_1^TQ_2^T = Q_2(Q_1AQ_1^T)Q_2^T = Q_2AQ_2^T = A$. Теперь уже нетрудно убедиться, что множество автоморфизмов относительно операции умножения автоморфизмов образует группу.

Рассмотрим теперь произведение $P_2P_1$. Это произведение, вообще говоря, не будет изоморфизмом. Действительно, $P_2P_1AP_1^TP_2^T = P_2(P_1AP_1^T)P_2^T = P_2BP_2^T$. В общем случае $P_2BP_2^T \neq B$. Следовательно, умножение изоморфизмов не замкнуто на множестве изоморфизмов и множество изоморфизмов не образует относительно операции умножения изоморфизмов группу. Произведение $P_2P_1$ будет изоморфизмом, когда либо $P_2$ - изоморфизм, а $P_1$ - автоморфизм для $A$, либо $P_1$ - изоморфизм, а $P_2$ - автоморфизм для $B$. В любом случае, с каждым изоморфизмом, например, $P_2$ связан целый класс смежности симметрической группы (группы всевозможных перестановок порядка $n$) по подгруппе автоморфизмов для$ A$. То есть для любого изоморфизма $P_2$, изоморфизмом будет и произведение $P_2Q$, для любого автоморфизма $Q$ ($QAQ^T=A$). Аналогично, для любого изоморфизма $P_1$, изоморфизмом будет и произведение $RP_1$, для любого автоморфизма $R$ ($RBR^T=B$).

Далее, любой автоморфизм $Q$ ($QAQ^T=A$), можно расписать поэлементно, т.е. в виде $\alpha(u)=v$ ($u, v$ – вершины графа $G$) и назвать эти вершины подобными. Затем изоморфизм $P$ ($B=PAP^T$) , также можно расписать поэлементно в виде $\pi(v)=v'$, где v - вершина графа $G$, а $v'$ - вершина графа $H$. Никто не мешает по аналогии назвать вершины $v$ и $v'$ подобными (автоморфизм частный случай изоморфизма). Другое дело, как Вы используете это аналогичное определение. Если это не ведет к недоразумениям, то никто не имеет права ставить Вам в упрек новое определение (по аналогии). Замечу, что у Харари, на стр. 36, для графов, имеющих различные множества вершин и ребер, введена операция объединения графов, например, графов $G\cup H$. Если графы $G$ и $H$ связные, то после объединения этих графов, они становятся различными компонентами связности одного графа. Вероятно, Ваш оппонент, когда делал Вам замечание, имел в виду следующее – определение подобных вершин у Харари дается для вершин одного графа, а Ваше обобщение переносит определение подобия на вершины разных графов. Поэтому его предложение сводится к тому, чтобы сделать вершины разных графов вершинами одного графа. Я в его, на мой взгляд, неудачном предложении не вижу "существа", вижу только желание сохранить форму.

Можно различать подобные вершины относительно автоморфизма и подобные вершины относительно изоморфизма (т.е. относительно операции изоморфного отображения). Можно сделать такое примечание в статье. Думаю, что из контекста там везде ясно, о каком подобии идет речь.

[whitefox]

По всей видимости, задавая вопрос своему Консультанту, Вы опустили в моём сообщении мотивировочную часть.

whitefox в сообщении #739061 писал(а):

Допустим, что вершины $u$ и $v$ графа $G$ подобны в соответствии с классическим определением (по Харари).
Но по Вашему определению они уже не будут подобными, так как не существует изоморфизма $\pi$ графа $G$ на граф $G'$ такого, что $\pi(u)=v$.

Поэтому он упустил один очень важный момент.
А именно, термин "подобие" традиционно используется для обозначения некоторых отношений эквивалентности.
Именно так его использует Харрари.

Но по Вашему определению, "расширенное подобие" уже эквивалентность не является, так как оно не рефлексивно и не транзитивно.

Приведу пример.
Пусть граф $G$ состоит из двух вершин $a,b$ и одного ребра $(a,b)$.
И пусть граф $G'$ тоже состоит из двух вершин $c,d$ и одного ребра $(c,d)$.
Очевидно, что графы $G$ и $G'$ изоморфны.
То есть существует изоморфим $\pi$ графа $G$ на граф $G'$ такой, что $\pi(a)=c$.
Также существует изоморфизм $\sigma$ графа $G'$ на граф $G$ такой, что $\sigma(c)=b$.
Но не существует никакого изоморфизма $\tau$ графа $G$ на граф $G'$ такого, чтобы $\tau(a)=b$.
Это показывает, что отношение "расширенного подобия" не является транзитивным.
А так как, кроме этого, не существует никакого изоморфизма $\varphi$ графа $G$ на граф $G'$ такого, чтобы $\varphi(a)=a$, то это отношение и не рефлексивно.

Не думаю, чтобы это было именно то, чего Вы хотели.
Именно поэтому я и предложил способ которым можно в отношение "расширенного подобия" ввести рефлексивность и транзитивность.
В самом деле, для графа $G\cup G'$ найдутся и автоморфизм $\tau$ и автоморфизм $\varphi$.

bin в сообщении #740669 писал(а):

Никто не мешает по аналогии назвать вершины $v$ и $v'$ подобными (автоморфизм частный случай изоморфизма). Другое дело, как Вы используете это аналогичное определение. Если это не ведет к недоразумениям, то никто не имеет права ставить Вам в упрек новое определение (по аналогии).

Никто не мешает, кроме не желательности распространения термина "подобие" на отношения не являющиеся эквивалентностью. Это легко может привести к недоразумению.

bin в сообщении #740669 писал(а):

Я в его, на мой взгляд, неудачном предложении не вижу "существа", вижу только желание сохранить форму.

Неудачным является применение термина "подобие" к не рефлексивному и не транзитивному отношению. А "сущность" моего предложения как раз и состоит в том, чтобы ввести эти отсутствующие рефлексивность и транзитивность.

Но должен признать, что моё определение будет применимо только к связным графам.
В общем случае это далеко не так.
Например, пусть граф $G$ состоит только из двух изолированных вершин $a,b$, а граф $G'$ состоит только из одной вершины $c$.
Очевидно, что эти графы не изоморфны, поэтому "разумное" расширение отношения "подобия" не должно устанавливать подобие вершин $a$ и $c$.
Но в графе $G\cup G'$ все три вершины $a,b,c$ подобны.
Нонсенс.

[bin]

whitefox в сообщении #740986 писал(а):

По всей видимости, задавая вопрос своему Консультанту, Вы опустили в моём сообщении мотивировочную часть.

Нет, я в точности скопировал Ваше сообщение и эту его часть. Скопирую и новое сообщение - интересно, что он мне посоветует. Ваше сообщение нужно серьезно обдумать, но прежде хочу спросить:
1) Вы сказали:

whitefox в сообщении #740986 писал(а):

Никто не мешает, кроме не желательности распространения термина "подобие" на отношения не являющиеся эквивалентностью. Это легко может привести к недоразумению.

Вопрос: где в моей статье подобное недоразумение? - Я согласен, что если кто-то где-то механически воспользуется моим расширением, не задумываясь о деталях, которые Вы тут отметили, то он может получить недоразумение. Но ведь я никому не навязываю свое расширение: оно локального применения, также как и леммы, которые я доказываю, иначе их следовало бы назвать теоремами. Вот если бы, например, я писал учебник, то такое "подобие" было бы недопустимым.

2) Выше я написал:

bin в сообщении #740669 писал(а):

Можно различать подобные вершины относительно автоморфизма и подобные вершины относительно изоморфизма (т.е. относительно операции изоморфного отображения). Можно сделать такое примечание в статье. Думаю, что из контекста там везде ясно, о каком подобии идет речь.

Вопрос: Не считаете ли Вы, что такого примечания будет достаточно для статьи? Т.е. для доказательств, которые я там привожу?

3) Есть возможность и другого варианта: заменить слово "подобие" (в случае расширенного применения) другим словом, например, изоподобие.
Вопрос: что Вы думаете о таком варианте?

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

[whitefox]

bin в сообщении #741034 писал(а):

Вопрос: где в моей статье подобное недоразумение?

Не изучал Вашу статью в этом направлении.
Именно поэтому и написал "может" как указание на потенциальную возможность такого недоразумения.

bin в сообщении #741034 писал(а):

Вопрос: Не считаете ли Вы, что такого примечания будет достаточно для статьи? Т.е. для доказательств, которые я там привожу?

bin в сообщении #741034 писал(а):

Есть возможность и другого варианта: заменить слово "подобие" (в случае расширенного применения) другим словом, например, изоподобие.
Вопрос: что Вы думаете о таком варианте?

bin в сообщении #741034 писал(а):

Вопрос: так ли несовершенство этого определения существенно для доказательств статьи? - Вы поняли, что я хотел сказать этим определением, надеюсь, и другой читатель поймет.

Давя своё определение "расширенного подобия", Вы, как я полагаю, имели ввиду определить новое отношение эквивалентности, аналогичное классическому отношению подобия, но только определённое на более широком классе.
Думаю, что в своих последующих выкладках Вы неявно опирались на этот предполагаемый факт. Поэтому, если не изменить само определение, а только сделать примечание и изменить название, то это может серьёзно опорочить последующее доказательство. К тому же эти полумеры и не нужны. То отношение эквивалентности, которому Вы пытаетесь дать определение, реально существует. Нужно всего лишь правильно его описать.

Давая свой вариант определения я, на самом деле, имел ввиду примерно следующее:
Пусть $G$ и $G'$ графы, не обязательно различные. И пусть $V(G)$ и $V(G')$ соответствующие множества вершин. Будем говорить, что вершины $u$ и $v$, принадлежащие множеству $V(G)\cup V(G')$, подобны, если существует отображение $\pi$, являющееся, либо изоморфизмом графа $G$ на граф $G'$ (если $u$ и $v$ принадлежат разным графам), либо автоморфизмом графа $G(G')$ (если $u$ и $v$ принадлежат графу $G(G' \text{соответственно})$), такое что $\pi(u)=v$.

Это определение мне показалось слишком тяжеловесным, поэтому и был предложен более изящный вариант, который, к сожалению, оказался не тождественным приведённому определению.

bin в сообщении #741034 писал(а):

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

К сожалению, мне не достало времени, чтобы внимательно изучить Вашу статью.

[bin]

whitefox в сообщении #741092 писал(а):

Давая свой вариант определения я, на самом деле, имел ввиду примерно следующее:
Пусть $G$ и $G'$ графы, не обязательно различные. И пусть $V(G)$ и $V(G')$ соответствующие множества вершин. Будем говорить, что вершины $u$ и $v$, принадлежащие множеству $V(G)\cup V(G')$, подобны, если существует отображение $\pi$, являющееся, либо изоморфизмом графа $G$ на граф $G'$ (если $u$ и $v$ принадлежат разным графам), либо автоморфизмом графа $G(G')$ (если $u$ и $v$ принадлежат графу $G(G' \text{соответственно})$), такое что $\pi(u)=v$.

Это определение мне показалось слишком тяжеловесным, поэтому и был предложен более изящный вариант, который, к сожалению, оказался не тождественным приведённому определению.

А как Вам такой вариант?:
Определение. Вершины $u,v$ подобны, если выполняется какое-либо из условий:
1) $u=\alpha (v); u,v \in V(G)$;
2) $u=\pi (v); u \in V(G); v \in V(G')$;
где $\alpha $ - автоморфизм графа $G$;
$\pi $ - изоморфизм графа $G'$ на граф $G$.

[whitefox]

Вполне приемлемо, как рабочий вариант.

Нужно иметь ввиду, что областью определения этого отношения подобия является множество $V(G)\cup V(G')$ (областью определения классического отношения подобия служит множество $V(G)$). Этот факт желательно отразить в определении.

И так как вершины $u$ и $v$ принадлежат множеству $V(G)\cup V(G')$, то возможны три случая:
1) обе вершины принадлежат графу $G$;
2) обе вершины принадлежат графу $G'$;
3) эти вершины принадлежат разным графам.
Для каждого случая придётся указать свой критерий подобия.

[bin]

whitefox в сообщении #741173 писал(а):

Вполне приемлемо, как рабочий вариант.

Хорошо. Значит продолжим работу над этим вариантом.

whitefox в сообщении #741173 писал(а):

1) обе вершины принадлежат графу $G$;
2) обе вершины принадлежат графу $G'$;
3) эти вершины принадлежат разным графам.
Для каждого случая придётся указать свой критерий подобия.

Если бы я начал определение словами: пусть дано 2 графа $G$ и $G'$, то чисто формально должен был бы учесть случаи 1) и 2). Однако "хитрость" заключается в том, что я не начинаю определение с двух графов: первое условие говорит только об одном графе, и обозначить его можно произвольным образом - хотим как $G$, а хотим как $G'$ или $H$. Допустим, напишу я:

Вершины $u,v$ подобны, если выполняется какое-либо из условий:
1.1) $u=\alpha (v); u,v \in V(G)$;
1.2) $u=\alpha (v); u,v \in V(G')$;
2) $u=\pi (v); u \in V(G); v \in V(G')$;

Совокупность условий 1.1 и 1.2 - тавтология (типа "масло масляное") и одно из них лишнее (избыточное).

whitefox в сообщении #741173 писал(а):

Нужно иметь ввиду, что областью определения этого отношения подобия является множество $V(G)\cup V(G')$ (областью определения классического отношения подобия служит множество $V(G)$). Этот факт желательно отразить в определении.

Это я не понял. Возьмем, например, определение графа $G=(V,E)$. Какая область определения для $V$? Любое конечное множество вершин, если мы не рассматриваем инфинитные графы. Следует ли перегружать определение самоочевидными высказываниями?

[whitefox]

bin в сообщении #741309 писал(а):

whitefox в сообщении #741173 писал(а):

Нужно иметь ввиду, что областью определения этого отношения подобия является множество $V(G)\cup V(G')$ (областью определения классического отношения подобия служит множество $V(G)$). Этот факт желательно отразить в определении.

Это я не понял.

Вы определяете новое отношение -- "расширенное отношение подобия".
Всякое отношение имеет свою область определения, то есть множество между элементами которого это отношение устанавливается.
Формальное определение:

ВикипедиЯ писал(а):

n-местным (n-арным) отношением, заданным на множествах $M_1,M_2,\ldots,M_n$, называется подмножество прямого произведения этих множеств.

Иногда понятие отношения определяется только для частного случая $M=M_1=M_2=\ldots=M_n$ для отношения R. Тогда факт принадлежности n-ки этому отношению можно записать как:

$$\langle x_1, x_2, \dots, x_n\rangle\in R$$

В Вашем случае Вы определяете бинарное отношение на некотором множестве $M$. Вот это множество $M$ и есть область определения Вашего отношения.
Но, что представляет из себя множество $M$?
В классическом случае областью определения отношения подобия является множество $V(G)$, то есть множество вершин графа $G$.
Но Ваше "расширенное отношение подобия" определено для двух графов $G$ и $G'$, поэтому областью его определения является множество $V(G)\cup V(G')$, то есть объединение множеств вершин графов $G$ и $G'$.

[bin]

whitefox
Спасибо за разъяснение. Я понимаю, что такое область определения, я не понял другого: нужно ли перегружать определение столь очевидным фактом? Определение должно содержать однозначное описание определяемого объекта, его устройство, структуру, а какие-либо дополнительные свойства этого объекта (без которых и так достигается однозначность) в определении лишние. Поэтому если их указывать, то за рамками определения в последующем за определением тексте, например, в примечании. Но если в дальнейшем это примечание нигде не будет использовано в явном виде, то не будет ли оно выглядеть лишним?

Цитата:

Определение (математика) — введение нового понятия или объекта в математическое рассуждение путём комбинации или уточнения элементарных либо ранее определённых понятий. (Википедия)

[whitefox]

Всегда приходится выбирать компромисс между точностью и краткость.
Точное определение может стать малопонятным, а краткое неверным.
Выбор хорошего определения -- элемент творчества.

-- 02 июл 2013, 14:44 --

P.S. Извините за банальность.

[bin]

whitefox в сообщении #742362 писал(а):

Всегда приходится выбирать компромисс между точностью и краткость.
Точное определение может стать малопонятным, а краткое неверным.
Выбор хорошего определения -- элемент творчества.

Ok. Спасибо.

whitefox в сообщении #741092 писал(а):

bin в сообщении #741034 писал(а):

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

К сожалению, мне не достало времени, чтобы внимательно изучить Вашу статью.

С большим интересом жду момента, когда Вы прочтете статью целиком.

[bin]

Выложил исправления версии 6 препринта.

[Alexey Romanov]

Следствие 3 в препринте очевидно неверно. Возьмём $G=G'=K_3$. Все вершины в нём подобны, так что пусть $v=w$ и $v' \neq w'$.

[bin]

Алексей, спасибо, Вы совершенно правы. Мне уже указывали на этот баг (для $n>3$), и 24 октября я выложил исправление, о чем написал в предыдущем сообщении.
_________
Михаил Трофимов