Моят път до училище книжка за оцветяване. Страници за оцветяване на правилата за движение

Актуализация на сайта
10.12.2006 15:46
За феновете на колите и анимационните филми - страници за оцветяване от анимационния филм Коли.

Благодарение на Disney и Pixar, през юни 2006 г. целият свят видя анимационен филм, в който само колите станаха герои.

Автомобилите в анимационния филм Cars ("Cars") живеят обикновен живот - единият държи магазин за гума, другият тунинг ателие, а някои просто живеят за собственото си удоволствие, като хипито Fillmore (Volkswagen T1) или неговият приятел - ветеран от Втората световна война Серж (Уилис). Главният герой на картината Маккуин, по прякор "Светкавица", мечтае само за състезания, победи и слава. Веднъж в радиаторния квартал на известната американска магистрала 66, „зеленият“ Маккуин веднага казва на всички колко е бърз и готин. Първият старт в състезанието НАСКАР обаче разсейва илюзиите му. Приятелите помагат на героя да преживее загубата - старият теглещ камион Meiter (GMC Pick-up), наставникът Док Хъдсън (Hudson Hornet) и малкият Луиджи (Fiat 600), който мечтае да види истинско Ferrari.

Е, къде без романтичната красавица Сали (Порше с очарователна татуировка 911)! До голяма степен благодарение на тях, McQueen все пак ще спечели състезанието, побеждавайки основния съперник Chico (Plymouth Hemi Cuda). Мечтата на Луиджи също ще се сбъдне - един ден "жребец от Маранело" ще се обади в магазина му за смяна на гуми, който между другото беше изразен от самия "Червен барон" Михаел Шумахер.

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

Използван е само оригиналният автомобилен шум - например, специално за състезателни епизоди, звукът е записан в продължение на няколко седмици на американски овали по време на състезания на NASCAR. Създаването на картината отне повече от две години, чийто бюджет беше 70 милиона долара. През това време са създадени 43 хиляди различни скици на автомобили, като всяка рисунка отнема повече от 17 часа. Във филма има общо 120 автомобилни герои, от нови Porsche и Ferrari до антични Ford Ts.

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

Изтегляне на прав път за автомобили

Тези листове ще са необходими най-вече. На лист формат А4 поставихме 3 пътя, които трябва да бъдат отпечатани и изрязани. Покажете на детето си как да реже пътя под прав ъгъл, за да направи участъка с необходимата му дължина.

Път за автомобили: околовръстен

За да свържете пътищата, ще ви е необходим пръстен, чийто шаблон е представен по-горе, и започнете да изграждате своята инфраструктура от него.

Автомобилен път: Прав завой

Представените завои ще позволят на момчето да завие пътя на 90 градуса, в желаната от него посока.

Не е остър завой на пътя за автомобили

Следният шаблон A4 ще ви помогне да обърнете пътя под произволен радиус.

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

Познаването на правилата за движение на детето е едно от основните условия за неговата безопасност на улицата. Много пешеходци, включително възрастни, са доста несериозни по отношение на спазването на тези правила, което често става причина за пътнотранспортни произшествия с различна тежест. Децата трябва ясно да разберат, че като са на улицата в селото, те са пълноправни участници в пътя, така че спазването на правилата за движение е тяхна отговорност.

Страници за оцветяване Правила за движение по пътищата за деца.

Обучението на детето на правилата за поведение на улицата (пътища, тротоари, градски транспорт) трябва да започне от много ранна възраст, преди да се научи да ходи и да тича самостоятелно. И тук е много важен примерът на родителите и другите възрастни, с които детето е на улицата. Трябва не само да разказвате и обяснявате правилата за движение на детето си, но и сами да ги спазвате стриктно. Страниците за оцветяване на правилата за движение на тази страница са предназначени предимно за деца в предучилищна възраст и ще помогнат на децата да научат основите на поведение на пътя, както и близо до него.

1. Страница за оцветяване на светофар.

Най-доброто място за безопасно пресичане на пътя е на пешеходна пътека, оборудвана със светофар. Страниците за оцветяване на светофар съдържат и малки стихчета, за да помогнат на децата да запомнят по-лесно правилата за използването му.

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

2. Оцветяване на пешеходната пътека.

Научете детето си да пресича платното само на пешеходна пътека. Страниците за оцветяване на пешеходни пътеки ще научат децата да пресичат правилно пътя. Прелез, който не е оборудван със светофар, се нарича нерегулиран.

• Пешеходната пътека е обозначена на повърхността на пътя със зебра.
• Преди да пресечете пътя, внимателно го проверете, уверете се, че наблизо няма движение.
• Пресичайте пътя, не пресичайте.
• Не пресичайте улицата.
• Обърнете специално внимание на стоящите превозни средства, които блокират видимостта ви.
• Спрете да говорите по телефона, докато преминавате през пешеходна пътека.
• Ако наблизо има подземни или надземни проходи, не забравяйте да ги използвате, на такива места трафикът е особено интензивен.

