?

Log in

No account? Create an account
раскраска дороги (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

раскраска дороги (математическое) [сент. 14, 2010|06:36 pm]
Anatoly Vorobey
(эта запись может быть интересна читателям с познаниями в математике и сочувствующим)

На днях я прочитал о интересной задаче из теории графов - гипотеза о раскраске дороги. Эта гипотеза была открытой в течение 37 лет, но три года назад ее доказал израильский математик Авраам Трахтман. Доказательство оказалось довольно элементарным, и с некоторыми сложностями (поскольку мозги атрофировались) я смог его прочитать и понять, и даже попробую в этой записи объяснить.

Задачу можно объяснить на таком примере. Представьте себе карту города, на которой на каждом перекрестке можно поехать в одну из четырех сторон - на север, юг, восток и запад. Если машина начинает с какого-то перекрестка и следует по какому-то списку указаний - "север, север, восток" итд. - то она приедет в итоге на какой-то другой перекресток. Можно ли найти такой список указаний, возможно длинный, который приведет машину в одно и то же место, независимо от того, где она начала? Если карта выглядит как Манхэттен - регулярная решетка - то нет, но может, в ней есть много тупиков и неожиданных поворотов?

Или другой пример. Ваш друг застрял в лабиринте, в котором нужно найти центр, и позвонил вам с просьбой помочь. Вы знаете, как устроен лабиринт, но не знаете, где ваш друг. Может ли быть такая последовательность команд, которая точно приведет вашего друга в центр, где бы он ни был?

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

В общем случае, пусть есть направленный граф G - с ребрами-"стрелками" между вершинами. Пусть у этого графа есть равномерная исходящая степень d - это значит, что из каждой вершины выходит ровно d ребер. Входить при этом в каждую отдельную вершину может разное количество, необязательно d. Пусть у нас есть набор из d букв какого-то алфавита, которые мы будем называть "цветами". Тогда "раскраска" графа задается назначением для каждой вершины всех d букв для d ее исходящих ребер. Так что если мы "находимся" в какой-то вершине, и хотим "пойти" куда-то согласно цвету α, то раскраска всегда скажет нам, по какому ребру нам надо идти к какой новой вершине. "Словом" назовем любую последовательность букв-цветов. Тогда, если в графе задана раскраска, и x - какая-то вершина, а w - какое-то слово, то xw обозначает вершину, к которой мы придем, начиная с x и следуя слову w.

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

У этой проблемы есть применения в нескольких разных областях, о которых можно прочитать например в википедии. Скажем, в компьютерных науках, в теории автоматов. Граф с раскраской можно рассматривать как детерминистский конечный автомат, в котором вершины - состояния, а ребра указывают, как между ними переходить. Предположим, мы управляем этим автоматом на расстоянии, пересылая команды по какому-то информационному каналу, и из-за каких-то поломок этот канал был загрязнен, автомат получил какие-то ошибочные инструкции, и сейчас мы вообще не знаем, в каком он состоянии. Тогда, если есть синхронизирующее слово, мы можем привести его в известное состояние, независимо от того, где он сейчас.

Итак, когда существует синхронизирующая раскраска? Гипотеза раскраски дороги накладывает на граф еще два ограничения (кроме того, что из каждой вершины выходит ровно d ребер). Во-первых, граф должен быть сильно связным - это значит, что из любой вершины к любой другой существует маршрут. Во-вторых, граф должен не быть периодичным. Представим себе, что все вершины графа можно разбить на множества V1, V2, ... Vn, так, что любое ребро графа соединяет вершины из каких-то Vi и Vi+1 или Vn и V0. Между вершинами в каждой V ребер нет, и "перескакивать" между любыми V они тоже не могут, только по порядку. Такой граф называется периодичным. Ясно, что у такого графа синхронизирующей раскраски быть не может, потому что как ни раскрашивай и по каким словам ни ходи, две вершины в разных Vi никога не сойдутся вместе - они так и будут ходить по циклу.

Теорема о раскраске дороги говорит, что этих условий достаточно: любой не периодичный, сильно связный направленный граф с d ребер из каждой вершины имеет синхронизирующую раскраску. Впервые ее сформулировали как гипотезу в 1970-м году, и с тех пор было много частичных результатов, доказывающих частные случаи, но полное доказательство появилось только в 2007-м. Далее следует мой пересказ почти всего доказательства (кроме одной технической леммы).

Периодичность

Прежде всего, заменим условие не-периодичности другим, эквивалентным ему. Граф периодичен тогда и только тогда, когда существует число N>1, на которое делится длина любого цикла в графе. Т.е. наше требование не-периодичности равносильно тому, что нет такого N, или иными словами наибольший общий делитель длин всех циклов в графе равен 1. Мы докажем, что любой граф, выполняющий это условие, имеет синхронизирующую раскраску.

Доказать, что периодичность эквивалентна условию "есть N>1, на которое делится длина любого цикла", тривиально в одну сторону и легко в другую. Если вы готовы принять это на веру, можете легко пропустить остаток этого абзаца, для всего остального доказательства это неважно. Если граф периодичен, т.е. можно разделить вершины на множества V1, V2, ... Vn, так, что ребра идут между ними по циклу, то очевидно, что длина любого цикла должна делиться на n, т.е. новое условие выполняется. Это тривиальное направление, но для нашей замены нужно как раз второе направление. Предположим, что есть такое N>1, на которое делится длина любого цикла. Построим в нашем графе какое-нибудь направленное остовное дерево (spanning tree) с корнем в вершине r. К любой вершине x есть маршрут в этом дереве начиная от корня длиной l(x). Мы утверждаем теперь, что для любого ребра p-->q в графе выполняется, что l(q) = l(p) + 1 (mod N). Если это утверждение верно, то из него следует сразу, что мы можем разбить все вершины на множества Vi согласно l(x) mod N, и граф будет периодичен. Почему же это утверждение верно? Если p-->q является частью остовного дерева, то это очевидно, потому что тогда просто l(q) = l(p) + 1. Если это не так, то запишем маршруты от корня r к вершинам p,q как Rp и Rq. Пусть также Rr означает маршрут от q обратно в r в графе (граф связный, так что он существует). Тогда мы можем записать два цикла: Rp p-->q Rr, и RqRr. Согласно условию, длины этих циклов делятся на N, вычитая и сокращая общие величины, получаем, что l(p)+1 = l(q) mod N, что и требовалось доказать.

Стабильная дружба и индукция

Пусть задана некая раскраска графа G. Назовем две вершины p,q друзьями, если какое-то слово w приводит их в одну вершину: pw = qw. Назовем p,q врагами, если им "никогда не сойтись". Назовем p,q стабильными друзьями, если после выполнения любого слова w они остаются друзьями: pw возможно не приходит в ту же вершину, что qw, но после еще какого-то w' сможет прийти. Стабильные друзья никогда не станут врагами.

Отношение стабильности между вершинами является, во-первых, эквивалентностью (оно рефлексивно, симметрично и транзитивно), а во-вторых сохраняется структурой графа: если p,q стабильные друзья, p соединено ребром с p', q с q', и эти ребра одного цвета, то p' и q' тоже стабильные друзья. Это значит, что стабильная дружба является конгруэнтностью и на нее можно поделить: создать новый граф G', вершины которого будут классы эквивалентности по стабильной дружбе в G. Если в G есть хоть одна стабильная пара, то G' будет размером меньше G. Более того, если в исходном графе G из каждой вершины выходило d ребер, то и в G' это будет так. Например, если P - вершина нового графа, являющаяся классом эквивалентности исходных вершин p1, p2..., а α - любой цвет, то ребра p1--α-->q1, p2---α-->q2, итд. все ведут в вершины q1, q2..., находящиеся в стабильной дружбе между собой, и потому лежащие в одной новой вершине Q, так что все эти ребра становятся новым ребром P--α-->Q. И так для каждого из d цветов.

Более того, если G был не-периодичным, то и G' таков. Ведь - используя наше альтернативное определение периодичности - любой цикл в G превращается в цикл в G', так что если все длины циклов в G' делятся на n > 1, то то же верно касательно всех циклов в G. Так что периодичность G' влечет периодичность G.

Предположим, что в G' удалось найти синхронизирующую раскраску. Ее можно использовать теперь в G вместо той раскраски, с которой мы начали: любое ребро p-->q получит новый цвет согласно новому цвету ребра P-->Q. Немного точнее следует сказать так: в каждой вершине P графа G' новая раскраска задается какой-то перестановкой всех цветов πP: ребро, которое было покрашено в цвет α получает новый цвет πP(α). Тогда в исходном графе G в каждой вершине p из класса стабильности P мы применяем ту же перестановку πP для перекраски ее ребер. Новая раскраска графа G вообще говоря определяет какие-то новые понятия "дружбы", "вражды" и "стабильности", не идентичные исходным. Но тем не менее если две вершины p, q были стабильными друзьями в старой раскраске - принадлежали одному классу P - то они останутся стабильными друзьями в новой. Это потому, что любую последовательность w, приводящую p,q в одну вершину, можно "перевести" из старой раскраски в новую или наоборот, пользуясь перестановкой πP в каждой вершине p по дороге. Поскольку p,q стабильны в старой раскраске и остаются таковыми "всю дорогу", каждая промежуточная пара вершин pn, qn по дороге от p,q к общей вершине будет стабильной, т.е. лежать внутри одной вершины Pn и получать поэтому одинаковую пермутацию πPn.

Новая окраска является синхронизирующей для G', т.е. какая-то последовательность w приводит все вершины в одну вершину P. Если мы теперь применим w к новой окраске в G, то все вершины сойдутся куда-то "внутрь P". Как указано выше, все вершины внутри класса P остаются стабильными и в новой раскраске, что значит, что теперь можно продолжать w, снова и снова сводя вместе оставшиеся еще отдельными пары вершин, пока все не сойдется в одну вершину G. Таким образом, новая раскраска является синхронизирующей для G.

Из всего этого следует, что для того, чтобы доказать теорему, достаточно доказать, что в любом графе, отвечающем условиям, найдется раскраска, в которой есть пара стабильных друзей. Потому что тогда от графа G можно перейти к графу G' меньше размером, и он тоже отвечает всем условиям. С помощью индуктивного аргумента можно предположить, что для графов меньшего размера проблема уже решена, и тогда синхронизирующая окраска для G' будет также синхронизирующей для G.

Клики и максимальные множества

Для любого подмножества A вершин графа и слова w, Aw обозначает множество вершин, к которым мы придем, начиная со всех вершин A и следуя слову w. Если мы начинаем со всех вершин графа вообще, то обозначим это Gw. В такой нотации синхронизирующая раскраска означает, что есть w такое, что Gw - множество из одного элемента.

Если множество вершин A имеет форму Gw для какого-то w, и кроме того любые две вершины в A - враги, т.е. никогда не сойдутся, назовем A кликой. Клики существуют, потому что мы всегда можем начать с целого G, взять пару вершин-друзей, пройти по w, которое их соединяет, и уменьшить число вершин на единицу; продолжать так, пока не останутся одни враги или не останется только одна вершина - тоже в таком случае клика, просто тривиальная.

Если A клика, то для любого слова w Aw - тоже клика; это ясно потому, что враги остаются врагами. Если x - любая вершина графа, то существует клика, включающая x. Это вытекает из того, что существует какая-то клика A (см. предыдущий абзац); если p - вершина в ней, то есть слово w, ведущее из p в x, т.к. граф связный; тогда Aw - клика, включающая x.

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

Для того, чтобы лучше понять, как устроены клики, оказывается полезным назначить веса вершинам в графе. Покажем, что у нас есть способ назначить положительный вес w(x) каждой вершине x, так, что если для любой вершины x просуммировать веса всех вершин, из которых идут ребра в x, то получится d*w(x), где d - число ребер из каждой вершины. Это следует из линейной алгебры, и если вы не знаете, что такое собственное значение, пропустите оставшуюся часть этого абзаца и примите существование таких w(x) на веру. Если M - матрица графа G (в ячейке (i,j) стоит 1, если есть ребро i-->j, и 0, если нет такого ребра), то w(x), как я их описал, являются элементами собственного вектора слева у этой матрицы для собственного значения d. Мы знаем, что такой вектор существует, потому что d является собственным значением: у него есть тривиальный собственный вектор справа (1,1,....1) - это сразу вытекает из того, что из каждой вершины выходит ровно d ребер.

Если A - любое множество вершин, то w(A) обозначает сумму весов всех вершин из A; а w(G) - сумма весов всех вершин в графе. Кроме того, если s - любое слово, то As-1 пусть обозначает множество вершин, к которым приходишь из A, если идти "в обратную сторону" по s, на каждом шагу заменяя каждую вершину на те вершины (если они есть), которые идут к ней соответствующим цветом.

Рассмотрим теперь все множества вершин, которые можно свести вместе в одну точку, т.е. такие A, что для какого-то w Aw содержит только одну вершину. Те множества A, которые среди всех таких обладают максимальным весом w(A), назовем максимальными множествами. Если раскраска синхронизирующая, то весь граф G - максимальное множество (единственное), но в противном случае это не так.

Если A - любое множество вершин, то сумма всех w(Aα-1), где α пробегает все d цветов, равна d*w(A) - это просто обобщение главного свойства веса с одной вершины на множество вершин A. Если к тому же при этом A - максимальное множество, то каждый из w(Aα-1) не может быть больше w(A), ведь эти множества тоже сводятся в одну вершину. А раз сумма d этих весов равна d*w(A), выходит, что каждый из них равен w(A), и все эти множества тоже максимальны. Отсюда сразу следует, что если A максимально, то Aw-1 тоже максимально для любого слова w.

Максимальные множества полезны тем, что непересекающимися их экземплярами можно покрыть весь граф. Докажем это.

Пусть у нас есть набор максимальных множеств A1...An, не пересекающихся попарно, и приводимых к одиночным вершинам a1...an одним и тем же словом w (в начальном случае будет n=1 и всего одно множество, так что начать легко). Ясно, что все a1...an отличаются друг от друга, ведь иначе можно было бы еще больше расширить максимальное множество за счет элементов другого с той же конечной вершиной. Предположим, что все Ai вместе еще не исчерпали все вершины G, и пусть x - вершина вне всех Ai. Поскольку граф связный, есть какой-то маршрут h из a1 в x. Тогда n максимальных множеств Aih-1w-1 переходят по слову whw в конечные вершины a1...an, а максимальное множество A1 переходит в какую-то вершину Awhw = (Aw)hw = (a1h)w = xw. Эта вершина xw тоже должна отличаться от всех a1...an, потому что иначе максимальное множество Ai можно было бы пополнить элементом x. А раз все эти n+1 множеств - все Aih-1w-1 плюс A1 - переходят по whw в разные вершины, они все попарно непересекаются. Такое расширение будем продолжать, пока не останется вершин вне набора.

Итак, мы можем покрыть весь граф G непересекающимися максимальными множествами. Поскольку они максимальные, у них у всех одинаковый весь wmax, и поэтому их количество в покрытии равно Nmax = w(G)/wmax.

Теперь рассмотрим любое множество A, состоящее из попарных врагов. Например, клика - пример такого множества (и кроме того имеет вид Gw). Внутри максимального множества не может оказаться пара врагов, потому что тогда оно не могло бы сойтись. Значит, в покрытии из Nmax максимальных множеств каждое содержит не более одного члена A, так что размер A не более чем Nmax. В частности, это верхний предел размера любой клики.

Пусть A клика, имеющая вид Gw, где w какое-то слово. Тогда G = Aw-1, и соответственно w(G) равно сумме w(aw-1), где a пробегает все вершины A. Количество слагаемых, согласно предыдущему абзацу, не больше Nmax, а каждое множество aw-1 можно свести в одну точку (в точку a словом w), поэтому его вес не больше максимального wmax. Раз вся сумма равна w(G) = Nmax*wmax, мы заключаем, что количество слагаемых в точности равно Nmax, а каждое слагамое в точности равно wmax. Мы доказали, что у всех клик одинаковый размер: ровно Nmax элементов.

Пусть имеются две клики A и B, так, что внутри A все элементы общие с B, кроме одного: |A| - |A∩B| = 1.

Поскольку у A и B одинаковый размер, имеем также |B| - |A∩B| = 1, т.е. у A и B все элементы общие, кроме одной вершины p в A, и одной вершины q в B. Мы хотели бы доказать, что эти вершины p,q являются стабильными друзьями. Если это не так, то какое-то слово w делает их врагами, т.е. pw и qw враги. Как было показано выше, Aw и Bw тоже являются кликами, и очевидно, что у них опять-таки общие все элементы, кроме врагов pw и qw. Тогда множество Aw ∪ Bw является множеством попарных врагов. Действительно, в нем все элементы Aw попарные враги, потому что это клика; то же верно насчет элементов Bw; и осталась только пара pw,qw - тоже враги. Но у этого множества есть Nmax+1 элементов, а выше мы показали, что в любом множестве попарных врагов не может быть больше Nmax элементов. Это противоречие, и поэтому pw и qw не могут быть врагами для любого w. Иными словами, p и q - стабильные друзья.

Остовные графы и клики

Пусть из данного графа G мы взяли все вершины, и из каждой вершины выбрали только одно исходящее ребро. Такой выбор определяет поддграф, который назовем остовным графом (spanning graph). Остовных графов может быть очень много разных, но подумаем немного о том, как они выглядят. Пусть есть некий остовной граф R. Если мы возьмем в нем любую вершину x, и начнем следовать по его ребрам, то каждый раз у нас будет единственный выбор, потому что в R из каждой вершины выходит только одно ребро, и рано или поздно мы замкнем цикл. Может быть, этот цикл не замкнется на x, а замкнется где-то "дальше" - например, x-->y-->z-->s-->y. Тогда от x будет вести "хвост" к этому циклу. Если мы начнем с какой-то другой вершины, тоже обязательно придем к циклу - этому или какому-то другому. Получается, что любая вершина R либо лежит на цикле (которых может быть несколько), либо является частью "хвоста", который приводит к циклу. Это значит, что R выглядит так: какое-то количество циклов, и на них построены какое-то количество "перевернутых" деревьев: каждое дерево не начинается, а кончается в "корне", который лежит на одном из циклов.

Каждой вершине графа мы можем присвоить уровень, соответствующий ее расстоянию до цикла в данном остовном графе R. Вершины, которые лежат на цикле, имеют уровень 0, а вершины, которые лежат на дереве, присоединенном к циклу, получают уровень, равный расстоянию в их дереве до "корня", лежащего на цикле. У каких-то вершин нашего графа есть максимальный уровень L. Возможно, он вообще равен 0 - т.е. нет никаких деревьев, одни циклы. Возможно, он больше нуля, и вершины этого максимального уровня лежат на всяких разных деревьях, подсоединяющихся к разным циклам или к одному.

Мы хотим так выбрать остовной граф R, чтобы все вершины максимального уровня лежали на одном и том же дереве. Интуитивно можно поверить, что это можно сделать, потому что если это не так - например, они раскиданы по разным деревьям - то можно выбрать одну из таких максимальных вершин x и увеличить ее уровень, присоединив к R какое-то ребро, идущее в x. Тогда какое-то другое ребро придется выкинуть, и не факт, что это не повредит чему-то другому... но это технический вопрос, о котором позже. Я просто пытаюсь сказать, что это интуитивно не выглядит очень сложным.

Пока что предположим, что можно выбрать R так, чтобы все вершины максимального уровня лежали на одном и том же дереве. Это дерево предполагается нетривиальным, т.е. максимальный уровень L > 0. Исходя из этого предположения, мы построим раскраску, и в ней клики A и B, отвечающие условию предыдущего раздела, и это докажет, что в этой раскраске есть стабильная пара друзей.

Раскраска будет следующая: выберем какой-то цвет α, и все ребра в графе R покрасим в этот цвет, а все остальные ребра в графе G - в какие-то другие цвета любым образом (если цвет есть только один, то R совпадает с G, так что проблемы нет). Таким образом, слова, состоящие из цвета α, "продвигают" вершины R по их деревьям по направлению к циклам, а потом гоняют их по циклам. Нам только такие слова и понадобятся.

Пусть x - любая вершина максимального уровня L в R, и пусть K - любая клика, включающая в себя x; мы знаем, что такая клика существует. Может ли K включать в себя еще какую-то вершину максимального уровня L? Согласно нашему предположению, все такие вершины находятся в том же дереве, что и x, а значит, слово αL приводит их в то же место, что и x - а именно, в корень этого дерева, лежащий на цикле. Значит, все такие вершины - друзья x, и не могут поэтому лежать в одной с ней клике. Поэтому, кроме x, K может включать только вершины меньшего уровня.

Посмотрим на множество A = KαL-1. Это тоже клика, и в нем все вершины, кроме x, достигли каких-то своих циклов в R, потому что все вершины A, кроме x, имеют уровень меньше L. Только x остался еще вне цикла, на расстоянии ровно 1 до своего корня на цикле. Теперь возьмем какое-то число m, кратное всем длинам циклов в R - например, произведение всех длин циклов. У m есть такая особенность, что если вершина y находится на цикле в R, то слово αm возвращает ее на место: yαm = y. Посмотрим на клику B = Aαm. Все вершины A, кроме x, лежали на циклах, и поэтому остались там же в B; и только x наконец вошла в свой цикл и улеглась там где-то. Это значит, что пересечение A и B содержит все вершины A, кроме одной: |A| - |A∩B| = 1. Но это как раз и значит, согласно предыдущему разделу, что у нашей раскраски есть стабильная пара, что и требовалось доказать.

Построение максимального уровня.

Осталось доказать, что всегда можно выбрать остовной граф R так, чтобы в нем был нетривиальный максимальный уровень L > 0, и все вершины этого уровня лежат на одном дереве.

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

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

Далее, предположим на секунду, что из какой-то вершины p все d ребер ведут в одну и ту же вершину q. Это разрешено условиями, но в таком случае мы этот набор ребер назовем связкой. Наше второе ограничение такое: нет такой вершины r, в которую ведут две связки из разных вершин p и q. Почему мы можем его наложить? Потому что если из p и q идут связки в r, то при любой раскраске p,q сойдутся в вершину r после первого же цвета, и поэтому они стабильные друзья. Так что в этом случае нам не нужны все построения остовных графов и клик, мы получаем стабильных друзей сразу. Поэтому мы можем предположить, что это не так.

Наконец, докажем, что всегда существует остовной граф R, в котором не все вершины лежат на циклах, а есть какие-то нетривиальные деревья. Выберем какой-то R, и предположим, что в нем все вершины лежат на циклах. Если бы в графе G все ребра лежали в связках - т.е. всегда все d ребер, выходящие из одной вершины, вели в одну и ту же вершину - тогда выбор R включал бы в себя всего лишь выбор одного ребра из каждой связки. В таком случае в R мог бы быть только один цикл (ведь несколько циклов в R никак не могли бы соединиться между собой в связном графе G - все ребра G соединяют только те же вершины, что и ребра R, потому что это связки - а раз G связный, это невозможно), и любой цикл в G просто выбирает другие ребра из связок этого цикла, но по сути дела это тот же самый цикл, той же самой длины. Но это значит, что длины всех циклов в G делятся на эту длину, что как раз противоречит не-периодичности G. Поэтому не может быть, чтобы в G все ребра лежали на связках, а значит, есть какие-то два ребра p-->q в R, и p-->s вне R (длинное рассуждение про связки нам нужно было, чтобы доказать, что какое-то ребро из p не просто не лежит в остовном графе, но и ведет в другую вершину s). Тогда заменим p-->q на p-->s, и это "разобьет" цикл, создав в нем какой-то нетривиальный хвост. Этот хвост и даст нам нетривиальное дерево в новом графе.

Теперь мы можем из всех остовных графов R, в которых есть нетривиальные деревья, выбрать какой-то R, максимальный по количеству вершин на циклах. T.e. в нем есть вершины и не на циклах, но кроме этого ограничения, количество вершин на циклах максимизировано. В этом графе есть какие-то вершины максимального уровня L, и мы можем предположить, что они есть на деревьях, ведущих к разным корням, иначе мы уже добились, чего надо. Выберем одну такую вершину x. Мы хотим так изменить граф, чтобы эта вершина стала частью более длинного маршрута в дереве, длиннее, чем L, а остальные деревья не изменились, и тогда максимальный уровень будет только в одном дереве, что нам и нужно. Изменить граф можно тремя способами:

a) взять какое-то ребро y-->x, и добавить его в R, а существующее там ребро y-->z выбросить;
b) взять ребро b-->r, которое как раз последнее на пути из x в его цикл (r на цикле), и выбросить его, а добавить какое-то другое b-->z.
c) взять ребро c-->r, являющееся частью цикла, и его выбросить, а добавить какое-то другое c-->z.

В лемме 7 статьи Трахтмана подробно доказывается, что одно (или в каком-то случае два) из этих изменений приводят к желанному результату. В процессе используется как максимальность R (если какое-то изменение ведет к графу с большим, чем в R, числом вершин на циклах, это противоречит его максимальности), так и определенное выше условие, что нет вершины, в которую ведут две связки. В итоге мы в любом случае получаем такой граф R, в котором все вершины максимального уровня лежат на одном нетривиальном дереве.

Update, неделю спустя: я решил все же сделать эту запись полностью самодостаточной и пересказать также доказательство леммы, на которую я сослался в предыдущем абзаце. Лучше бы это сделать с диаграммой, но мне не хочется ее рисовать или выдирать из статьи, поэтому я попробую словами. Итак, представим, что у нас есть остовный граф R, в котором есть нетривиальные деревья, и из всех таких графов в нем максимальное количество вершин лежат на циклах. Мы стремимся преобразовать R в такой остовный граф, в котором все вершины максимального уровня лежат на одном дереве; как только в процессе попыток мы получаем такой граф, то сразу заканчиваем (и нас не волнует, что максимальность графа по кол-ву вершин на циклах при этом может потеряться, она нам сама по себе не важна, мы только пользуемся ей в процессе). Пусть x - вершина максимального уровня L, T - дерево, на котором она лежит, r - вершина на цикле C, на которой заканчивается Т, b-->r - последнее перед r ребро на пути от x к циклу C. Мы можем предположить, что есть еще какие-то деревья, присоединяющиеся к этому циклу или другим, на которых есть вершины уровня L - иначе уже все сделано. Из этого следует, что если нам удастся получить из T дерево с элементом большей степени, чем L, и не удлинить эти другие деревья, то мы закончили.

Сначала попытаемся сделать операцию a) выше: возьмем какое-то ребро y-->x в G - оно существует, т.к. граф связный и без петель, и не лежит в R, т.к. x максимального уровня. Добавим его в R, а какое-то y-->z, которое там было раньше, выкинем. Если y лежит на дереве T, то y-->x замыкает новый цикл, и в новом графе больше вершин лежат на циклах, и все еще есть нетривиальные деревья (как минимум те другие, что были в R), что противоречит максимальности R. Если y не лежит на T, и y-->z не является частью цикла C, то удаление y-->z не разбивает этот цикл, а добавление y-->x удлиняет максимальный уровень дерева T как минимум на единицу, а другие деревья не удлиняет, так что мы закончили. Остается вариант, когда y-->z лежало на цикле C, который теперь разбился, и образовался новый цикл: от r до y, потом y-->x, потом от x до r по бывшему дереву. Длина этого цикла равна l(ry)+1+L, а длина старого цикла C равна была l(ry)+1+l(zr). Новый цикл не может быть длиннее старого, это противоречит максимальности R, поэтому видим, что L ≤ l(zr), т.е. длине маршрута от z до r в старом цикле. С другой стороны, в новом графе теперь у вершины z уровень как минимум l(zr), и если это больше L, то мы закончили. Так что можно предположить, что l(zr)=L. Подытожим: предполагаем, что a) не работает, и тогда мы знаем, что y-->z лежит на цикле C, l(zr) = L.

Теперь попробуем операцию b): заменим ребро b-->r на какое-то другое ребро b-->d. Посмотрим, где лежит новая вершина d. Если на дереве T, то мы создали новый цикл, не разбив предыдущий, и опровергли максимальность R. Если на другом дереве, то у максимальных вершин T, включая x, теперь будет уровень больше L, а у других деревьев не будет, и мы закончили. Если на другом цикле, не C, то мы теперь сделаем заодно с b) еще и a): поскольку мы знаем, что y-->z лежит на C, то эта операция разобьет C, но не новый цикл, к которому теперь подключено дерево Τ, и на этом дереве теперь будут вершины уровня, большего L, и мы опять закончили.

Остается вариант, когда b-->d тоже подключается к циклу C, в каком-то другом месте, чем r, или в том же месте и тогда d=r. После того, как мы заменили b-->r на b-->d, мы получили ту же ситуацию, что изначально - дерево T, вершина x уровня L итд. - только к циклу дерево подключается теперь через вершину d. Рассматривая теперь операцию а), мы заключаем (предполагая, что она не работает), что l(zd) = L, точно так же, как раньше заключили, что l(zr) = L. Но если l(zd)=l(zr), т.е. расстояние по циклу от z одинаковое до d и r, то это одна и та же вершина: d=r. Итак, если b) не работает, то любое ребро из b должно вести в r, т.е. ребра из b образуют связку.

