Omaľovánka cesta. Omaľovánky na cesty (matematické) Omaľovánky s pravidlami správania sa detí v mestskej hromadnej doprave a na autobusových zastávkach

Aktualizácia stránky
10.12.2006 15:46
Pre fanúšikov áut a karikatúr - maľovanky z karikatúry Cars.

Vďaka Disney a Pixar videl celý svet v júni 2006 karikatúru, v ktorej sa hrdinami stali iba autá.

Autá v rozprávke Autá ("Autá") žijú obyčajným životom - jeden má gumáreň, druhý tuningové štúdio a niektorí si žijú len pre svoje potešenie, ako napríklad hipisák Fillmore (Volkswagen T1) alebo jeho kamarát - a. veterán druhej svetovej vojny Serge (Willys). Hlavná postava obrazu McQueen, prezývaný „Blesk“, sníva len o pretekoch, víťazstvách a sláve. Keď sa „zelený“ McQueen ocitne v Radiator District na známej americkej diaľnici 66, okamžite každému povie, aký je rýchly a cool. Prvý štart na pretekoch NASCAR však rozptýli jeho ilúzie. Priatelia pomáhajú hrdinovi prežiť stratu - stará odťahovka Meiter (GMC Pick-up), mentor Doc Hudson (Hudson Hornet) a malý Luigi (Fiat 600), ktorý sníva o tom, že uvidí skutočné Ferrari.

No kdeže bez romantickej krásky Sally (Porsche s očarujúcim tetovaním 911)! Z veľkej časti vďaka nim McQueen stále vyhrá preteky a porazí hlavného rivala Chica (Plymouth Hemi Cuda). Splní sa aj Luigiho sen – jedného dňa zavolá do jeho obchodu „žrebec z Maranella“ na výmenu pneumatík, čo mimochodom nahovoril sám „Červený barón“ Michael Schumacher.

Je pozoruhodné, že tvorcovia obrazu aj tí, ktorí ho vyjadrili, sú ľudia zaoberajúci sa automobilmi. Napríklad režisér Joe Lasseter strávil väčšinu svojho detstva v továrni Chevrolet, kde bol jeho otec jedným z hlavných konštruktérov. Ako konzultant pôsobil Jay Mays, popredný dizajnér koncernu Ford. Okrem už spomenutého sedemnásobného majstra sveta Formuly 1 Michaela Schumachera nahovorili hrdinov hviezdy NASCAR Richard Petty a Paul Newman, ale aj legendárny pretekár Michael Andretti.

Použil sa len pôvodný hluk auta – napríklad špeciálne pre pretekárske epizódy sa zvuk nahrával niekoľko týždňov na amerických ováloch počas súťaží NASCAR. Vytvorenie obrazu, ktorého rozpočet bol 70 miliónov USD, trvalo viac ako dva roky. Za tento čas vzniklo 43 tisíc rôznych náčrtov áut a každá kresba trvala viac ako 17 hodín. Vo filme je celkovo 120 automobilových postáv, od nových Porsche a Ferrari až po starožitné Fordy T.

Znalosť pravidiel cestnej premávky dieťaťa je jednou z hlavných podmienok jeho bezpečnosti na ulici. Mnohí chodci, vrátane dospelých, sú pri dodržiavaní týchto pravidiel dosť ľahkomyseľní, čo sa často stáva príčinou dopravných nehôd rôznej závažnosti. Deti musia jasne pochopiť, že keď sú na ulici v obci, sú plnohodnotnými účastníkmi cesty, takže dodržiavanie pravidiel cestnej premávky je ich zodpovednosťou.

Omaľovánky Pravidlá cestnej premávky pre deti.

Učiť dieťa pravidlám správania sa na ulici (cesty, chodníky, mestská doprava) treba začať už vo veľmi ranom veku, ešte predtým, ako sa naučí samo chodiť a behať. A tu je veľmi dôležitý príklad rodičov a iných dospelých, s ktorými je dieťa na ulici. Pravidlá cestnej premávky musíte svojmu dieťaťu nielen povedať a vysvetliť, ale aj sami ich prísne dodržiavať. Omaľovánky pravidiel cestnej premávky na tejto stránke sú primárne určené pre predškolákov a pomôžu deťom osvojiť si základy správania sa na ceste, ale aj v jej blízkosti.

1. Omaľovánka so semaforom.

Najlepším miestom na bezpečný prechod cez cestu je priechod pre chodcov vybavený semaformi. Omaľovánky so semaforom obsahujú aj malé riekanky, ktoré deťom pomôžu ľahšie si zapamätať pravidlá používania.

• Jazdu začnite vždy, až keď na semafore svieti zelená.
• Nikdy neprechádzajte cez cestu na červené alebo žlté semafory, aj keď v blízkosti nie sú žiadne vozidlá.
• Keď rozsvietite zelené svetlo, navyše sa uistite, že ste v bezpečí - pozrite sa doľava a potom doprava.

2. Farbenie priechodu pre chodcov.

Naučte svoje dieťa prechádzať cez vozovku len na priechode pre chodcov. Omaľovánky prechodov pre chodcov naučia deti správne prechádzať cez cestu. Priecestie, ktoré nie je vybavené svetelnou signalizáciou, sa nazýva neregulované.

• Priechod pre chodcov je na povrchu vozovky označený zebrou.
• Pred prechodom cez cestu ju dôkladne skontrolujte, uistite sa, že v blízkosti nie je žiadna premávka.
• Prejdite cez cestu, neprebiehajte.
• Neprechádzajte cez ulicu.
• Venujte zvláštnu pozornosť stojacim vozidlám, ktoré vám bránia vo výhľade.
• Prestaňte telefonovať pri prechádzaní cez priechod pre chodcov.
• Ak sú v blízkosti podzemné alebo vyvýšené chodby, určite ich použite, na takýchto miestach je premávka obzvlášť intenzívna.

3. Chodníky.

Chodník je určený pre pešiu dopravu. Povzbudzujte deti, aby sa správne správali na chodníkoch, najmä na tých, ktoré sa nachádzajú v oblastiach so silnou premávkou.

• Pri jazde po chodníku popri ceste sa k nemu príliš nepribližujte.
• Pozorne sledujte možný výjazd áut z dvorov, uličiek.
• Nehrajte loptu na chodníku, neutekajte.

4. Omaľovánky s pravidlami správania sa k deťom v mestskej hromadnej doprave a na autobusových zastávkach.

Tieto omaľovánky naučia deti pravidlám bezpečného používania verejnej dopravy.

• Zastávka MHD je nebezpečným miestom pre možnú zlú viditeľnosť cesty a veľké davy ľudí, ktorí môžu omylom vytlačiť dieťa z chodníka na vozovku. Tu si treba dávať obzvlášť pozor.
• K dverám prepravy sa priblížte až po jej úplnom zastavení.
• Po opustení vozidla prejdite cez cestu až po opustení zastávky.

Okrem týchto základných pravidiel cestnej premávky deti zaujme vyfarbovanie dopravných značiek. Prezentované omaľovánky podľa pravidiel cestnej premávky sú vhodné pre batoľatá, predškolákov a žiakov základných škôl, ako aj na použitie v materských školách a na vyučovaní na základnej škole. Všetky obrázky s Pravidlami cestnej premávky sú úplne zadarmo - dajú sa stiahnuť a vytlačiť.

Chlapcov môžete zamestnať na dlhší čas, ak ich pozvete hrať sa s autami na pieskovisku. Ale čo keď je vonku zima, dieťa sa nudí. V tomto prípade si môžete stiahnuť a vytlačiť nasledujúce šablóny ciest pre autá. Zábava sa začne vystrihnutím všetkých kruhov, zákrut a rovných ciest. Z týchto šablón môže dieťa postaviť cestu akéhokoľvek tvaru, len sa uistite, že je vytlačený správny počet požadovaných listov A4.

Stiahnite si rovná cesta pre autá

Tieto listy budú potrebné predovšetkým. Na list formátu A4 sme umiestnili 3 cesty, ktoré je potrebné vytlačiť a vystrihnúť. Ukážte svojmu dieťaťu, ako rezať cestu v pravom uhle, aby bola časť taká dlhá, akú potrebuje.

Cesta pre autá: okruh

Na prepojenie ciest budete potrebovať prstenec, ktorého šablóna je uvedená vyššie, a začnite z neho budovať infraštruktúru.

Cesta autom: Rovná zákruta

Prezentované zákruty umožnia chlapcovi otočiť cestu o 90 stupňov v smere, ktorý potrebuje.

Nie prudká zákruta cesty pre autá

Nasledujúca šablóna A4 vám pomôže otočiť cestu pod akýmkoľvek polomerom.

(tento príspevok môže byť zaujímavý pre čitateľov so znalosťami matematiky a sympatizantov)

Minule som čítal o zaujímavom probléme z teórie grafov – o dohadoch o farbení ciest. Tento dohad je otvorený už 37 rokov, no pred tromi rokmi ho dokázal izraelský matematik Abraham Trachtman. Dôkaz sa ukázal byť celkom elementárny a s určitými ťažkosťami (keďže môj mozog atrofoval) som ho dokázal prečítať a pochopiť, a dokonca som sa ho pokúsil vysvetliť v tomto príspevku.

Problém možno vysvetliť na príklade. Predstavte si mapu mesta, kde na každej križovatke môžete ísť jedným zo štyroch smerov – sever, juh, východ a západ. Ak auto začína na nejakej križovatke a ide podľa nejakého zoznamu smerov - "sever, sever, východ" atď. - potom nakoniec dorazí na inú križovatku. Dá sa nájsť taký zoznam smerov, možno dlhý, ktorý dovedie auto na to isté miesto, bez ohľadu na to, kde začalo? Ak mapa vyzerá ako Manhattan – bežná sieť – tak nie, ale možno je na nej veľa slepých uličiek a nečakaných odbočiek?

Alebo iný príklad. Váš priateľ uviazol v bludisku, v ktorom musíte nájsť centrum a zavolal vám o pomoc. Viete, ako funguje bludisko, ale neviete, kde je váš priateľ. Môže existovať postupnosť príkazov, ktoré určite dovedú vášho priateľa do stredu, nech je kdekoľvek?

V týchto dvoch príkladoch sú „smery“ v každom bode pevné a riešenie buď existuje, alebo neexistuje. Ale vo všeobecnejšom prípade sa tento problém pýta: ak si môžeme vybrať, kde napríklad ukazuje „západ, sever, východ, juh“ na každej križovatke svojím vlastným spôsobom, môžeme potom zabezpečiť existenciu „synchronizačného slova “ - postupnosť príkazov, ktorá z akéhokoľvek miesta povedie k jednému pevnému?

Vo všeobecnom prípade nech existuje orientovaný graf G - s hranami "šípky" medzi vrcholmi. Nech má tento graf jednotný výstupný stupeň d - to znamená, že z každého vrcholu vychádza presne d hrán. Zároveň môže do každého jednotlivého vrcholu vstúpiť iné číslo, nie nevyhnutne d. Predpokladajme, že máme množinu d písmen nejakej abecedy, ktorú budeme nazývať „kvety“. Potom je „zafarbenie“ grafu dané priradením ku každému vrcholu všetkých d písmen pre d jeho odchádzajúcich hrán. Ak sa teda „nachádzame“ na nejakom vrchole, a chceme niekam „ísť“ podľa farby α, tak nám farbenie vždy povie, na ktorú hranu máme ísť do ktorého nového vrcholu. "Slovo" je akákoľvek sekvencia farieb písmen. Potom, ak je v grafe dané zafarbenie a x je nejaký vrchol a w je nejaké slovo, potom xw označuje vrchol, ku ktorému dospejeme, začínajúc od x a po slove w.

Omaľovánka je tzv synchronizácia, ak existuje slovo w, ktoré vedie ľubovoľný vrchol x k jednému pevnému vrcholu x 0 . V tomto prípade sa volá w synchronizovať slovo. Otázka, ktorú si kladie problém sfarbenia ciest, znie: existuje vždy synchrónne sfarbenie? Je vždy možné zafarbiť okraje grafu tak, aby sa všetky vrcholy dali zmenšiť na jeden?

Tento problém má uplatnenie vo viacerých rôznych oblastiach, o ktorých sa možno dočítať napríklad na Wikipédii. Napríklad v informatike, v teórii automatov. Graf so sfarbením si možno predstaviť ako deterministický konečný stavový stroj, v ktorom sú vrcholy stavmi a hrany naznačujú, ako sa medzi nimi pohybovať. Predpokladajme, že ovládame tento automat na diaľku, posielame príkazy cez nejaký informačný kanál a v dôsledku nejakého zlyhania bol tento kanál znečistený, automat dostal nejaké chybné inštrukcie a teraz vôbec nevieme, v akom stave je. Potom, ak existuje synchronizačné slovo, môžeme ho uviesť do známeho stavu bez ohľadu na to, kde sa teraz nachádza.

Kedy teda existuje synchronizované sfarbenie? Dohad o farbení cesty ukladá grafu ďalšie dve obmedzenia (okrem skutočnosti, že každý vrchol má presne d hrán). Po prvé, graf musí byť silne prepojený, čo znamená, že existuje trasa z akéhokoľvek vrcholu do akéhokoľvek iného. Po druhé, graf nesmie byť periodický. Predstavte si, že všetky vrcholy grafu možno rozdeliť do množín V 1, V 2, ... V n tak, že ľubovoľná hrana grafu spája vrcholy z nejakého V i a V i+1 alebo V n a V 0 . Medzi vrcholmi v každom V nie sú žiadne hrany a ani nemôžu "skákať" medzi žiadnym V, iba v poradí. Takýto graf sa nazýva periodický. Je jasné, že takýto graf nemôže mať synchronizačné zafarbenie, pretože bez ohľadu na to, ako ho vyfarbíte a akými slovami idete, dva vrcholy v rôznych V i sa nikdy nestretnú - budú obchádzať cyklus.

Veta o farbení ciest hovorí, že tieto podmienky sú dostatočné: každý neperiodický silne spojený orientovaný graf s d hranami z každého vrcholu má synchronizačné zafarbenie. Prvýkrát bol formulovaný ako domnienka v roku 1970 a odvtedy sa objavilo množstvo čiastkových výsledkov dokazujúcich konkrétne prípady, no úplný dôkaz sa objavil až v roku 2007. Nasleduje moje prerozprávanie takmer celého dôkazu (okrem jednej technickej lemy).

Periodicita

V prvom rade nahraďme podmienku neperiodicity inou, ktorá je jej ekvivalentná. Graf je periodický vtedy a len vtedy, ak existuje číslo N>1, ktoré delí dĺžku ľubovoľného cyklu v grafe. Tie. naša požiadavka na neperiodicitu je ekvivalentná s tvrdením, že také N neexistuje, alebo inými slovami, najväčší spoločný deliteľ dĺžok všetkých cyklov v grafe je 1. Dokážeme, že každý graf, ktorý spĺňa túto podmienku, má synchronizačné sfarbenie.

Dokázať, že periodicita je ekvivalentná podmienke „existuje N>1, ktorou je deliteľná dĺžka akéhokoľvek cyklu“, je triviálne v jednom smere a jednoduché v druhom. Ak ste ochotní to vziať s dôverou, môžete zvyšok tohto odseku ľahko preskočiť; na zvyšku dôkazu nezáleží. Ak je graf periodický, t.j. Keďže je možné rozdeliť vrcholy na množiny V 1, V 2, ... V n tak, že hrany idú medzi nimi v cykle, potom je zrejmé, že dĺžka akéhokoľvek cyklu musí byť deliteľná číslom n, t.j. nová podmienka je splnená. Toto je triviálny smer, ale na našu výmenu potrebujeme práve druhý smer. Predpokladajme, že existuje také N>1, ktoré delí dĺžku ľubovoľného cyklu. Postavme do nášho grafu nejaký smerovaný kostra (spanning tree) s koreňom vo vrchole r. Existuje cesta k akémukoľvek vrcholu x v tomto strome začínajúca od koreňa dĺžky l(x). Teraz tvrdíme, že pre akúkoľvek hranu p-->q v grafe platí l(q) = l(p) + 1 (mod N). Ak je toto tvrdenie pravdivé, tak z neho hneď vyplýva, že všetky vrcholy môžeme rozdeliť na množiny V i podľa l(x) mod N a graf bude periodický. Prečo je toto tvrdenie pravdivé? Ak je p-->q súčasťou kostry, potom je to zrejmé, pretože potom stačí l(q) = l(p) + 1. Ak to tak nie je, zapíšeme cesty od koreňa r do vrcholy p,q ako Rp a Rq. Nech aj R r znamená cestu z q späť do r v grafe (graf je spojený, takže existuje). Potom môžeme napísať dva cykly: R p p --> q R r a R q R r . Podľa podmienky sú dĺžky týchto cyklov deliteľné N, odčítaním a zrušením celkových hodnôt dostaneme, že l(p)+1 = l(q) mod N, čo sa malo dokázať.

Stabilné priateľstvo a indukcia

Nech je dané nejaké zafarbenie grafu G. Dva vrcholy nazývame p,q priateľmi, ak ich nejaké slovo w privedie do toho istého vrcholu: pw = qw. Nazvime p,q nepriateľmi, ak sa „nikdy nestretnú“. Nazvime p,q stabilnými priateľmi, ak po vykonaní akéhokoľvek slova w zostanú priateľmi: pw sa nemusí dostať do rovnakého vrcholu ako qw, ale po nejakom ďalšom w" už môže. Stabilní priatelia sa nikdy nestanú nepriateľmi.

Vzťah stability medzi vrcholmi je po prvé ekvivalenciou (je reflexívny, symetrický a tranzitívny) a po druhé je zachovaný štruktúrou grafu: ak p,q sú stabilní priatelia, p je spojené hranou s p" , q s q", a tieto okraje rovnakej farby, potom p" a q" sú tiež stabilnými priateľmi. To znamená, že stabilné priateľstvo je kongruencia a možno naň rozdeliť: vytvorte nový graf G", ktorého vrcholy budú stabilné triedy ekvivalencie priateľstva v G. Ak je v G aspoň jeden stabilný pár, potom G" bude mať veľkosť menšiu ako G. Navyše, ak v pôvodnom grafe má G z každého vrcholu d hrán, tak v G" to bude rovnaké. Napríklad ak P je vrchol nového grafu, čo je trieda ekvivalencie pôvodných vrcholov p1, p2... , a α je ľubovoľná farba, potom hrany p1--α--> q1, p2---α-->q2 atď. vedú k vrcholom q1, q2..., ktoré sú v stabilnom priateľstve s každým iné, a preto ležia v jednom novom vrchole Q, takže všetky tieto hrany sa stanú novou hranou P --α-->Q A tak ďalej pre každú z d farieb.

Navyše, ak G bolo neperiodické, potom G" je. Pretože – pri použití našej alternatívnej definície periodicity – každý cyklus v G sa zmení na cyklus v G", takže ak sú všetky dĺžky cyklu v G" deliteľné n > 1, potom to isté platí pre všetky cykly v G. Takže periodicita G“ znamená periodicitu G.

Predpokladajme, že v G" sa nám podarilo nájsť synchronizačné zafarbenie. Teraz ho možno použiť v G namiesto sfarbenia, s ktorým sme začali: akákoľvek hrana p-->q dostane novú farbu podľa novej farby hrany P-->Q. Trochu presnejšie by sme to mali povedať takto: v každom vrchole P grafu G" je nové zafarbenie dané nejakou permutáciou všetkých farieb π P: hrana, ktorá bola natretá farbou α, dostane novú farbu farba π P (α). Potom v pôvodnom grafe G pri každom vrchole p z triedy stability P aplikujeme rovnakú permutáciu π P na prefarbenie jeho hrán. Nové sfarbenie grafu G vo všeobecnosti definuje niektoré nové pojmy „priateľstvo“, „nepriateľstvo“ a „stabilita“, ktoré nie sú totožné s pôvodnými. Ale napriek tomu, ak dva vrcholy p, q boli stabilnými priateľmi v starom sfarbení - patrili do rovnakej triedy P - potom zostanú stabilnými priateľmi v novom. Je to preto, že každá postupnosť w, ktorá prináša p,q do jedného vrcholu, môže byť "prenesená" zo starého zafarbenia do nového alebo naopak pomocou permutácie π P v každom vrchole p pozdĺž cesty. Keďže p,q sú stabilné v starom zafarbení a zostávajú tak „celé cesty“, každý medziľahlý pár vrcholov p n , q n na ceste z p,q k spoločnému vrcholu bude stabilný, t.j. ležia vo vnútri toho istého vrcholu P n a preto dostávajú rovnakú permutáciu π P n .

Nové zafarbenie sa synchronizuje pre G", t.j. nejaká sekvencia w privedie všetky vrcholy do jedného vrcholu P. Ak teraz aplikujeme w na nové zafarbenie v G, potom sa všetky vrcholy zbiehajú niekde „vo vnútri P“. Ako je uvedené vyššie, všetky vrcholy v rámci triedy P zostávajú stabilné v novom sfarbení, čo znamená, že teraz môžeme pokračovať w, znova a znova spájať zostávajúce dvojice vrcholov, ktoré sú stále oddelené, až kým sa všetko nezblíži do jedného vrcholu G. Nové zafarbenie je teda synchronizácia pre G.

Z toho všetkého vyplýva, že na dokázanie vety stačí dokázať, že v každom grafe, ktorý spĺňa podmienky, existuje sfarbenie, v ktorom je pár stabilných priateľov . Pretože potom sa dá prejsť z grafu G do grafu G" menšieho a ten tiež spĺňa všetky podmienky. Pomocou induktívneho argumentu môžeme predpokladať, že pre grafy menšej veľkosti je problém už vyriešený a potom synchronizácia sfarbenie pre G" bude tiež synchronizované pre G .

Kliky a maximálne zostavy

Pre akúkoľvek podmnožinu A vrcholov grafu a slovo w, Aw označuje množinu vrcholov, ku ktorým dospejeme, začínajúc od všetkých vrcholov A a po slove w. Ak vychádzame zo všetkých vrcholov grafu vo všeobecnosti, potom to označíme Gw. V tomto zápise synchronizačné sfarbenie znamená, že existuje w také, že Gw je množina jedného prvku.

Ak má vrcholová množina A tvar Gw pre nejaké w a navyše akékoľvek dva vrcholy v A sú nepriateľmi, t.j. nikdy nekonvergovať, volajme A klika. Kliky existujú, pretože vždy môžeme začať s celým číslom G, vziať pár priateľov vrcholov, prejsť cez w, ktoré ich spája, a znížiť počet vrcholov o jeden; takto pokračujte, kým nezostanú len nepriatelia alebo zostane len jeden vrchol - aj v tomto prípade klika, jednoducho triviálna.

Ak A je klika, potom pre každé slovo w je aj Aw klika; to je jasné, pretože nepriatelia zostávajú nepriateľmi. Ak x je ľubovoľný vrchol grafu, potom existuje klika obsahujúca x. Vyplýva to z toho, že existuje nejaká klika A (pozri predchádzajúci odsek); ak je v ňom p vrchol, potom existuje slovo w vedúce z p do x, pretože spojený graf; potom Aw je klika vrátane x.

Kliknutia nám pomôžu dokázať, že existuje sfarbenie so stabilnými priateľmi - podľa predchádzajúcej časti to stačí na preukázanie vety. V tejto časti dokážeme, že ak existujú dve kliky A a B, takže všetky vrcholy v nich sú spoločné, okrem jedného v A a jedného v B, potom sú tieto dva vrcholy stabilnými priateľmi. Problém sa teda redukuje na nájdenie sfarbenia, ktoré obsahuje takéto kliky A a B.