3. Тротоари.

Тротоарът е предвиден за пешеходно движение. Насърчавайте децата да се държат правилно на тротоарите, особено на тези, разположени в зони с интензивен трафик.

• Когато шофирате по тротоара по пътя, не се приближавайте твърде много до него.
• Наблюдавайте внимателно евентуалното излизане на автомобили от дворове, алеи.
• Не играйте с топка на тротоара, не бягайте.

4. Страници за оцветяване с правилата за поведение на децата в градския градски транспорт и на автобусните спирки.

Тези страници за оцветяване ще научат децата на правилата за безопасно използване на обществения транспорт.

• Спирката на градския транспорт е опасно място поради възможната лоша видимост на пътя и големи тълпи от хора, които случайно могат да избутат дете от тротоара на платното. Тук трябва да сте особено внимателни.
• Приближавайте се до вратите на транспорта само след пълното му спиране.
• След като напуснете превозното средство, продължете да пресичате пътя само след като то е напуснало спирката.

В допълнение към тези основни правила на пътя, децата ще се интересуват от оцветяването на пътни знаци. Представените страници за оцветяване според правилата за движение са подходящи за малки деца, деца в предучилищна възраст и ученици в начална училищна възраст, както и за използване в детските градини и в часовете в началното училище. Всички картинки с правилата за движение по пътищата са напълно безплатни - те могат да бъдат изтеглени и отпечатани.

(този запис може да представлява интерес за читатели с познания по математика и симпатизанти)

Онзи ден прочетох за един интересен проблем от теорията на графите - предположението за оцветяване на пътя. Тази хипотеза съществува от 37 години, но преди три години беше доказана от израелския математик Абрахам Трахтман. Доказателството се оказа доста елементарно и с известни затруднения (защото мозъкът ми атрофира) успях да го прочета и разбера и дори ще се опитам да го обясня в този запис.

Проблемът може да се обясни с пример. Представете си карта на града, където на всяко кръстовище можете да отидете в една от четирите посоки - север, юг, изток и запад. Ако колата тръгне от някакво кръстовище и следва някакъв списък от посоки - "север, север, изток" и т.н. - тогава тя в крайна сметка ще стигне до друга пресечка. Възможно ли е да се намери такъв списък с упътвания, може би дълъг, който да доведе колата до едно и също място, независимо откъде е тръгнала? Ако картата изглежда като Манхатън - правилна решетка - тогава не, но може би в нея има много задънени улици и неочаквани завои?

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

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

В общия случай нека има насочен граф G - с "стрелкови" ръбове между върховете. Нека тази графика има еднаква изходяща степен d - това означава, че точно d ребра излизат от всеки връх. В същото време във всеки отделен връх може да влезе различен номер, не непременно d. Да предположим, че имаме набор от d букви от някаква азбука, която ще наречем "цветя". След това "оцветяването" на графиката се дава чрез присвояване на всеки връх на всички d букви за d от неговите изходящи ребра. Така че, ако се „намираме“ в някакъв връх и искаме да „отидем“ някъде според цвета α, тогава оцветяването винаги ще ни каже кой ръб до кой нов връх трябва да отидем. „Дума“ е всяка последователност от цветове на букви. След това, ако в графиката е дадено оцветяване и x е някакъв връх и w е някаква дума, тогава xw обозначава върха, до който ще стигнем, започвайки от x и след думата w.

Книжката за оцветяване се казва синхронизиране, ако има дума w, която води всеки връх x до един фиксиран връх x 0 . В този случай се извиква w дума за синхронизиране. Въпросът, зададен от проблема с оцветяването на пътя, е: винаги ли има синхронно оцветяване? Винаги ли е възможно да се оцветят ръбовете на графа по такъв начин, че всички върхове да могат да бъдат сведени до един?

Този проблем има приложения в няколко различни области, за които можете да прочетете например в Wikipedia. Например в компютърните науки, в теорията на автоматите. Граф с оцветяване може да се разглежда като детерминистичен краен автомат, в който върховете са състоянията, а ръбовете показват как да се навигира между тях. Да предположим, че управляваме този автомат от разстояние, изпращайки команди по някакъв информационен канал и поради някакви повреди този канал е бил замърсен, автоматът е получил някакви грешни инструкции и сега ние изобщо не знаем в какво състояние е. След това, ако има дума за синхронизиране, можем да я доведем до известно състояние, независимо къде се намира в момента.