Наконец, рассмотрим ребро c-->r, лежащее на цикле C. Поскольку мы можем предположить, что все ребра из b лежат на связке, ведущей в r, а также можем наложить ограничение, о котором говорили выше, что не может быть двух связок, ведущих в одну вершину, не все ребра из c ведут в r, а есть какое-то ребро c-->e. Заменим c-->r на c-->e. Где может лежать вершина e? Не на дереве T, потому что это "расширило" бы цикл C, противореча максимальности R. Значит, e лежит на другом дереве или на другом цикле, или даже на том же цикле C, но не в вершине r. Тогда дерево T, до того, как оно подключается к циклу, удлиняется теперь как минимум на одно ребро, исходящее из r, а может и на больше (только на одно, если e лежит сразу после r, и c-->e замыкает цикл C заново, выводя из него только r). Значит, у вершины x и других максимальных вершин T уровень теперь не меньше L+1, а другие деревья не удлинились, и опять-таки мы получили, что надо.
СсылкаОтветить

Comments:
[User Picture]From: vvagr
2010-09-14 04:53 pm
Ниасилил, при чём настолько, что даже не могу понять - это доказательство конструктивное или нет? А любопытно.
(Ответить) (Thread)
[User Picture]From: avva
2010-09-14 10:53 pm
Вообще говоря, нет. Главная часть док-ва - нахождение стабильной пары вершин - на первый взгляд выглядит неконструктивной, но ее как раз можно изменить так, чтобы была конструктивной. Но потом надо поделить граф на отношение стабильности на всем графе, и конструктивного способа его построить статья не предлагает. Формально говоря, его можно найти конструктивно полным перебором, как и синхронизирующую раскраску можно найти полным перебором - все объекты конечного ограниченного размера, кроме слов-команд, а их можно проверять только до тех пор, пока состояния не начнут неизбежно повторяться. Но это не очень интересно.
(Ответить) (Parent) (Thread)
[User Picture]From: botya
2010-09-14 07:07 pm
Ниасилил.

Интересно, придумают когда-нибудь математики более-менее адекватный способ иллюстрировать свои предположения? Хотя бы комиксами.
(Ответить) (Thread)
[User Picture]From: matholimp
2010-09-14 08:36 pm

Комиксами???

Иллюстрировать для кого и ради чего?
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2010-09-14 08:32 pm
Я б осилил (первая половина очень понятно написано), но надо лекцию готовить.
(Ответить) (Thread)
[User Picture]From: status_constr
2010-09-14 08:58 pm
нельзя не заметить, что виновник торжества, 65-летний профессор Бар-Иланского университета, бывший свердловчанин Авраам Трахтман - весьма примечательная личность и автор нескольких прелюбопытных публицистических текстов на родном (русском то есть) языке. Чтобы их обнаружить, достаточно погуглить его имя.

Различные изложения приведенной в посте теоремы и доказательства можно найти, погуглив опять-таки его имя, но транскрибированное нестандартно: Avraham Trahtman или Avraham Trakhtman
(Ответить) (Thread)
From: markvs
2010-09-15 01:17 am
>автор нескольких прелюбопытных публицистических текстов на родном (русском
>то есть) языке. Чтобы их обнаружить, достаточно погуглить его имя.

Может, у меня Гугл неправильный, но я эти тексты найти не могу. Дайте ссылку, пожалуйста.