Aby ste lepšie pochopili, ako kliky fungujú, je užitočné priradiť váhy vrcholom v grafe. Ukážme, že máme spôsob, ako priradiť kladnú váhu w(x) každému vrcholu x, takže ak pre akýkoľvek vrchol x spočítajte váhy všetkých vrcholov, ktoré majú hrany v x, potom dostaneme d*w(x), kde d je počet hrán z každého vrcholu. Vyplýva to z lineárnej algebry a ak neviete, čo je to vlastná hodnota, preskočte zvyšok tohto odseku a vezmite existenciu takéhoto w(x) na vieru. Ak M je matica grafu G (bunka (i,j) je 1, ak existuje hrana i-->j, a 0, ak taká hrana neexistuje), potom w(x), ako som ich opísal, sú prvky vlastného vektora vľavo táto matica pre vlastnú hodnotu d. Vieme, že takýto vektor existuje, pretože d je vlastná hodnota: má triviálny vlastný vektor napravo(1,1,....1) - to hneď vyplýva z toho, že z každého vrcholu vychádza práve d hrán.

Ak je A ľubovoľná množina vrcholov, potom w(A) označuje súčet váh všetkých vrcholov v A; a w(G) je súčet váh všetkých vrcholov v grafe. Okrem toho, ak s je akékoľvek slovo, potom nech As -1 označuje množinu vrcholov, ku ktorým prichádzate z A, ak idete "v opačnom smere" pozdĺž s, pričom v každom kroku nahradíte každý vrchol týmito vrcholmi (ak existujú). ktoré k tomu idú v príslušnej farbe.

Uvažujme teraz všetky množiny vrcholov, ktoré sa dajú spojiť do jedného bodu, t.j. A také, že pre niektoré w obsahuje Aw iba jeden vrchol. Tie množiny A, ktoré spomedzi všetkých majú maximálnu váhu w(A), sa nazývajú maximálne množiny. Ak je vyfarbenie synchronizované, potom je celý graf G maximálnou množinou (unikátny), ale inak tomu tak nie je.

Ak je A ľubovoľná množina vrcholov, potom súčet všetkých w(Aα -1), kde α prechádza všetkými d farbami, sa rovná d*w(A) – toto je len zovšeobecnenie hlavnej vlastnosti váhy z jednej vrchol do množiny vrcholov A. Ak je navyše A maximálna množina, potom každé z w(Aα -1) nemôže byť väčšie ako w(A), pretože aj tieto množiny sa redukujú na jeden vrchol. A keďže súčet d týchto váh sa rovná d*w(A), ukáže sa, že každá z nich sa rovná w(A) a všetky tieto množiny sú tiež maximálne. Z toho okamžite vyplýva, že ak je A maximálne, potom aj Aw -1 je maximálne pre každé slovo w.

Maximálne množiny sú užitočné, pretože ich nesúvislé inštancie môžu pokryť celý graf. Poďme to dokázať.

Majme množinu maximálnych množín A 1 ...A n, ktoré sa nepretínajú v pároch a sú redukované na jednotlivé vrcholy a 1 ...a n tým istým slovom w (v počiatočnom prípade bude n=1 a iba jedna sada, takže je ľahké začať). Je jasné, že všetky a 1 ...a n sa od seba líšia, pretože inak by bolo možné ešte viac rozšíriť maximálnu množinu na úkor prvkov inej s rovnakým konečným vrcholom. Predpokladajme, že všetky A i spolu ešte nevyčerpali všetky vrcholy G a nech x je vrchol mimo všetkých A i . Keďže graf je prepojený, existuje určitá cesta h od a 1 po x. Potom n maximálnych množín A i h -1 w -1 prechádza slovom whw do konečných vrcholov a 1 ...a n , a maximálna množina A 1 ide do nejakého vrcholu Awhw = (Aw)hw = (a 1 h)w = xw. Tento vrchol xw musí byť tiež odlišný od všetkých a 1 ...a n , pretože inak by sa maximálna množina A i mohla doplniť prvkom x. A keďže všetky tieto množiny n + 1 - všetky A i h -1 w -1 plus A 1 - idú pozdĺž whw do rôznych vrcholov, všetky sú párovo disjunktné. V tejto expanzii budeme pokračovať, kým nebudú žiadne vrcholy mimo množiny.

Takže môžeme pokryť celý graf G disjunktnými maximálnymi množinami. Keďže sú maximálne, všetky majú rovnaký súčet w max , a preto ich počet v pokrytí je N max = w(G)/w max .

Teraz zvážte akúkoľvek množinu A pozostávajúcu z párových nepriateľov. Príkladom takejto množiny je napríklad klika (a má tiež tvar Gw). Vo vnútri maximálnej množiny nemôže byť dvojica nepriateľov, pretože by sa potom nemohla zblížiť. Preto v pokrytí N max maximálnych množín každá obsahuje najviac jeden člen A, takže veľkosť A je najviac N max. Ide najmä o hornú hranicu veľkosti akéhokoľvek kliku.

Nech A je klika tvaru Gw, kde w je nejaké slovo. Potom G = Aw -1 , a teda w(G) sa rovná súčtu w(aw -1), kde a prechádza všetkými vrcholmi A. Podľa predchádzajúceho odseku je počet členov najviac N max. , pričom každú množinu aw -1 je možné zredukovať na jeden bod (do bodu a so slovom w), takže jej hmotnosť nie je väčšia ako maximum w max . Keďže celý súčet je w(G) = N max *w max , usúdime, že počet členov je presne N max a každý člen je presne w max . Dokázali sme, že všetky kliknutia majú rovnakú veľkosť: presne N max prvkov.

Nech sú dve kliky A a B, takže vo vnútri A sú všetky prvky spoločné s B, okrem jedného: |A| - |A∩B| = 1.

Keďže A a B majú rovnakú veľkosť, máme aj |B| - |A∩B| = 1, t.j. A a B majú všetky prvky spoločné okrem jedného vrcholu p v A a jedného vrcholu q v B. Chceli by sme dokázať, že tieto vrcholy p,q sú stabilnými priateľmi. Ak to tak nie je, tak nejaké slovo w z nich robí nepriateľov, t.j. pw a qw sú nepriatelia. Ako je uvedené vyššie, Aw a Bw sú tiež kliky a je zrejmé, že opäť majú všetky prvky spoločné, okrem nepriateľov pw a qw. Potom množina Aw ∪ Bw je množina párových nepriateľov. V skutočnosti sú v ňom všetky prvky Aw párovými nepriateľmi, pretože je to klika; to isté platí pre prvky Bw; a zostalo len pár pw, qw - tiež nepriatelia. Ale táto sada má N max +1 prvkov a vyššie sme ukázali, že žiadna sada párových nepriateľov nemôže mať viac ako N max prvkov. Toto je protirečenie, a preto pw a qw nemôžu byť nepriateľmi pre žiadne w. Inými slovami, p a q sú stáli priatelia.

