Моя дорога в школу раскраска. Раскраски правила дорожного движения. Скачать прямую дорогу для машинок

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

Раскраски Правила дорожного движения для детей.

Обучение ребенка правилам поведения на улице (дороги, тротуары, городской транспорт) нужно начинать в самом раннем возрасте, до того, как он научится ходить и бегать самостоятельно. И здесь очень важен пример родителей и остальных взрослых, с которыми ребенок находится на улице. Вы должны не только рассказывать и объяснять правила дорожного движения своему ребенку, но и сами строго их соблюдать. Представленные на этой странице раскраски Правила дорожного движения в первую очередь предназначены для дошкольников и помогут детям усвоить основные моменты поведения на дороге, а также вблизи нее.

1. Раскраска Светофор.

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

• Всегда начинайте движение только при горящем зеленом сигнале светофора.
• Никогда не переходите дорогу на сигналы, запрещающие движение – красный или желтый, даже если поблизости нет транспортных средств.
• Переходя на зеленый свет, дополнительно убедитесь в своей безопасности – посмотрите налево, затем направо.

2. Раскраска пешеходный переход.

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

• Пешеходный переход обозначен на поверхности дороги «зеброй».
• Перед переходом дороги внимательно осмотрите ее, убедитесь в отсутствии поблизости транспорта.
• Переходите дорогу, а не перебегайте.
• Не переходите улицу наискосок.
• Особое внимание уделяйте стоящему транспорту, который закрывает обзор.
• При перемещении по пешеходному переходу прекратите разговаривать по телефону.
• Если рядом находятся подземный или надземный переходы – обязательно воспользуйтесь ими, в таких местах движение особенно интенсивно.

3. Тротуары.

Тротуар предназначается для движения пешеходов. Приучайте детей к правильному поведению на тротуарах, особенно расположенных в местах с интенсивным потоком транспорта.

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

4. Раскраски с правилами поведения детей в городском общественном транспорте и на остановках.

Эти раскраски научат детей правилам безопасного пользования общественным транспортом.

• Остановка общественного транспорта – опасное место из-за возможного плохого обзора дороги и большого скопления людей, которые могут случайно столкнуть ребенка с тротуара на проезжую часть. Здесь нужно быть особенно внимательными.
• Подходите к дверям транспорта только после его полной остановки.
• Выйдя из транспорта, приступайте к переходу дороги только после его отъезда от остановки.

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

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

(эта запись может быть интересна читателям с познаниями в математике и сочувствующим)

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

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

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

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

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

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

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

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

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

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

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

Доказать, что периодичность эквивалентна условию "есть N>1, на которое делится длина любого цикла", тривиально в одну сторону и легко в другую. Если вы готовы принять это на веру, можете легко пропустить остаток этого абзаца, для всего остального доказательства это неважно. Если граф периодичен, т.е. можно разделить вершины на множества V 1 , V 2 , ... V n , так, что ребра идут между ними по циклу, то очевидно, что длина любого цикла должна делиться на n, т.е. новое условие выполняется. Это тривиальное направление, но для нашей замены нужно как раз второе направление. Предположим, что есть такое N>1, на которое делится длина любого цикла. Построим в нашем графе какое-нибудь направленное остовное дерево (spanning tree) с корнем в вершине r. К любой вершине x есть маршрут в этом дереве начиная от корня длиной l(x). Мы утверждаем теперь, что для любого ребра p-->q в графе выполняется, что l(q) = l(p) + 1 (mod N). Если это утверждение верно, то из него следует сразу, что мы можем разбить все вершины на множества V i согласно l(x) mod N, и граф будет периодичен. Почему же это утверждение верно? Если p-->q является частью остовного дерева, то это очевидно, потому что тогда просто l(q) = l(p) + 1. Если это не так, то запишем маршруты от корня r к вершинам p,q как R p и R q . Пусть также R r означает маршрут от q обратно в r в графе (граф связный, так что он существует). Тогда мы можем записать два цикла: R p p-->q R r , и R q R r . Согласно условию, длины этих циклов делятся на 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 стабильны в старой раскраске и остаются таковыми "всю дорогу", каждая промежуточная пара вершин p n , q n по дороге от p,q к общей вершине будет стабильной, т.е. лежать внутри одной вершины P n и получать поэтому одинаковую пермутацию π P n .