И така, кога съществува синхронизираното оцветяване? Хипотезата за оцветяване на пътя налага още две ограничения върху графиката (освен факта, че всеки връх има точно 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 са врагове, т.е. никога не се събират, нека наречем А клика. Кликите съществуват, защото винаги можем да започнем с цяло число 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 и изберем само едно изходящо ребро от всеки връх. Такъв избор дефинира подграф, който наричаме обхващаща графика(обхватна графика). Може да има много различни обхващащи графики, но нека помислим малко за това как изглеждат. Нека има някакъв обхващащ граф R. Ако вземем произволен връх x в него и започнем да следваме ръбовете му, тогава всеки път ще имаме единствения избор, защото в R само едно ребро излиза от всеки връх и рано или късно ще затворен цикъл. Може би този цикъл няма да се затвори при x, а ще се затвори някъде "по-нататък" - например x-->y-->z-->s-->y. Тогава от x ще доведе "опашка" към този цикъл. Ако започнем от някой друг връх, също непременно ще стигнем до цикъл – този или някой друг. Оказва се, че всеки връх на R или лежи върху цикъл (от които може да има няколко), или е част от "опашката", която води до цикъла. Това означава, че R изглежда така: върху тях са построени определен брой цикли и определен брой "обърнати" дървета: всяко дърво не започва, а завършва в "корен", който лежи на един от циклите.

На всеки връх на графа можем да присвоим ниво, съответстващо на разстоянието му от цикъла в дадения обхващащ граф R. Върховете, които лежат на цикъла, имат ниво 0, а върховете, които лежат на дървото, прикрепено към цикъла, получават ниво, равно на разстоянието в тяхното дърво до "корена " лежи на цикъл. Някои върхове на нашия график имат максимално ниво L. Може би то обикновено е равно на 0 - т.е. няма дървета, само цикли. Може би е по-голямо от нула и върховете на това максимално ниво лежат на всякакви различни дървета, свързани с различни цикли или с един.

Искаме да изберем обхващаща графа R по такъв начин, че всички върхове на максимално ниво лежат на едно и също дърво. Интуитивно човек може да вярва, че това може да се направи, защото ако това не е така - например, те са разпръснати в различни дървета - тогава човек може да избере един от тези максимални върхове x и да увеличи нивото му, като прикрепи към R някакъв ръб до х. След това ще трябва да се изхвърли някой друг ръб и не е сигурно, че няма да нарани нещо друго... но това е технически проблем, повече за това по-късно. Просто се опитвам да кажа, че интуитивно не изглежда много сложно.

За момента да предположим, че можем да изберем 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; и само х най-накрая влезе в своя цикъл и се установи там някъде. Това означава, че пресечната точка на 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, който има максималния брой върхове на циклите. Т.е. има върхове, които не са в цикли, но освен това ограничение, броят на върховете в цикли е максимален. Този график има някои върхове с максимално ниво L и можем да приемем, че те са върху дървета, водещи до различни корени, в противен случай вече сме постигнали това, от което се нуждаем. Избираме един такъв връх x. Искаме да променим графиката, така че този връх да стане част от по-дълъг маршрут в дървото, по-дълъг от L, и останалите дървета да не се променят, и тогава максималното ниво ще бъде само в едно дърво, което е, което ние искам. Можете да промените графиката по три начина:

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

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

Актуализация, седмица по-късно:въпреки това реших да направя този запис напълно самодостатъчен и също така да преразкажа доказателството на лемата, на което се позовах в предишния параграф. Би било по-добре да направя това с диаграма, но не искам да го нарисувам или да го откъсна от статията, така че ще опитам с думи. И така, нека си представим, че имаме обхващащ граф R, който има нетривиални дървета и от всички такива графове в него максималният брой върхове се намира върху цикли. Ние се стремим да трансформираме R в обхващащ граф, в който всички върхове на максимално ниво лежат на едно и също дърво; веднага щом получим такава графа в процеса на опитване, веднага завършваме (и не ни интересува, че максималната графа по отношение на броя на върховете на циклите може да бъде загубена, тя не е важна за нас сама по себе си, ние го използваме само в процеса). Нека x е върхът на максималното ниво L, T дървото, на което лежи, r върхът на цикъла C, където T завършва, 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, тогава сега ще направим a) заедно с b) също a): тъй като знаем, че y-->z лежи на C, тогава тази операция ще прекъсне C, но не и новия цикъл, към който сега е свързано дърво Τ и това дърво вече ще има върхове на ниво, по-голямо от L, и ние сме готови отново.

Останалата опция е, когато b-->d също е свързано с цикъла C, на някое друго място освен r, или на същото място и след това d=r. След като заменихме b-->r с b-->d, получихме същата ситуация като първоначално - дърво T, възел x от ниво L и т.н. - само дървото вече е свързано с цикъла чрез върха d. Разглеждайки сега операция a), заключаваме (ако приемем, че не работи), че 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, а другите дървета не са се удължили и отново имаме това, от което се нуждаем.