2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 19, 20, 21, 22, 23, 24, 25, 26  След.
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение21.06.2013, 12:56 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение26.06.2013, 14:08 
Аватара пользователя


22/09/09

1907
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$ связные, то после объединения этих графов, они становятся различными компонентами связности одного графа. Вероятно, Ваш оппонент, когда делал Вам замечание, имел в виду следующее – определение подобных вершин у Харари дается для вершин одного графа, а Ваше обобщение переносит определение подобия на вершины разных графов. Поэтому его предложение сводится к тому, чтобы сделать вершины разных графов вершинами одного графа. Я в его, на мой взгляд, неудачном предложении не вижу "существа", вижу только желание сохранить форму.

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение27.06.2013, 11:33 
Заслуженный участник
Аватара пользователя


19/12/10
1546
По всей видимости, задавая вопрос своему Консультанту, Вы опустили в моём сообщении мотивировочную часть.
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$ подобны.
Нонсенс. :cry:

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение27.06.2013, 14:36 
Аватара пользователя


22/09/09

1907
whitefox в сообщении #740986 писал(а):
По всей видимости, задавая вопрос своему Консультанту, Вы опустили в моём сообщении мотивировочную часть.
Нет, я в точности скопировал Ваше сообщение и эту его часть. Скопирую и новое сообщение - интересно, что он мне посоветует. Ваше сообщение нужно серьезно обдумать, но прежде хочу спросить:
1) Вы сказали:
whitefox в сообщении #740986 писал(а):
Никто не мешает, кроме не желательности распространения термина "подобие" на отношения не являющиеся эквивалентностью. Это легко может привести к недоразумению.
:?: Вопрос: где в моей статье подобное недоразумение? - Я согласен, что если кто-то где-то механически воспользуется моим расширением, не задумываясь о деталях, которые Вы тут отметили, то он может получить недоразумение. Но ведь я никому не навязываю свое расширение: оно локального применения, также как и леммы, которые я доказываю, иначе их следовало бы назвать теоремами. Вот если бы, например, я писал учебник, то такое "подобие" было бы недопустимым.

2) Выше я написал:
bin в сообщении #740669 писал(а):
Можно различать подобные вершины относительно автоморфизма и подобные вершины относительно изоморфизма (т.е. относительно операции изоморфного отображения). Можно сделать такое примечание в статье. Думаю, что из контекста там везде ясно, о каком подобии идет речь.
:?: Вопрос: Не считаете ли Вы, что такого примечания будет достаточно для статьи? Т.е. для доказательств, которые я там привожу?

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение27.06.2013, 17:33 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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 писал(а):
Поэтому вопрос: а есть ли у Вас еще какие замечания к статье в целом, к приведенным в ней доказательствам?
К сожалению, мне не достало времени, чтобы внимательно изучить Вашу статью.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение27.06.2013, 18:53 
Аватара пользователя


22/09/09

1907
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$.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение27.06.2013, 23:26 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Вполне приемлемо, как рабочий вариант.

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение28.06.2013, 14:03 
Аватара пользователя


22/09/09

1907
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$? Любое конечное множество вершин, если мы не рассматриваем инфинитные графы. Следует ли перегружать определение самоочевидными высказываниями?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение02.07.2013, 10:23 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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'$.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение02.07.2013, 12:56 
Аватара пользователя


22/09/09

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение02.07.2013, 13:43 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение02.07.2013, 21:37 
Аватара пользователя


22/09/09

1907
whitefox в сообщении #742362 писал(а):
Всегда приходится выбирать компромисс между точностью и краткость.
Точное определение может стать малопонятным, а краткое неверным.
Выбор хорошего определения -- элемент творчества.
Ok. Спасибо.
whitefox в сообщении #741092 писал(а):
bin в сообщении #741034 писал(а):
Поэтому вопрос: а есть ли у Вас еще какие замечания к статье в целом, к приведенным в ней доказательствам?
К сожалению, мне не достало времени, чтобы внимательно изучить Вашу статью.
С большим интересом жду момента, когда Вы прочтете статью целиком.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение24.10.2013, 02:41 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение27.10.2013, 09:22 


31/01/09
96
Москва, мехмат МГУ, МИЭТ
Следствие 3 в препринте очевидно неверно. Возьмём $G=G'=K_3$. Все вершины в нём подобны, так что пусть $v=w$ и $v' \neq w'$.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение27.10.2013, 19:56 
Аватара пользователя


22/09/09

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 380 ]  На страницу Пред.  1 ... 19, 20, 21, 22, 23, 24, 25, 26  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group