Новая окраска является синхронизирующей для 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.

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

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

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

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

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

Пусть имеются две клики 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 - тоже враги. Но у этого множества есть N max +1 элементов, а выше мы показали, что в любом множестве попарных врагов не может быть больше N max элементов. Это противоречие, и поэтому 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, а другие деревья не удлинились, и опять-таки мы получили, что надо.

Можно надолго занять мальчиков, если предложить им сыграть машинками в песочнице. Но что делать, если на улице холодно, ребенок скучает. В этом случае можно скачать и распечатать следующие шаблоны дорог для машинок. Забавы начнутся уже с вырезания всех колец, поворотов и прямых дорог. С этих шаблонов ребенок может построить дорогу любой формы, проследите лишь за тем, чтобы было распечатано должное количество нужных листов А4 формата.

Скачать прямую дорогу для машинок

Этих листов понадобится больше всех. На листе А4 формата мы разместили 3 дороги, которые необходимо распечатать и вырезать. Покажите ребенку как разрезать дорогу под прямым углом, чтобы сделать участок той продолжительностью, которая нужна ему.

Дорога для машинок: кольцо

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

Дорога для машинок: прямой поворот

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

Не крутой поворот дороги для машинок

Завернуть дорогу под любым радиусом поможет следующий шаблон А4 формата.

Обновление сайта
10.12.2006 15:46
Для любителей автомобилей и мультфильмов - раскраски из мультфильма Тачки .

Благодаря компании Disney и студии Pixar в июне 2006 года весь мир увидел мультик, в котором героями стали только машины.

Автомобили в мультфильме Cars ("Тачки") живут обычной жизнью – один держит магазин по продаже резины, другой – тюнинговое ателье, а некоторые просто живут в свое удовольствие, как, например, хиппи Филмор (Volkswagen T1) или его друг – ветеран Второй мировой Серж (Willys). Главный же герой картины МакКуин по прозвищу "Молния" мечтает лишь о гонках, победах и славе. Попав в Радиаторный округ на знаменитом американском шоссе 66, еще "зеленый" МакКуин тут же рассказывает всем, какой он быстрый и крутой. Впрочем, первый же старт в гонке NASCAR развеивает его иллюзии. Пережить проигрыш герою помогают друзья – старый эвакуатор Мейтер (GMC Pick-up), наставник Док Хадсон (Hudson Hornet) и маленький Луиджи (Fiat 600), мечтающий увидеть настоящую Ferrari.

Ну и куда же без романтической красотки Салли (Porsche с очаровательной татуировкой 911)! Во многом благодаря им МакКуин все же одержит победу в гонке, одолев главного соперника Чико (Plymouth Hemi Cuda). Сбудется и мечта Луиджи – однажды в его магазин для смены резины заедет "жеребец из Маранелло", которого озвучил, кстати, сам "Красный Барон" Михаэль Шумахер.

Примечательно, что и создатели картины, и те, кто ее озвучивал, – люди, причастные к автомобилям. Например, режиссер Джо Лассетер почти все детство провел на заводе Chevrolet, где его отец был одним из главных конструкторов. В качестве консультанта выступил ведущий дизайнер концерна Ford Джей Мэйс. В озвучивании героев, кроме уже упомянутого семикратного чемпиона мира "Формулы-1" Михаэля Шумахера, приняли участие звезды NASCAR Ричард Петти и Пол Ньюман, а также легендарный гонщик Майкл Андретти.

Шум машин использован только оригинальный – например, специально для гоночных эпизодов звук несколько недель записывали на американских овалах во время соревнований NASCAR. На создание картины, бюджет которой составил 70 млн. USD, ушло более двух лет. За это время было создано 43 тыс. различных набросков машин, а на каждый рисунок уходило более 17 часов. Всего в фильме 120 персонажей-автомобилей – от новых Porsche и Ferrari до антикварного Ford T.