Preklenutie grafov a klikov

Zoberme všetky vrcholy z daného grafu G a z každého vrcholu vyberieme len jednu výstupnú hranu. Takáto voľba definuje podgraf, ktorý nazývame graf rozpätia(graf rozpätia). Môže existovať veľa rôznych grafov preklenutia, ale poďme sa trochu zamyslieť nad tým, ako vyzerajú. Nech je nejaký graf rozpätia R. Ak v ňom vezmeme ľubovoľný vrchol x a začneme sledovať jeho hrany, zakaždým budeme mať jedinú možnosť, pretože v R vychádza z každého vrcholu iba jedna hrana a skôr či neskôr uzavretý cyklus. Možno sa tento cyklus neuzavrie pri x, ale uzavrie sa niekde "ďalej" - napríklad x-->y-->z-->s-->y. Potom z x povedie "chvost" do tohto cyklu. Ak začneme z nejakého iného vrcholu, tiež určite prídeme do cyklu - tohto alebo iného. Ukazuje sa, že ktorýkoľvek vrchol R buď leží na cykle (ktorých môže byť niekoľko), alebo je súčasťou „chvosta“, ktorý vedie k cyklu. To znamená, že R vyzerá takto: je na nich postavený určitý počet cyklov a určitý počet „obrátených“ stromov: každý strom nezačína, ale končí v „koreni“, ktorý leží na jednom z cyklov.

Ku každému vrcholu grafu môžeme priradiť úrovni, zodpovedajúcej jeho vzdialenosti od cyklu v danom grafe rozpätia R. Vrcholy, ktoré ležia na cykle, majú úroveň 0 a vrcholy, ktoré ležia na strome pripojenom k ​​cyklu, dostanú úroveň rovnajúcu sa vzdialenosti v ich strome od „koreňu „ležať na cykle. Niektoré vrcholy nášho grafu majú maximálnu úroveň L. Možno sa všeobecne rovná 0 - t.j. nie sú tam stromy, iba cykly. Možno je väčšia ako nula a vrcholy tejto maximálnej úrovne ležia na najrôznejších stromoch spojených s rôznymi cyklami alebo s jedným.

Chceme vybrať graf rozpätia R takým spôsobom, že všetky vrcholy maximálnej úrovne ležia na tom istom strome. Intuitívne sa dá veriť, že sa to dá, pretože ak to tak nie je – napríklad sú roztrúsené po rôznych stromoch – potom si môžeme vybrať jeden z takýchto maximálnych vrcholov x a zvýšiť jeho úroveň pripojením k R nejakej hrany smerujúcej do x. Potom bude treba vyhodiť nejakú inú hranu a nie je isté, či to nebude bolieť niečo iné... ale to je technický problém, o tom neskôr. Snažím sa len povedať, že to intuitívne nevyzerá veľmi komplikovane.

Pre túto chvíľu predpokladajme, že môžeme zvoliť R tak, aby všetky vrcholy maximálnej úrovne ležali v tom istom strome. Predpokladá sa, že tento strom je netriviálny, t.j. maximálna úroveň L > 0. Na základe tohto predpokladu zostrojíme sfarbenie s klikami A a B, ktoré spĺňa podmienku predchádzajúcej časti, a tým dokážeme, že toto sfarbenie má stabilný pár priateľov.

Vyfarbenie bude nasledovné: vyberieme si nejakú farbu α a touto farbou vyfarbíme všetky hrany v grafe R a všetky ostatné hrany v grafe G - v nejakých iných farbách akýmkoľvek spôsobom (ak je len jedna farba, potom sa R ​​zhoduje s G, takže žiadny problém). Slová pozostávajúce z farby α teda „posúvajú“ vrcholy R pozdĺž svojich stromov smerom k cyklom a potom ich posúvajú pozdĺž cyklov. Potrebujeme len takéto slová.

Nech x je ľubovoľný vrchol maximálnej úrovne L v R a nech K je ľubovoľná klika, ktorá obsahuje x; vieme, že taká klika existuje. Môže K zahŕňať nejaký iný vrchol maximálnej úrovne L? Podľa nášho predpokladu sú všetky takéto vrcholy v tom istom strome ako x, čo znamená, že slovo α L ich vedie na to isté miesto ako x – teda ku koreňu tohto stromu ležiaceho na cykle. Všetky takéto vrcholy sú teda priateľmi x, a preto s ním nemôžu ležať v tej istej klike. Preto okrem x môže K zahŕňať iba vrcholy nižšej úrovne.

Pozrime sa na množinu A = Kα L-1 . Toto je tiež klika a v nej všetky vrcholy, okrem x, dosiahli niektoré zo svojich cyklov v R, pretože všetky vrcholy A okrem x majú úroveň nižšiu ako L. Iba x je stále mimo cyklu, vo vzdialenosti presne 1 od jeho koreňa na cykle. Teraz si zoberme nejaké číslo m, ktoré je násobkom všetkých dĺžok cyklov v R – napríklad súčin všetkých dĺžok cyklov. m má takú vlastnosť, že ak je vrchol y na cykle v R, potom ho slovo α m vráti na svoje miesto: yα m = y. Pozrime sa na kliku B = Aα m . Všetky vrcholy A, okrem x, ležali na cykloch, a preto tam zostali v B; a len x nakoniec vstúpilo do jeho kolobehu a niekde sa tam usadilo. To znamená, že priesečník A a B obsahuje všetky vrcholy A okrem jedného: |A| - |A∩B| = 1. To však podľa predchádzajúcej časti znamená, že naše sfarbenie má stabilný pár, čo bolo potrebné dokázať.

Budovanie maximálnej úrovne.

Zostáva dokázať, že vždy je možné zvoliť rozpätie grafu R tak, aby mal netriviálnu maximálnu úroveň L > 0 a všetky vrcholy tejto úrovne ležali na tom istom strome.

Súčasťou tohto dôkazu je dosť nudná a technická lemma, ktorú som si prečítal a otestoval, ale nebudem to rozpisovať, len pre záujemcov poviem, kde to v článku je. Ale poviem vám, ako sa k tejto lemme dostať.

Budeme potrebovať dve obmedzenia, ktoré môžeme uložiť na graf G. Najprv povieme, že v G nie sú žiadne slučky, t.j. hrany z vrcholu do toho istého vrcholu. Ide o to, že ak je v grafe slučka, potom je veľmi ľahké nájsť synchronizačné sfarbenie iným spôsobom. Vyfarbme túto slučku nejakou farbou α a potom idúc od tohto vrcholu opačným smerom „proti šípkam“ zafarbíme okraje tak, aby farba α vždy viedla k tomuto vrcholu. Keďže graf je prepojený, dá sa to ľahko usporiadať a potom slučka zabezpečí, že určitá mocnina α privedie celý graf do tohto vrcholu.

Ďalej predpokladajme na sekundu, že z nejakého vrcholu p vedú všetky d hrany do rovnakého vrcholu q. Podmienky to umožňujú, ale v tomto prípade túto množinu hrán nazveme zväzok. Naše druhé obmedzenie je toto: neexistuje vrchol r, do ktorého vedú dve spojenia z rôznych vrcholov p a q. Prečo to môžeme nanútiť? Pretože ak existujú väzby od p a q do r, potom pre akékoľvek sfarbenie p,q po prvej farbe zbiehajú k vrcholu r, a preto sú stabilnými priateľmi. Takže v tomto prípade nepotrebujeme celú konštrukciu grafov a klikov, hneď získame stabilných priateľov. Preto môžeme predpokladať, že to tak nie je.

Nakoniec dokážme, že vždy existuje preklenovací graf R, v ktorom nie všetky vrcholy ležia na cykloch, ale existuje niekoľko netriviálnych stromov. Vyberieme nejaké R a predpokladajme, že všetky vrcholy v ňom ležia na cykloch. Ak v grafe G ležia všetky hrany vo zväzkoch – t.j. vždy všetky d hrany vychádzajúce z jedného vrcholu viedli do rovnakého vrcholu - potom výber R by zahŕňal len výber jednej hrany z každého zväzku. V tomto prípade by v R mohol byť len jeden cyklus (napokon niekoľko cyklov v R nemohlo byť navzájom spojených v súvislom grafe G - všetky hrany G spájajú len tie isté vrcholy ako hrany R, pretože tieto sú väzy - a keďže G je spojené, je to nemožné) a akýkoľvek cyklus v G jednoducho vyberie iné hrany z väzieb tohto cyklu, ale v skutočnosti je to rovnaký cyklus, rovnakej dĺžky. To ale znamená, že dĺžky všetkých cyklov v G sú deliteľné touto dĺžkou, čo práve odporuje neperiodickosti G. Preto sa nemôže stať, že v G ležia všetky hrany na väzbách, čo znamená, že existujú nejaké dve hrany p -- >q v R a p-->s mimo R (potrebovali sme dlhý argument o spojkách, aby sme dokázali, že nejaká hrana z p nielenže neleží v preklenutom grafe, ale vedie aj k inému vrcholu s). Potom nahradíme p-->q p-->s, čím sa cyklus „preruší“ a vytvorí sa v ňom nejaký netriviálny chvost. Tento chvost nám v novom grafe poskytne netriviálny strom.

Teraz, zo všetkých grafov R, ktoré majú netriviálne stromy, môžeme vybrať nejaké R, ktoré má maximálny počet vrcholov v cykloch. T.e. má vrcholy nie na cykloch, ale okrem tohto obmedzenia je počet vrcholov na cykloch maximalizovaný. Tento graf má niektoré vrcholy maximálnej úrovne L a môžeme predpokladať, že sú na stromoch vedúcich k rôznym koreňom, inak sme už dosiahli to, čo potrebujeme. Vyberieme jeden takýto vrchol x. Chceme zmeniť graf tak, aby sa tento vrchol stal súčasťou dlhšej trasy v strome, dlhšej ako L, a zvyšok stromov sa nezmenil, a potom bude maximálna úroveň iba v jednom strome, čo je to, čo chcieť. Graf môžete zmeniť tromi spôsobmi:

a) vezmite nejakú hranu y-->x a pridajte ju k R a zahoďte tam existujúcu hranu y-->z;
b) vezmite hranu b-->r, ktorá je práve posledná na ceste z x do jej cyklu (r na cykle), a zahoďte ju a pridajte ďalšie b-->z.
c) vezmite hranu c-->r, ktorá je súčasťou cyklu a zahoďte ju a pridajte ďalšie c-->z.

Lema 7 Trachtmanovho článku podrobne dokazuje, že jedna (alebo v niektorých prípadoch dve) z týchto zmien vedú k požadovanému výsledku. Proces využíva maximalitu R (ak nejaká zmena vedie ku grafu s väčším počtom vrcholov na cykloch ako v R, je to v rozpore s jeho maximalitou), ako aj podmienku definovanú vyššie, že neexistuje vrchol, ku ktorému vedú dve spojky. Výsledkom je, že v každom prípade dostaneme graf R, v ktorom všetky vrcholy maximálnej úrovne ležia na jednom netriviálnom strome.

Aktualizácia o týždeň neskôr: napriek tomu som sa rozhodol urobiť tento záznam úplne sebestačným a tiež prerozprávať dôkaz lemy, na ktorú som poukázal v predchádzajúcom odseku. Bolo by lepšie to urobiť pomocou diagramu, ale nechcem ho kresliť ani vytrhávať z článku, takže to skúsim slovami. Predstavme si teda, že máme preklenutý graf R, ktorý má netriviálne stromy a zo všetkých takýchto grafov v ňom leží maximálny počet vrcholov na cykloch. Naším cieľom je transformovať R na graf rozpätia, v ktorom všetky vrcholy maximálnej úrovne ležia na rovnakom strome; akonáhle takýto graf v procese skúšania dostaneme, okamžite končíme (a je nám jedno, že maximálny graf z hľadiska počtu vrcholov na cykloch sa môže stratiť, to pre nás samo osebe nie je dôležité, používame ho iba v procese). Nech x je vrchol maximálnej úrovne L, T strom, na ktorom leží, r vrchol cyklu C, kde T končí, b-->r posledná hrana pred r na ceste z x do cyklu C. Môžeme predpokladať, že do tohto cyklu sa stále zapájajú nejaké stromy alebo iné, ktoré majú vrcholy úrovne L – inak je už všetko hotové. Z toho vyplýva, že ak sa nám podarí získať strom z T s prvkom väčšieho stupňa ako L a tieto ďalšie stromy nepredĺžime, tak máme hotovo.