С политическими взглядами Абрама Наумовича я немного знаком. Хорошо, что avva про них не знает. Подозреваю, что иначе не стал бы он объяснять доказательства такого человека. :)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2010-09-15 06:59 am
Интересное подозрение. Любопытно, вы понимаете, насколько оно оскорбительно, или наивно судите по себе (т.е. экстраполируете от своего поведения в подобной ситуации)?

Публицистические статьи Трахтмана лежат на его домашней странице, я просмотрел их пару дней назад.
(Ответить) (Parent) (Thread)
From: markvs
2010-09-15 12:18 pm
Спасибо, эти тексты я читал раньше. Я думал, что он что-то новое написал.

> Любопытно, вы понимаете, насколько оно оскорбительно,

Зря обиделись. Я ведь там специально даже :) добавил, чтобы не обижались.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2010-09-15 12:31 pm
У меня эта тема - пунктик. Давайте спишем на то, что из-за него отказывает чувство юмора. Извините :)
(Ответить) (Parent) (Thread)
From: ztarlitz
2010-09-15 10:45 pm
Мне уже интересно, что же это за человек такой? Странички его увы найти не смог, и текстов соответственно тоже.
(Ответить) (Parent) (Thread)
[User Picture]From: status_constr
2010-09-15 12:37 pm
там вроде как тексты не политические, а по еврейской истории, давней и не очень

