Дан ориентированный граф (без петель). Известно, что для любой его вершины u и для любых двух её потомков x, y существует вершина t, такая что существуют пути из x в t и из y в t. Докажите, что для каждой вершины u графа существует единственная вершина v исходящей степени 0, такая что существует путь из u в v; при этом про граф известно, что а) в нём конечное число вершин и нет циклов; б) в нём бесконечное число вершин, но при этом нет никаких бесконечных путей (в частности, циклов нет).

задан 14 Июл '15 23:24

изменен 15 Июл '15 0:09

Здесь в тексте условия некоторые символы не читаются -- вместо них присутствуют "квадратики".

Судя по всему, здесь речь идёт об одной из формулировок леммы Ньюмэна (т.н. Diamond Lemma). Она доказывается по индукции. Позже могу написать подробнее. Здесь важно удобные обозначения ввести, чтобы проще было говорить о свойствах графа.

(14 Июл '15 23:33) falcao

@falcao А теперь? Вообще это задачка как бы на "процессы", но почти все процессовые задачи решаются и индукцией. Было бы интересно узнать решение, наскоком точно не выходит

(15 Июл '15 0:11) sapere aude

@sapere aude: теперь все символы видны -- это ровно то, на что я и думал. Сейчас напишу решение.

(15 Июл '15 2:56) falcao
10|600 символов нужно символов осталось
2

Это очень полезная теоретическая лемма о так называемых переписывающих системах (rewrite systems). Её в литературе часто называют Diamond Lemma. У её масса всяких полезных приложений. Можно посмотреть ссылку здесь. Я сейчас постараюсь написать всё максимально подробно.

Будем рассматривать вершины графа как некоторые объекты, которые можно упрощать. Если от вершины $%u$% к вершине $%v$% идёт направленное ребро, то будет писать $%u\to v$%. Это значит, что посредством одного элементарного преобразования $%u$% можно упростить до $%v$% (элементарно). Эти преобразования можно применять несколько раз. Предположим, что существует такая цепочка $%u=w_0\to w_1\to\cdots\to w_n=v$%, где $%n\ge0$% (сюда включается случай $%u=v$% при $%n=0$%). Тогда мы пишем $%u\stackrel{\ast}{\to}v$%. Это значит, что $%u$% можно привести к виду $%v$%.

Это общее описание, а на практике можно приводить таким способом что угодно: матрицы, многочлены, цепочки символов, и так далее. Эта теория работает в том случае, если у любого объекта имеется приведённая форма, причём в точности одна. Дадим определения. Объект $%v$% называется приведённым, если из вершины $%v$% не выходит ни одна стрелка, то есть не существует вершины $%w$% такой, что $%v\to w$%. Это означает, что объект $%v$% уже не упростить. Далее, приведённый объект $%v$% считается приведённой формой объекта $%u$%, если $%u\stackrel{\ast}{\to}v$%. В общем случае объект может не иметь ни одной приведённой формы, или иметь их несколько. Хорошим считается случай, когда у любого объекта приведённая форма существует и единственна.

Для существования приведённой формы достаточно того, чтобы в графе не было "нисходящих" путей (по стрелкам) бесконечной длины (в частности, не было петель). Это в точности то, что выполнено в пунктах а) и б), поэтому сразу примем это условие. Формально оно означает, что любая цепочка вида $%w_1\to w_2\to\cdots$% обрывается. Переписывающую систему с таким свойством обычно называют нётеровой (Noetherian, или ещё terminating).

Теперь введём ещё два стандартных понятия из этой теории. Система называется конфлюентной (confluent), если для любых объектов $%u$%, $%u_1$%, $%u_2$% таких, что $%u\stackrel{\ast}{\to}u_1$% и $%u\stackrel{\ast}{\to}u_2$%, существует объект $%v$% такой, что $%u_1\stackrel{\ast}{\to}v$% и $%u_2\stackrel{\ast}{\to}v$%. Смысл следующий: если мы привели объект $%u$% двумя разными способами к $%u_1$% и к $%u_2$%, то далее можно эти два объекта привести к одному и тому же объекту $%v$%. Легко видеть, что отсюда сразу следует единственность приведённой формы. Действительно, если $%u_1$% и $%u_2$% приведены, то из них более не выходит стрелок, и тогда свести их к одному и тому же $%v$% можно только при $%u_1=v=u_2$%, то есть приведённые формы одного и того же объекта равны.

Приведённая форма объекта $%u$% -- это и есть вершина $%v$% нисходящей степени $%0$% (приведённая), для которой имеется путь из $%u$% в $%v$% (то есть $%u\stackrel{\ast}{\to}v$%). Её единственность нам и надо установить. Если нарисовать пути на картинке, то при этом возникает "ромбик", почему лемму и называют "Diamond".

В условии нам дано свойство графа, похожее на конфлюентность. Оно называется локальной конфлюентностью (locally confluent rewrite system). Состоит оно в следующем: если объект $%u$% удалось элементарно привести двумя способами -- к виду $%u_1$% и к виду $%u_2$%, то есть $%u\to u_1$% и $%u\to u_2$%, то далее снова существует объект $%v$% такой, что $%u_1\stackrel{\ast}{\to}v$% и $%u_2\stackrel{\ast}{\to}v$%. Нетрудно видеть, что это частный случай конфлюентности. Смысл в том, что это условие проще проверять, так как на практике нам обычно бывают известны все элементарные способы приведения объекта, и две выходящие из одной вершины стрелки проще "сводить" вместе.

Итак, доказываем следующее утверждение. Пусть дана нётерова переписывающая система. Тогда из локальной конфлюентности следует её конфлюентность, а потому и единственность приведённой формы у любого объекта.

В доказательстве будем использовать такую форму индукции, которую часто называют нётеровой индукцией (Noetherian induction). Она напоминает "метод бесконечного спуска". Суть её в том, что если требуется доказать некоторое свойство $%P(u)$% для всех объектов $%u$%, то его достаточно доказать в предположении, что $%P(v)$% верно для всех "нисходящих" объектов $%v$% таких, что из $%u$% в $%v$% имеется путь положительной длины, то есть $%u\to\cdots\to v$%. Это значит, что $%u\stackrel{\ast}{\to}v$%, но при этом $%u\ne v$%. В частности, это верно в случае $%u\to v$%, то есть для всех "прямых потомков". Действительно, если мы это установили, то наличие контрпримера $%w_1$%, для которого неверно $%P(w_1)$%, означало бы, что $%P(w_2)$% неверно для некоторого $%w_2$% такого, что $%w_1\to\cdots\to w_2$%. А для $%w_2$% мы бы нашли контрпример $%w_3$% такой, что $%w_2\to\cdots\to w_3$%, и так до бесконечности, что противоречило бы нётеровости системы.

Доказывать мы будем свойство $%P(u)$% для каждой вершины $%u$%, состоящее в следующем: если $%u\stackrel{\ast}{\to}u_1$% и $%u\stackrel{\ast}{\to}u_2$%, то существует объект $%v$% такой, что $%u_1\stackrel{\ast}{\to}v$% и $%u_2\stackrel{\ast}{\to}v$%. Это и есть определение конфлюентности системы.

Начнём с тривиального случая, когда $%u=u_1$%. Тогда в качестве $%v$% подходит $%u_2$%, поскольку $%u_1=u\stackrel{\ast}{\to}u_2=v$% и $%u_2\stackrel{\ast}{\to}u_2=v$%. Аналогично поступаем, если $%u=u_2$%.

Теперь, если $%u\ne u_1$% и $%u\ne u_2$%, то "нисходящие" пути из $%u$% в $%u_1$% и $%u_2$% непусты, поэтому они начинаются элементарными преобразованиями $%u\to v_1$%, $%u\to v_2$% соответственно, где $%v_1\stackrel{\ast}{\to}u_1$% и $%v_2\stackrel{\ast}{\to}u_2$%. Воспользуемся теперь локальной конфлюентностью системы, находя для двух "стрелок" $%u\to v_1$% и $%u\to v_2$% такой объект $%w$%, для которого $%v_1\stackrel{\ast}{\to}w$% и $%v_2\stackrel{\ast}{\to}w$%. (Все эти вещи легче будут восприниматься, если нарисовать картинку с несколькими "ромбиками".)

Теперь применим предположение нётеровой индукции к вершине $%v_1$%. Для неё у нас имеются два пути: $%v_1\stackrel{\ast}{\to}u_1$% и $%v_1\stackrel{\ast}{\to}w$%. Поскольку $%P(v_1)$% верно по предположению, существует объект $%t_1$% такой, что $%u_1\stackrel{\ast}{\to}t_1$% и $%w\stackrel{\ast}{\to}t_1$%. Аналогично, применяя предположение $%P(v_2)$%, находим объект $%t_2$%, для которого $%w\stackrel{\ast}{\to}t_2$% и $%u_2\stackrel{\ast}{\to}t_2$%.

Последний шаг: рассматриваем вершину $%w$%, для которой у нас имеется непустой путь из $%u$%, а именно, $%u\to v_1\stackrel{\ast}{\to}w$%. Значит, $%P(w)$% верно по предположению нётеровой индукции, и поэтому существует объект $%v$% такой, что $%t_1\stackrel{\ast}{\to}v$% и $%t_2\stackrel{\ast}{\to}v$%. Объект $%v$% является искомым, поскольку $%u_1\stackrel{\ast}{\to}t_1\stackrel{\ast}{\to}v$% и $%u_2\stackrel{\ast}{\to}t_2\stackrel{\ast}{\to}v$%.

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

ссылка

отвечен 15 Июл '15 4:11

@falcao спасибо громадное за такое популярное изложение! Так много незнакомых конструкций для одного доказательства. Мне кажется, что я все понял, но пока еще похожу денек-другой и попробую повторить доказательства по смыслу, так как упражнений особо нет, то наверное только так в этом можно убедиться)

(15 Июл '15 22:43) sapere aude

@sapere aude: эта тематика мне весьма близка, и я эту лемму много раз применял -- почему и написал подробно. Всё это дело хорошо работает для преобразований слов в группах и полугруппах.

(15 Июл '15 23:04) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,122
×156

задан
14 Июл '15 23:24

показан
520 раз

обновлен
15 Июл '15 23:04

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru