Моя дорога до школи забарвлення. Розмальовки правила дорожнього руху

Оновлення сайту
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.

Можна надовго зайняти хлопчиків, якщо запропонувати їм зіграти машинками у пісочниці. Але що робити, якщо на вулиці холодно, дитина нудьгує. У цьому випадку можна завантажити та роздрукувати такі шаблони доріг для машинок. Забави розпочнуться вже з вирізування всіх кілець, поворотів та прямих доріг. З цих шаблонів дитина може побудувати дорогу будь-якої форми, простежте лише за тим, щоб було роздруковано належну кількість потрібних аркушів формату А4.

Завантажити пряму дорогу для машинок

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

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

Для з'єднання доріг вам знадобиться кільце, шаблон якого представлений вище, з нього і починайте будівництво вашої інфраструктури.

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

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

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

Загорнути дорогу під будь-яким радіусом допоможе наступний шаблон формату А4.

Ви знаходитесь в категорії забарвлення дороги. Розмальовка, яку ви розглядаєте описана нашими відвідувачами наступним чином "" Тут ви знайдете безліч розмальовок онлайн. Ви можете завантажити розмальовки дорога і так само роздрукувати їх безкоштовно. Як відомо, творчі заняття відіграють величезну роль у розвитку дитини. Вони активізують розумову діяльність, формують естетичний смак та прищеплюють любов до мистецтва. Процес розфарбовування картинок на тему дорога розвиває дрібну моторику, посидючість і акуратність, допомагає дізнатися більше про навколишній світ, знайомить з усією різноманітністю кольорів та відтінків. Ми щодня додаємо на наш сайт нові безкоштовні розмальовки для хлопчиків та дівчаток, які можна розфарбовувати онлайн або завантажити та роздрукувати. Зручний каталог, складений за категоріями, полегшить пошук потрібної картинки, а великий вибір розмальовок дозволить кожен день знаходити цікаву тему для розфарбовування.

Знання дитиною Правил дорожнього руху – одна з головних умов її безпеки на вулиці. Багато пішоходів, у тому числі й дорослих, досить легковажно ставляться до дотримання цих правил, що нерідко стає причиною різних за тяжкістю дорожньо-транспортних пригод. Діти мають чітко розуміти, що, перебуваючи на вулиці в населеному пункті, вони є повноправними учасниками дорожнього руху, тому дотримання правил дорожнього руху – їхній обов'язок.

Правила дорожнього руху для дітей.

Навчання дитини правилам поведінки на вулиці (дороги, тротуари, міський транспорт) потрібно починати в ранньому віці, до того, як вона навчиться ходити і бігати самостійно. І тут дуже важливим є приклад батьків та інших дорослих, з якими дитина знаходиться на вулиці. Ви повинні не тільки розповідати та пояснювати правила дорожнього руху своїй дитині, але й самі суворо їх дотримуватись. Представлені на цій сторінці забарвлення Правила дорожнього руху в першу чергу призначені для дошкільнят та допоможуть дітям засвоїти основні моменти поведінки на дорозі та поблизу неї.

1. Розмальовка світлофора.

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

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

2. Розмальовки пішохідного переходу.

Привчайте дитину перетинати проїжджу частину вулиці лише на пішохідному переході. Забарвлення пішохідних переходів навчать дітей правильно переходити дорогу. Перехід, не обладнаний світлофором, називається нерегульованим.

• Пішохідний перехід позначений на поверхні дороги "зеброю".
• Перед переходом дороги уважно огляньте її, переконайтеся у відсутності поблизу транспорту.
• Переходьте дорогу, а не перебігайте.
• Не переходьте вулицю навскіс.
• Особливу увагу приділяйте транспорту, що стоїть, який закриває огляд.
• При переміщенні пішохідним переходом припиніть розмовляти телефоном.
• Якщо поруч знаходяться підземний або надземний переходи – обов'язково скористайтеся ними, у таких місцях рух особливо інтенсивний.

3. Тротуари.

Тротуар призначається для руху пішоходів. Привчайте дітей до правильної поведінки на тротуарах, особливо в місцях з інтенсивним потоком транспорту.

• Під час руху тротуаром уздовж дороги, не підходьте до неї занадто близько.
• Уважно спостерігайте за можливим виїздом автомобілів із дворів, провулків.
• Не грайте на тротуарі у м'яч, не бігайте.