написанные весьма достойно, и по содержанию, и по форме

прямые ссылки давать не очень хочется, все-таки автор поста совсем бе об этом писал, математика в данном случае гораздо интереснее

Вы попробуйте в окошке поиска набрать четыре слова - Авраам Трахтман еврейская история - вот так, без кавычек - и всё найдется, либо непосредственно, либо чьи-то заметки о нем, в которых уже ссылки

про его политические взгляды я тоже ничего "такого" знаю и не особо интересуюсь - и, по-моему, Вы зря наговариваете на автора данного поста, тем более в третьем лице, не знаю, как-то не очень ловко, по-моему, а может, и ничего

зато я знаю, что студенты его очень хвалят
(Ответить) (Parent) (Thread)
From: markvs
2010-09-15 03:03 pm
>зато я знаю, что студенты его очень хвалят

Это хорошо. Спасибо за информацию.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2010-09-15 06:44 am

Трахтман, публикации в Интернете

Перевод с древнеевропейского
"Заметки по еврейской истории", № 44 от 19 июля 2004 г.

Алкаш непробудный
"Лебедь", Альманах, № 567 от 15 июня 2008 г.

http://www.math.biu.ac.il/people/
trakhtman/stories

(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2010-09-14 10:17 pm
А почему все w(x) окажутся положительными?
(Ответить) (Thread)
[User Picture]From: avva
2010-09-14 10:48 pm
Я не знал ответа на этот вопрос (в статье это принимается за очевидно известное), но видимо - после некоторых поисков - это следствие теоремы Перрона-Фробениуса для случая неотрицательной матрицы. См.
http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Non-negative_matrices

Для того, чтобы эта теорема была применима к неотрицательной, но не строго положительной матрице, нужно, чтобы матрица была несводимой; статья в википедии дает четыре альтернативных определения этой несводимости, и четвертое как раз говорит, что соответствующий граф сильно связян, что дано в нашем случае.

Строго положительный собственный вектор будет существовать для самого большого по модулю собственного значения; то, что в данном случае это именно d графа, следует например из Collatz-Wielandt formula в этой же статье: нижняя и верхняя границы для собственного значения в этой формуле обе равны d для нашего графа, потому что в каждой строке матрицы ровно d единиц.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2010-09-15 01:39 pm
По модулю этого всё, кажется довольно понятно. Я немного тупил с тем, нужно ли рассматривать некоторые множества как мультимножества, но, вроде, разобрался.
(Ответить) (Parent) (Thread)
[User Picture]From: centralasian
2010-09-15 12:59 am
Наткнувшись на предположим на секунду, я выпал из зоны комфорта в зону когнитивнейшего из диссонансов: "Так, а зачем ему нужно вводить концепцию времени?"
(Ответить) (Thread)
[User Picture]From: status_constr
2010-09-15 12:46 pm
время - ключевой фактор при раскраске дорог

не приходилось видеть короткометражку Резо Габриадзе "Бабочка"? и другие короткометражки Габриадзе из этой серии?

там и раскраска дорог, и фактор времени в виде чудесной аллегории

гениальные фильмы

почти такие же гениальные, как то, что сделал А.Трахтман
(Ответить) (Parent) (Thread)
[User Picture]From: zoster_toster
2010-09-15 04:23 pm
"Отношение стабильности... сохраняется структурой графа: если p,q стабильные друзья, p соединено ребром с p', q с q', то p' и q' тоже стабильные друзья".
Наверное, нужно потребовать, чтобы рёбра pp' и qq' были одноцветными.
(Ответить) (Thread)
[User Picture]From: avva
2010-09-15 06:08 pm
Ага, правильная поправка, спасибо. Сейчас добавлю это.
(Ответить) (Parent) (Thread)