Najprv skúsme vykonať operáciu a) vyššie: vezmite nejakú hranu y-->x v G - existuje, pretože graf je spojený a bez slučiek a neleží v R, pretože x maximálna úroveň. Pridajme to k R a vyhodíme nejaké y-->z, ktoré tam bolo predtým. Ak y leží na strome T, tak y-->x uzatvára nový cyklus a v novom grafe leží viac vrcholov na cykloch a stále existujú netriviálne stromy (aspoň tie ostatné, ktoré boli v R), čo je v rozpore s maximálnosťou R. Ak y neleží na T a y-->z nie je súčasťou cyklu C, potom vymazanie y-->z tento cyklus nepreruší a pridanie y-->x predĺži maximálna úroveň stromu T aspoň o jeden a ostatné stromy sa nepredlžujú, takže máme hotovo. Zostávajúca možnosť je, keď y-->z leží na cykle C, ktorý sa teraz prerušil a vytvoril sa nový cyklus: z r na y, potom y-->x, potom z x do r pozdĺž bývalého stromu. Dĺžka tohto cyklu je l(ry)+1+L, pričom dĺžka starého cyklu C bola l(ry)+1+l(zr). Nový cyklus nemôže byť dlhší ako starý, to odporuje maximálnosti R, takže vidíme, že L ≤ l(zr), t.j. dĺžka trasy od z do r v starej slučke. Na druhej strane, v novom grafe má teraz vrchol z úroveň aspoň l(zr), a ak je väčšia ako L, tak sme hotoví. Môžeme teda predpokladať, že l(zr)=L. Aby sme to zhrnuli: predpokladáme, že a) nefunguje, a potom vieme, že y-->z leží na cykle C, l(zr) = L.

Teraz skúsme operáciu b): nahraďte hranu b-->r nejakou inou hranou b-->d. Pozrime sa, kde leží nový vrchol d. Ak na strome T, potom sme vytvorili nový cyklus bez porušenia predchádzajúceho a vyvrátili sme maximalizáciu R. Ak na inom strome, potom maximálne vrcholy T vrátane x budú mať teraz úroveň väčšiu ako L, zatiaľ čo ostatné stromy nebudú a máme hotovo . Ak na inom cykle, nie na C, potom teraz urobíme a) spolu s b) aj a): keďže vieme, že y-->z leží na C, potom táto operácia preruší C, ale nie nový cyklus, ku ktorému teraz je to spojený strom Τ a tento strom bude mať teraz vrcholy o úroveň väčšiu ako L a znova sme skončili.

Zostávajúca možnosť je, keď b-->d je tiež spojené s cyklom C, na inom mieste ako r, alebo na rovnakom mieste a potom d=r. Potom, čo sme nahradili b-->r za b-->d, dostali sme rovnakú situáciu ako pôvodne - strom T, uzol x úrovne L atď. - len strom je teraz pripojený k cyklu cez vrchol d. Ak vezmeme do úvahy operáciu a), dospejeme k záveru (za predpokladu, že nefunguje), že l(zd) = L, rovnako ako sme predtým usúdili, že l(zr) = L. Ale ak l(zd)=l(zr), t.j. vzdialenosť pozdĺž cyklu od z je rovnaká k d a r, potom je to rovnaký vrchol: d=r. Takže ak b) nefunguje, tak akákoľvek hrana z b musí viesť do r, t.j. okraje od b tvoria zväzok.

Nakoniec uvažujme hranu c-->r ležiacu na cykle C. Keďže môžeme predpokladať, že všetky hrany z b ležia na spojnici vedúcej do r, môžeme tiež uložiť obmedzenie uvedené vyššie, že nemôžu existovať dve spojnice vedúce k jeden vrchol, nie všetky hrany z c vedú do r, ale je tam nejaká hrana c-->e. Nahradíme c-->r za c-->e. Kde môže ležať vrchol e? Nie na strome T, pretože by to "predĺžilo" cyklus C, čo je v rozpore s maximom R. Takže e leží na inom strome alebo na inom cykle, alebo dokonca na rovnakom cykle C, ale nie na vrchole r . Potom je strom T, predtým ako sa pripojí k cyklu, teraz rozšírený aspoň o jednu hranu vychádzajúcu z r a možno aj o viac (iba o jednu, ak e leží hneď za r, a c--> e opäť uzatvára cyklus C, odvodzujúce z neho len r). To znamená, že úroveň vrcholu x a ostatných maximálnych vrcholov T je teraz aspoň L + 1 a ostatné stromy sa nepredĺžili a opäť máme to, čo potrebujeme.

Nachádzate sa na omaľovánke cesty. Omaľovánku, ktorú si prezeráte, naši návštevníci opísali takto: "" Tu nájdete množstvo omaľovánok online. Cestné omaľovánky si môžete stiahnuť a tiež vytlačiť zadarmo. Ako viete, kreatívne aktivity zohrávajú obrovskú úlohu vo vývoji dieťaťa. Aktivujú duševnú činnosť, formujú estetický vkus a vštepujú lásku k umeniu. Proces vyfarbovania obrázkov na tému cesty rozvíja jemné motorické zručnosti, vytrvalosť a presnosť, pomáha dozvedieť sa viac o svete okolo nás, predstaví vám celú škálu farieb a odtieňov. Každý deň pridávame na našu stránku nové bezplatné omaľovánky pre chlapcov a dievčatá, ktoré si môžete vyfarbiť online alebo stiahnuť a vytlačiť. Pohodlný katalóg zostavený podľa kategórií uľahčí nájdenie správneho obrázka a veľký výber omaľovánok vám umožní nájsť každý deň novú zaujímavú tému na vyfarbenie.