4. Розмальовки з правилами поведінки дітей у міському громадському транспорті та на зупинках.

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

• Зупинка громадського транспорту – небезпечне місце через можливий поганий огляд дороги та велике скупчення людей, які можуть випадково зіштовхнути дитину з тротуару на проїжджу частину. Тут треба бути особливо уважними.
• Підходьте до дверей транспорту лише після його повної зупинки.
• Виходячи з транспорту, приступайте до переходу дороги лише після від'їзду від зупинки.

Крім цих основних правил дорожнього руху, дітям будуть цікаві розмальовки дорожніх знаків. Представлені розмальовки з ПДР підійдуть для малюків, дошкільнят та учнів молодшого шкільного віку, а також для використання у дитячих садках та на уроках у початкових класах школи. Всі картинки з Правилами дорожнього руху абсолютно безкоштовні - їх можна завантажити та роздрукувати.

(Цей запис може бути цікавим читачам з пізнаннями в математиці та співчуваючих)

Днями я прочитав про цікаве завдання з теорії графів-гіпотеза про забарвлення дороги. Ця гіпотеза була відкрита протягом 37 років, але три роки тому її довів ізраїльський математик Авраам Трахтман. Доказ виявився досить елементарним, і з деякими складнощами (оскільки мізки атрофувалися) я зміг його прочитати і зрозуміти, і навіть спробую в цьому записі пояснити.

Завдання можна пояснити на такому прикладі. Уявіть карту міста, на якій на кожному перехресті можна поїхати в одну з чотирьох сторін - на північ, південь, схід і захід. Якщо машина починає з якогось перехрестя і слідує за якимось списком вказівок - "північ, північ, схід" тощо. - то вона приїде в результаті на якесь інше перехрестя. Чи можна знайти такий список вказівок, можливо, довгий, який приведе машину в те саме місце, незалежно від того, де вона почала? Якщо карта виглядає як Манхеттен - регулярні ґрати - то ні, але може, в ній є багато глухих кутів і несподіваних поворотів?

Або інший приклад. Ваш друг застряг у лабіринті, в якому потрібно знайти центр, і зателефонував вам із проханням допомогти. Ви знаєте, як влаштований лабіринт, але не знаєте, де ваш друг. Чи може бути така послідовність команд, яка точно приведе вашого друга до центру, де б він не був?

У цих двох прикладах "напрями" у кожній точці фіксовані, і рішення або існує, або ні. Але в більш загальному випадку це завдання запитує: якщо ми можемо вибрати, куди показує наприклад "захід, північ, схід, південь", на кожному перехресті по-своєму, чи зможемо тоді забезпечити існування "синхронізуючого слова" - послідовності команд, яка з будь-якого місця приведе до одного фіксованого?

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

Забарвлення називається синхронізуючоюякщо існує таке слово w, яке будь-яку вершину x призводить до однієї фіксованої вершини x 0 . У цьому випадку w називається синхронізуючим словом. Питання, яке ставить проблема розмальовки дороги: чи завжди існує розфарбування, що синхронізує? Чи завжди можна розфарбувати ребра графа, щоб можна було звести всі вершини до однієї?

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

Отже, коли існує розфарбування, що синхронізує? Гіпотеза розмальовки дороги накладає на граф ще два обмеження (крім того, що з кожної вершини виходить рівно ребер). По-перше, граф має бути дуже зв'язковим - це означає, що з будь-якої вершини до будь-якої іншої існує маршрут. По-друге, граф не повинен бути періодичним. Уявімо, що всі вершини графа можна розбити на множини V 1 , V 2 , ... V n , так що будь-яке ребро графа з'єднує вершини з якихось Vi i Vi +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, і т.д. --α--> 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. У такій нотації синхронізуюче забарвлення означає, що є таке, що 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. Де може лежати вершина? Не дереві T, оскільки це " розширило " цикл C, суперечачи максимальності R. Значить, e лежить іншому дереві чи іншому циклі, і навіть у тому циклі C, але з вершині r. Тоді дерево T, до того як воно підключається до циклу, подовжується тепер як мінімум на одне ребро, що виходить з r, а може і на більше (тільки на одне, якщо e лежить відразу після r, і c-> e замикає цикл Зново, виводячи з нього тільки r). Значить, у вершини x та інших максимальних вершин T рівень тепер не менший за L+1, а інші дерева не подовжилися, і знову-таки ми отримали, що треба.