Moja bojanka na putu do škole. Stranice za bojanje Pravila puta

Ažuriranje stranice
10.12.2006 15:46
Za ljubitelje automobila i crtića - bojanke iz crtića Automobili.

Zahvaljujući Disneyju i Pixaru, u lipnju 2006. cijeli je svijet vidio crtić u kojem su samo automobili postali junaci.

Automobili u crtiću Cars ("Cars") žive obične živote - jedan drži gumarsku radnju, drugi tuning studio, a neki samo žive za svoje zadovoljstvo, poput hipija Fillmorea (Volkswagen T1) ili njegovog prijatelja - veterana svjetskog rata Serge (Willys). Glavni lik slike McQueen, nadimak "Munja", sanja samo o utrkama, pobjedama i slavi. Jednom u Radiator Districtu na poznatoj američkoj autocesti 66, "zeleni" McQueen svima odmah govori koliko je brz i cool. No, prvi start u NASCAR utrci raspršuje njegove iluzije. Prijatelji pomažu junaku da preživi gubitak - stari Meiter tegljač (GMC Pick-up), mentor Doc Hudson (Hudson Hornet) i mali Luigi (Fiat 600), koji sanja da vidi pravi Ferrari.

Pa, gdje bez romantične ljepotice Sally (Porsche sa šarmantnom tetovažom 911)! Uvelike zahvaljujući njima, McQueen će ipak pobijediti u utrci, pobijedivši glavnog rivala Chica (Plymouth Hemi Cuda). Ostvarit će se i Luigijev san - jednog će dana u njegovu radnju navratiti "pastuh iz Maranella" na promjenu guma, kojeg je, usput, izrazio sam "Crveni barun" Michael Schumacher.

Važno je napomenuti da su i kreatori slike i oni koji su je izrazili ljudi koji se bave automobilima. Primjerice, redatelj Joe Lasseter proveo je većinu svog djetinjstva u tvornici Chevrolet, gdje je njegov otac bio jedan od glavnih dizajnera. Jay Mays, vodeći dizajner koncerna Ford, djelovao je kao konzultant. Uz već spomenutog sedmerostrukog svjetskog prvaka Formule 1 Michaela Schumachera, u davanju glasova herojima sudjelovale su zvijezde NASCAR-a Richard Petty i Paul Newman, kao i legendarni trkač Michael Andretti.

Korištena je samo izvorna buka automobila - primjerice, posebno za epizode utrka, zvuk je sniman nekoliko tjedana na američkim ovalima tijekom NASCAR natjecanja. Bilo je potrebno više od dvije godine za stvaranje slike, čiji je proračun bio 70 milijuna dolara. Tijekom tog vremena stvoreno je 43 tisuće različitih skica automobila, a svaki crtež trajao je više od 17 sati. U filmu je ukupno 120 automobilskih likova, od novih Porschea i Ferrarija do starinskih Ford T-ova.

Dječake možete dugo zaokupiti ako ih pozovete da se igraju autićima u pješčaniku. Ali što ako je vani hladno, djetetu je dosadno. U tom slučaju možete preuzeti i ispisati sljedeće predloške za automobilske ceste. Zabava će započeti izrezivanjem svih prstenova, zavoja i ravnih cesta. Iz ovih predložaka dijete može napraviti cestu bilo kojeg oblika, samo pripazite da je ispisan odgovarajući broj potrebnih A4 listova.

Preuzmite ravnu cestu za automobile

Ovi će listovi biti najpotrebniji. Na list A4 formata postavili smo 3 ceste koje je potrebno isprintati i izrezati. Pokažite djetetu kako presjeći cestu pod pravim kutom kako bi dionica bila potrebne dužine.

Cesta za automobile: prsten

Za povezivanje cesta trebat će vam prsten, čiji je predložak prikazan gore, i počnite graditi svoju infrastrukturu od njega.

Automobilska cesta: skretanje ravno

Predstavljeni zavoji omogućit će dječaku da okrene cestu za 90 stupnjeva, u smjeru koji mu je potreban.

Nije oštro skretanje ceste za automobile

Sljedeći predložak A4 pomoći će vam da okrenete cestu pod bilo kojim radijusom.

Nalazite se na stranici za bojanje ceste. Stranicu za bojanje koju gledate naši posjetitelji opisuju na sljedeći način "" Ovdje ćete pronaći mnogo stranica za bojanje na mreži. Možete preuzeti stranice za bojanje ceste i također ih besplatno ispisati. Kao što znate, kreativne aktivnosti igraju veliku ulogu u razvoju djeteta. Aktiviraju mentalnu aktivnost, formiraju estetski ukus i usađuju ljubav prema umjetnosti. Proces bojanja slika na temu ceste razvija fine motoričke sposobnosti, upornost i točnost, pomaže da naučite više o svijetu oko nas, upoznaje vas sa svom raznolikošću boja i nijansi. Svaki dan na našu web stranicu dodajemo nove besplatne stranice za bojanje za dječake i djevojčice, koje možete bojati online ili preuzeti i ispisati. Prikladan katalog sastavljen po kategorijama olakšat će pronalaženje prave slike, a veliki izbor stranica za bojanje omogućit će vam da svaki dan pronađete novu zanimljivu temu za bojanje.

Djetetovo poznavanje Pravila puta jedan je od glavnih uvjeta za njegovu sigurnost na ulici. Mnogi pješaci, uključujući i odrasle, prilično su neozbiljni u pogledu poštivanja ovih pravila, što često postaje uzrokom prometnih nesreća različite težine. Djeca moraju jasno shvatiti da su na ulici u selu puni sudionici ceste, pa je poštivanje prometnih pravila njihova odgovornost.

Stranice za bojanje Pravila puta za djecu.

Učiti dijete pravilima ponašanja na ulici (ceste, nogostupi, gradski prijevoz) treba započeti u vrlo ranoj dobi, prije nego što nauči samostalno hodati i trčati. I tu je vrlo važan primjer roditelja i drugih odraslih osoba s kojima je dijete na ulici. Ne samo da svom djetetu morate reći i objasniti pravila na cesti, već ih se i sami strogo pridržavati. Stranice za bojanje prometnih pravila na ovoj stranici prvenstveno su namijenjene predškolskoj dobi i pomoći će djeci da nauče osnove ponašanja na cesti, kao iu njenoj blizini.

1. Stranica za bojanje semafora.

Najbolje mjesto za siguran prelazak ceste je na pješačkom prijelazu opremljenom semaforima. Stranice za bojanje semafora također sadrže male pjesmice kako bi djeca lakše zapamtila pravila za njihovo korištenje.

• Uvijek započnite vožnju tek kada je na semaforu zeleno.
• Nikada ne prelazite cestu na crveni ili žuti prometni signal, čak i ako u blizini nema vozila.
• Kad upalite zeleno svjetlo, dodatno provjerite jeste li sigurni – pogledajte lijevo, pa desno.

2. Bojanje pješačkog prijelaza.

Naučite dijete da kolnik prelazi samo na pješačkom prijelazu. Stranice za bojanje pješačkih prijelaza naučit će djecu pravilnom prijelazu ceste. Prijelaz koji nije opremljen semaforom naziva se nereguliranim.

• Pješački prijelaz označen je na površini kolnika zebrom.
• Prije prelaska ceste pažljivo je pregledajte, uvjerite se da u blizini nema prometa.
• Pređi cestu, ne pretrčavaj.
• Ne prelazite ulicu.
• Obratite posebnu pozornost na vozila koja stoje i zaklanjaju vam pogled.
• Prestanite razgovarati telefonom dok hodate preko pješačkog prijelaza.
• Ako u blizini postoje podzemni ili povišeni prolazi, svakako ih koristite, na takvim je mjestima promet posebno intenzivan.

3. Nogostupi.

Nogostup je namijenjen za promet pješaka. Potičite djecu da se pravilno ponašaju na pločnicima, posebno onima koji se nalaze u područjima s gustim prometom.

• Kada vozite nogostupom uz cestu, nemojte mu se previše približavati.
• Pažljivo promatrajte mogući izlazak automobila iz dvorišta, uličica.
• Ne igrajte se loptom na pločniku, ne trčite.

4. Stranice za bojanje s pravilima ponašanja za djecu u gradskom javnom prijevozu i na autobusnim stajalištima.

Ove bojanke naučit će djecu pravilima sigurnog korištenja javnog prijevoza.

• Stajalište javnog prijevoza opasno je mjesto zbog moguće slabe preglednosti ceste i velike gužve ljudi koji mogu slučajno izgurati dijete s nogostupa na kolnik. Ovdje morate biti posebno oprezni.
• Priđite vratima transportnog sredstva tek nakon što se potpuno zaustavi.
• Nakon što napustite vozilo, nastavite prelaziti cestu tek nakon što vozilo izađe iz stajališta.

Osim ovih osnovnih pravila prometa, djecu će zanimati bojanje prometnih znakova. Predstavljene bojanke prema prometnim pravilima prikladne su za malu djecu, predškolce i učenike osnovnoškolske dobi, kao i za korištenje u dječjim vrtićima i na nastavi u osnovnoj školi. Sve slike s Pravilima ceste potpuno su besplatne - mogu se preuzeti i ispisati.

(ovaj bi unos mogao biti zanimljiv čitateljima koji poznaju matematiku i simpatizerima)

Neki dan sam čitao o zanimljivom problemu iz teorije grafova - pretpostavci o bojanju ceste. Ova pretpostavka postoji već 37 godina, ali ju je prije tri godine dokazao izraelski matematičar Abraham Trachtman. Dokaz se pokazao prilično elementarnim i uz određene poteškoće (jer mi je mozak atrofirao) uspjela sam ga pročitati i razumjeti, a čak ću ga pokušati objasniti u ovom zapisu.

Problem se može objasniti na primjeru. Zamislite kartu grada, gdje na svakom raskrižju možete ići u jednom od četiri smjera - sjever, jug, istok i zapad. Ako auto krene na nekom raskrižju i slijedi neki popis smjerova - "sjever, sjever, istok" itd. - onda će ona na kraju stići na neko drugo raskrižje. Je li moguće pronaći takav popis uputa, možda dugačak, koji će dovesti automobil na isto mjesto, bez obzira gdje je krenuo? Ako karta izgleda kao Manhattan - pravilna mreža - onda ne, ali možda na njoj ima mnogo slijepih ulica i neočekivanih zaokreta?

Ili drugi primjer. Vaš prijatelj je zapeo u labirintu u kojem morate pronaći središte i nazvao vas je tražeći pomoć. Znaš kako labirint funkcionira, ali ne znaš gdje ti je prijatelj. Može li postojati niz naredbi koje će sigurno dovesti vašeg prijatelja do središta, bez obzira gdje se nalazio?

U ova dva primjera, "smjerovi" u svakoj točki su fiksni, a rješenje ili postoji ili ne. Ali u općenitijem slučaju, ovaj problem postavlja sljedeće pitanje: ako možemo izabrati kamo pokazuje, na primjer, "zapad, sjever, istok, jug", na svakom raskrižju na svoj način, možemo li onda osigurati postojanje "riječi za sinkronizaciju " - niz naredbi, koje će s bilo kojeg mjesta dovesti do jedne fiksne?

U općem slučaju, neka postoji usmjereni graf G - sa "strelicama" bridova između vrhova. Neka ovaj graf ima jednoliki izlazni stupanj d - to znači da iz svakog vrha izlazi točno d bridova. Pritom u svaki pojedini vrh može ući različiti broj, ne nužno d. Pretpostavimo da imamo skup od d slova neke abecede, koje ćemo nazvati "cvjetovi". Zatim se "bojenje" grafa daje dodjeljivanjem za svaki vrh svih d slova za d njegovih izlaznih bridova. Dakle, ako se "smjestimo" na nekom vrhu, i želimo "ići" negdje prema boji α, tada će nam bojanje uvijek reći koji rub trebamo ići do kojeg novog vrha. "Riječ" je bilo koji niz boja slova. Zatim, ako je u grafu zadano bojanje, a x je neki vrh i w je neka riječ, tada xw označava vrh do kojeg ćemo doći, počevši od x i nakon riječi w.

Bojanka se zove sinkronizirajući, ako postoji riječ w koja vodi bilo koji vrh x do jednog fiksnog vrha x 0 . U ovom slučaju w se zove sinkronizirati riječ. Pitanje koje postavlja problem bojanja cesta je: postoji li uvijek sinkrono bojanje? Je li uvijek moguće obojiti rubove grafa na takav način da se svi vrhovi mogu svesti na jedan?

Ovaj problem ima primjenu u nekoliko različitih područja, o čemu se može čitati, primjerice, na Wikipediji. Na primjer, u informatici, u teoriji automata. Graf s bojanjem može se smatrati determinističkim konačnim strojem u kojem su vrhovi stanja, a rubovi pokazuju kako se kretati između njih. Pretpostavimo da tim automatom upravljamo iz daljine, šaljući naredbe preko nekog informacijskog kanala, a zbog nekih kvarova taj kanal je zagađen, automat je dobio neke pogrešne upute, i sad uopće ne znamo u kakvom je stanju. Zatim, ako postoji riječ za sinkronizaciju, možemo je dovesti u poznato stanje, bez obzira gdje se sada nalazi.

Dakle, kada postoji sinkronizirano bojanje? Pretpostavka o bojanju ceste nameće još dva ograničenja na graf (osim činjenice da svaki vrh ima točno d bridova). Prvo, graf mora biti jako povezan, što znači da postoji ruta od bilo kojeg vrha do bilo kojeg drugog. Drugo, graf ne smije biti periodičan. Zamislimo da se svi vrhovi grafa mogu podijeliti u skupove V 1 , V 2 , ... V n , tako da bilo koji brid grafa povezuje vrhove iz nekih V i i V i+1 ili V n i V 0 . Nema bridova između vrhova u svakom V, a ne mogu ni "skakati" između bilo kojeg V, samo redom. Takav graf nazivamo periodičnim. Jasno je da takav graf ne može imati sinkronizirajuće bojanje, jer bez obzira na to kako bojite i kojim riječima idete, dva vrha u različitim V i nikada se neće spojiti - oni će ići oko ciklusa.

Teorem o bojanju ceste kaže da su ovi uvjeti dovoljni: bilo koji neperiodični snažno povezani usmjereni graf s d bridova iz svakog vrha ima sinkronizirajuću boju. Prvi put je formuliran kao pretpostavka 1970. godine i od tada je bilo mnogo parcijalnih rezultata koji dokazuju posebne slučajeve, ali potpuni dokaz pojavio se tek 2007. godine. Ono što slijedi je moje prepričavanje gotovo cijelog dokaza (osim jedne tehničke leme).

Periodičnost

Prije svega, zamijenimo uvjet neperiodičnosti drugim koji mu je ekvivalentan. Graf je periodičan ako i samo ako postoji broj N>1 koji dijeli duljinu bilo kojeg ciklusa u grafu. Oni. naš zahtjev neperiodičnosti je ekvivalentan tvrdnji da ne postoji takav N, ili drugim riječima, najveći zajednički djelitelj duljina svih ciklusa u grafu je 1. Dokazat ćemo da svaki graf koji zadovoljava ovaj uvjet ima sinkronizirajuće bojenje.

Dokazati da je periodičnost ekvivalentna uvjetu "postoji N>1 kojim je duljina bilo kojeg ciklusa djeljiva" trivijalno je u jednom smjeru, a lako u drugom. Ako ste voljni ovo prihvatiti na vjeru, lako možete preskočiti ostatak ovog paragrafa; to nije važno za ostatak dokaza. Ako je graf periodičan, tj. Kako je moguće vrhove podijeliti u skupove V 1 , V 2 , ... V n , tako da bridovi idu između njih u ciklusu, onda je očito da duljina bilo kojeg ciklusa mora biti djeljiva s n, tj. novi uvjet je ispunjen. Ovo je trivijalan smjer, ali za našu zamjenu trebamo samo drugi smjer. Pretpostavimo da postoji takav N>1, koji dijeli duljinu bilo kojeg ciklusa. Izgradimo u našem grafu neko usmjereno razapinjuće stablo (spanning tree) s korijenom u vrhu r. Postoji put do bilo kojeg vrha x u ovom stablu počevši od korijena duljine l(x). Sada tvrdimo da za bilo koji rub p-->q u grafu, l(q) = l(p) + 1 (mod N). Ako je ova tvrdnja točna, onda iz nje odmah slijedi da sve vrhove možemo podijeliti u skupove V i prema l(x) mod N, a graf će biti periodičan. Zašto je ova izjava istinita? Ako je p-->q dio razapinjućeg stabla, onda je to očito, jer tada samo l(q) = l(p) + 1. Ako to nije slučaj, tada pišemo rute od korijena r do vrhovi p,q kao R p i R q . Neka također R r znači rutu od q natrag do r u grafu (graf je povezan, dakle postoji). Tada možemo napisati dva ciklusa: R p p-->q R r, i R q R r. Prema uvjetu, duljine ovih ciklusa su djeljive s N, oduzimajući i poništavajući ukupne vrijednosti, dobivamo da je l(p)+1 = l(q) mod N, što je trebalo i dokazati.

Stabilno prijateljstvo i indukcija

Neka je zadano neko bojanje grafa G. Dva vrha p,q nazivamo prijateljima ako ih neka riječ w dovodi u isti vrh: pw = qw. Nazovimo p,q neprijateljima ako se "nikad ne sretnu". Nazovimo p,q stabilnim prijateljima ako nakon izvršenja bilo koje riječi w ostanu prijatelji: pw možda neće doći u isti vrh kao qw, ali nakon još malo w" može. Stabilni prijatelji nikada ne postaju neprijatelji.

Relacija stabilnosti između vrhova je, prvo, ekvivalencija (refleksivna je, simetrična i tranzitivna), i drugo, očuvana je strukturom grafa: ako su p,q stabilni prijatelji, p je povezan bridom s p" , q s q", a ti rubovi iste boje, tada su p" i q" također stabilni prijatelji. To znači da je stabilno prijateljstvo kongruencija i može se podijeliti na: stvoriti novi graf G", čiji će vrhovi biti stabilne klase ekvivalencije prijateljstva u G. Ako postoji barem jedan stabilan par u G, tada će G" biti manji od G veličine. Štoviše, ako u izvornom grafu G iz svakog vrha ima d bridova, tada će u G" biti isto. Na primjer, ako je P vrh novog grafa, koji je klasa ekvivalencije originalnih vrhova p1, p2... , a α je bilo koje boje, tada bridovi p1--α--> q1, p2---α-->q2, itd. svi vode do vrhova q1, q2..., koji su u stabilnom prijateljstvu sa svakim drugi, i stoga leže u jednom novom vrhu Q, tako da svi ti bridovi postaju novi brid P --α-->Q I tako dalje za svaku od d boja.

Štoviše, ako je G bio neperiodičan, onda G" jest. Jer - korištenjem naše alternativne definicije periodičnosti - bilo koji ciklus u G pretvara se u ciklus u G", pa ako su sve duljine ciklusa u G" djeljive s n > 1, onda isto vrijedi za sve cikluse u G. Dakle, periodičnost G" implicira periodičnost G.

Pretpostavimo da smo u G" uspjeli pronaći sinkronizujuće bojanje. Ono se sada može koristiti u G umjesto bojanja s kojim smo započeli: svaki rub p-->q dobit će novu boju u skladu s novom bojom ruba P-->Q. Malo preciznije, trebali bismo reći ovako: na svakom vrhu P grafa G" dobiva se novo bojanje nekom permutacijom svih boja π P: rub koji je obojan bojom α dobiva novu boja π P (α). Zatim u izvornom grafu G, na svakom vrhu p iz klase stabilnosti P, primjenjujemo istu permutaciju π P da prebojimo njegove rubove. Nova boja grafa G općenito definira neke nove koncepte "prijateljstva", "neprijateljstva" i "stabilnosti" koji nisu identični izvornim. Ali unatoč tome, ako su dva vrha p, q bili stabilni prijatelji u starom bojanju - pripadali su istoj klasi P - tada će ostati stabilni prijatelji u novom. To je zato što bilo koji niz w koji dovodi p,q u jedan vrh može biti "prebačen" sa starog bojanja na novi, ili obrnuto, koristeći permutaciju π P na svakom vrhu od p duž ceste. Kako su p,q stabilni u starom bojanju i takvi ostaju "cijelim putem", svaki međupar vrhova p n , q n na putu od p,q do zajedničkog vrha bit će stabilan, tj. leže unutar istog vrha P n i stoga primaju istu permutaciju π P n .

Novo bojanje se sinkronizira za G", tj. neka sekvenca w dovodi sve vrhove u jedan vrh P. Ako sada primijenimo w na novo bojanje u G, tada svi vrhovi konvergiraju negdje "unutar P". Kao što je gore navedeno, svi vrhovi unutar klase P ostaju stabilni u novom bojanju, što znači da sada možemo nastaviti w, okupljajući preostale parove vrhova koji su još uvijek odvojeni, uvijek iznova, dok sve ne konvergira u jedan vrh G. Dakle, novi bojanje je sinkronizirano za G.

Iz svega ovoga slijedi da je za dokaz teorema dovoljno dokazati da u svakom grafu koji ispunjava uvjete postoji bojanje u kojem postoji par stabilnih prijatelja. Jer tada je moguće prijeći s grafa G na graf G" manje veličine, a on također ispunjava sve uvjete. Koristeći induktivni argument, možemo pretpostaviti da je za grafove manje veličine problem već riješen, a tada će sinkronizirajuće bojenje za G" također biti sinkronizirajuće za G .

Klike i maksimalni skupovi

Za bilo koji podskup A vrhova grafa i riječi w, Aw označava skup vrhova do kojih ćemo doći, počevši od svih vrhova A i slijedeći riječ w. Ako polazimo od svih vrhova grafa općenito, onda to označavamo s Gw. U ovoj notaciji, sinkronizirajuće bojenje znači da postoji w takav da je Gw skup jednog elementa.

Ako skup vrhova A ima oblik Gw za neki w, a osim toga bilo koja dva vrha u A su neprijatelji, tj. nikada ne konvergiraju, nazovimo A klika. Klike postoje jer uvijek možemo početi s cijelim brojem G, uzeti par prijateljskih vrhova, prijeći w koji ih povezuje i smanjiti broj vrhova za jedan; nastavite ovako dok ne ostanu samo neprijatelji ili dok ne ostane samo jedan vrh - također u ovom slučaju klika, samo trivijalno.

Ako je A klika, tada je za svaku riječ w Aw također klika; to je jasno jer neprijatelji ostaju neprijatelji. Ako je x bilo koji vrh grafa, tada postoji klika koja sadrži x. Ovo slijedi iz činjenice da postoji neka klika A (vidi prethodni paragraf); ako je p vrh u njemu, tada postoji riječ w koja vodi od p do x, jer povezani graf; tada je Aw klika koja uključuje x.

Klikovi će nam pomoći da dokažemo da postoji bojanje sa stabilnim prijateljima - prema prethodnom odjeljku, to je dovoljno za dokaz teorema. Kroz ovaj odjeljak ćemo dokazati da ako postoje dvije klike A i B, tako da su svi vrhovi u njima zajednički, osim jednog u A i jednog u B, tada su ta dva vrha stabilni prijatelji. Dakle, problem se svodi na pronalaženje bojanja koje sadrži takve klike A i B.

Kako bismo bolje razumjeli kako klike funkcioniraju, korisno je dodijeliti težine vrhovima u grafu. Pokažimo da imamo način da dodijelimo pozitivnu težinu w(x) svakom vrhu x, tako da ako za bilo koji vrh x zbrojiti težine svih vrhova koji imaju bridove u x, tada dobivamo d*w(x), gdje je d broj bridova iz svakog vrha. Ovo slijedi iz linearne algebre, a ako ne znate što je svojstvena vrijednost, preskočite ostatak ovog paragrafa i vjerujte postojanju takvog w(x). Ako je M matrica grafa G (ćelija (i,j) je 1 ako postoji rub i-->j, i 0 ako takav rub ne postoji), tada w(x), kako sam ih opisao, su elementi svojstvenog vektora lijevo ovu matricu za svojstvenu vrijednost d. Znamo da takav vektor postoji jer je d svojstvena vrijednost: ima trivijalni svojstveni vektor desno(1,1,....1) - to odmah proizlazi iz činjenice da iz svakog vrha izlazi točno d bridova.

Ako je A bilo koji skup vrhova, tada w(A) označava zbroj težina svih vrhova u A; a w(G) je zbroj težina svih vrhova u grafu. Nadalje, ako je s bilo koja riječ, tada neka As -1 označava skup vrhova do kojih dolazite iz A ako idete "u suprotnom smjeru" duž s, u svakom koraku zamjenjujući svaki vrh s tim vrhovima (ako postoje) koji mu idu u odgovarajućoj boji.

Razmotrimo sada sve skupove vrhova koji se mogu spojiti u jednu točku, tj. A takav da, za neki w, Aw sadrži samo jedan vrh. Oni skupovi A koji od svih takvih imaju najveću težinu w(A) nazivaju se maksimalnim skupovima. Ako je bojanje sinkronizirajuće, tada je cijeli graf G maksimalan skup (jedinstven), ali inače nije.

Ako je A bilo koji skup vrhova, tada je zbroj svih w(Aα -1), gdje α prolazi kroz svih d boja, jednak d*w(A) - ovo je samo generalizacija svojstva glavne težine iz jednog vrh na skup vrhova A. Ako je, osim toga, A maksimalan skup, tada svaki od w(Aα -1) ne može biti veći od w(A), jer ti skupovi također konvergiraju na jedan vrh. A budući da je zbroj d ovih težina jednak d*w(A), ispada da je svaki od njih jednak w(A), a svi ti skupovi su također maksimalni. Ovo odmah implicira da ako je A maksimalno, onda je Aw -1 također maksimalno za bilo koju riječ w.

Maksimalni skupovi su korisni jer njihove disjunktne instance mogu pokriti cijeli graf. Dokažimo to.

Neka imamo skup maksimalnih skupova A 1 ...A n koji se ne sijeku u parovima i svode se na pojedinačne vrhove a 1 ...a n istom riječi w (u početnom slučaju bit će n=1 i samo jedan set, tako da je lako započeti). Jasno je da se svi a 1 ...a n međusobno razlikuju, jer bi inače bilo moguće maksimalni skup još više proširiti elementima drugog s istim završnim vrhom. Pretpostavimo da svi A i zajedno još nisu iscrpili sve vrhove od G, i neka je x vrh izvan svih A i . Budući da je graf povezan, postoji neki put h od a 1 do x. Tada n maksimalnih skupova A i h -1 w -1 ide po riječi whw do krajnjih vrhova a 1 ...a n , a maksimalni skup A 1 ide do nekog vrha Awhw = (Aw)hw = (a 1 h)w = xw. Ovaj vrh xw također mora biti različit od svih a 1 ...a n , jer bi inače maksimalni skup A i mogao biti upotpunjen elementom x. A budući da svi ti n + 1 skupovi - svi A i h -1 w -1 plus A 1 - idu duž whw do različitih vrhova, svi su po paru disjunktni. Nastavit ćemo ovu ekspanziju sve dok ne bude vrhova izvan skupa.

Dakle, možemo pokriti cijeli graf G disjunktnim maksimalnim skupovima. Budući da su maksimalni, svi imaju isti ukupni w max , pa je stoga njihov broj u pokrivanju N max = w(G)/w max .

Sada razmotrite bilo koji skup A koji se sastoji od parova neprijatelja. Na primjer, klika je primjer takvog skupa (i također ima oblik Gw). Unutar maksimalnog skupa ne može postojati par neprijatelja jer se tada ne bi moglo spojiti. Dakle, u pokrivanju od N max maksimalnih skupova, svaki sadrži najviše jedan član od A, tako da je veličina A najviše N max. Konkretno, ovo je gornja granica veličine bilo koje klike.

Neka je A klika oblika Gw, gdje je w neka riječ. Tada je G = Aw -1 , te je prema tome w(G) jednak zbroju w(aw -1), gdje a prolazi kroz sve vrhove A. Broj članova, prema prethodnom paragrafu, je najviše N max , a svaki skup aw -1 može se svesti na jednu točku (na točku a s riječju w), pa njegova težina nije veća od maksimalnog w max . Budući da je cijeli zbroj w(G) = N max *w max , zaključujemo da je broj članova točno N max , a svaki član je točno w max . Dokazali smo da svi klikovi imaju istu veličinu: točno N max elemenata.

Neka postoje dvije klike A i B, tako da su unutar A svi elementi zajednički s B, osim jednog: |A| - |A∩B| = 1.

Budući da A i B imaju istu veličinu, imamo i |B| - |A∩B| = 1, tj. A i B imaju sve zajedničke elemente osim jednog vrha p u A i jednog vrha q u B. Željeli bismo dokazati da su ti vrhovi p,q stabilni prijatelji. Ako to nije slučaj, onda ih neka riječ w čini neprijateljima, tj. pw i qw su neprijatelji. Kao što je prikazano gore, Aw i Bw su također klike, i očito je da opet imaju sve elemente zajedničke, osim neprijatelja pw i qw. Tada je skup Aw ∪ Bw skup parova neprijatelja. Doista, u njemu su svi elementi Aw-a neprijatelji u paru, jer je to klika; isto vrijedi i za elemente Bw; i ostalo je samo par pw, qw - također neprijatelja. Ali ovaj skup ima N max +1 elemenata, a gore smo pokazali da bilo koji skup neprijatelja u paru ne može imati više od N max elemenata. Ovo je kontradikcija, i stoga pw i qw ne mogu biti neprijatelji za bilo koje w. Drugim riječima, p i q su stabilni prijatelji.

Spanning grafovi i klike

Uzmimo sve vrhove iz zadanog grafa G i izaberimo samo jedan izlazni brid iz svakog vrha. Takav izbor definira podgraf koji nazivamo razapinjući graf(rasponski graf). Može postojati mnogo različitih rasponskih grafova, ali razmislimo malo o tome kako izgledaju. Neka postoji neki razapinjući graf R. Ako uzmemo bilo koji vrh x u njemu i počnemo pratiti njegove bridove, tada ćemo svaki put imati jedini izbor, jer u R samo jedan brid izlazi iz svakog vrha, i prije ili kasnije ćemo zatvoriti ciklus. Možda se ovaj ciklus neće zatvoriti na x, nego će se zatvoriti negdje "dalje" - npr. x-->y-->z-->s-->y. Tada će od x voditi "rep" do ovog ciklusa. Ako krenemo od nekog drugog vrha, također ćemo sigurno doći do ciklusa - ovog ili nekog drugog. Ispada da svaki vrh od R ili leži na ciklusu (kojih može biti nekoliko), ili je dio "repa" koji vodi do ciklusa. To znači da R izgleda ovako: određeni broj ciklusa, a na njima je izgrađen određeni broj "obrnutih" stabala: svako stablo ne počinje, već završava u "korijenu" koji leži na jednom od ciklusa.

Svakom vrhu grafa možemo dodijeliti razini, što odgovara njegovoj udaljenosti od ciklusa u danom razapinjućem grafu R. Vrhovi koji leže na ciklusu imaju razinu 0, a vrhovi koji leže na stablu pripojenom ciklusu dobivaju razinu jednaku udaljenosti u njihovom stablu do "korijena " ležanje na ciklusu. Neki vrhovi našeg grafa imaju maksimalnu razinu L. Možda je ona općenito jednaka 0 - tj. nema drveća, samo ciklusi. Možda je veći od nule, a vrhovi ove maksimalne razine leže na svim vrstama različitih stabala povezanih s različitim ciklusima ili s jednim.

Želimo odabrati razapinjući graf R na takav način da svi vrhovi maksimalne razine leže na istom stablu. Intuitivno se može vjerovati da se to može učiniti, jer ako to nije slučaj - na primjer, oni su raštrkani po različitim stablima - tada se može odabrati jedan od takvih maksimalnih vrhova x i povećati njegovu razinu pričvršćivanjem na R nekog ruba koji ide do x. Onda će se morati izbaciti neki drugi rub, a nije sigurno da neće nešto drugo ozlijediti... ali to je tehnički problem, o tome kasnije. Samo pokušavam reći da intuitivno ne izgleda jako komplicirano.

Za sada pretpostavimo da možemo izabrati R tako da svi vrhovi maksimalne razine leže u istom stablu. Pretpostavlja se da je ovo stablo netrivijalno, tj. maksimalna razina L > 0. Na temelju ove pretpostavke konstruirat ćemo bojanje s klikama A i B u njemu, zadovoljavajući uvjet iz prethodnog odjeljka, čime ćemo dokazati da to bojanje ima stabilan par prijatelja.

Bojanje će biti sljedeće: odaberemo neku boju α, te obojimo sve bridove u grafu R u tu boju, a sve ostale bridove u grafu G - u neke druge boje na bilo koji način (ako postoji samo jedan boja, tada se R poklapa s G pa nema problema). Dakle, riječi koje se sastoje od boje α "napreduju" vrhove R duž svojih stabala prema ciklusima, a zatim ih voze duž ciklusa. Samo takve riječi nam trebaju.

Neka je x bilo koji vrh maksimalne razine L u R, i neka je K bilo koja klika koja uključuje x; znamo da takva klika postoji. Može li K uključivati ​​neki drugi vrh maksimalne razine L? Prema našoj pretpostavci, svi takvi vrhovi su u istom stablu kao x, što znači da ih riječ α L vodi na isto mjesto kao x - naime, do korijena ovog stabla koji leži na ciklusu. Dakle, svi takvi vrhovi su prijatelji x i stoga ne mogu ležati u istoj kliki s njim. Stoga, osim x, K može uključivati ​​samo vrhove niže razine.

Pogledajmo skup A = Kα L-1 . Ovo je također klika iu njoj su svi vrhovi, osim x, dosegli neki od svojih ciklusa u R, jer svi vrhovi od A, osim x, imaju razinu nižu od L. Samo je x još uvijek izvan ciklusa, na udaljenosti od točno 1 do svog korijena na ciklusu. Sada uzmimo neki broj m koji je višekratnik svih duljina ciklusa u R - na primjer, umnožak svih duljina ciklusa. m ima takvo svojstvo da ako se vrh y nalazi na ciklusu u R, tada ga riječ α m vraća na njegovo mjesto: yα m = y. Pogledajmo kliku B = Aα m . Svi vrhovi od A, osim x, leže na ciklusima, i stoga ostaju tamo u B; a tek je x konačno ušao u svoj ciklus i nastanio se tu negdje. To znači da sjecište A i B sadrži sve vrhove A, osim jednog: |A| - |A∩B| = 1. Ali to samo znači, prema prethodnom odjeljku, da naše bojanje ima stabilan par, što je trebalo dokazati.

Izgradnja maksimalne razine.

Ostaje dokazati da je uvijek moguće odabrati razapinjući graf R na takav način da ima netrivijalnu maksimalnu razinu L > 0, a da svi vrhovi te razine leže na istom stablu.

Dio ovog dokaza je prilično dosadna i tehnička lema koju sam pročitao i testirao, ali neću je ponavljati, samo ću reći gdje je u članku za one koje zanima. Ali reći ću vam kako doći do ove leme.

Trebat će nam dva ograničenja koja možemo nametnuti grafu G. Prvo, kažemo da u G nema petlji, tj. bridovi od vrha do istog vrha. Poanta je da ako postoji petlja u grafu, tada je vrlo lako pronaći sinkronizirajuće bojanje na drugi način. Obojimo ovu petlju u neku boju α, a zatim ćemo, idući od tog vrha u suprotnom smjeru "kontra strelica", obojati bridove tako da boja α uvijek vodi do tog vrha. Budući da je graf povezan, to je lako urediti, a zatim petlja osigurava da će neka snaga α dovesti cijeli graf do ovog vrha.

Zatim, pretpostavimo na trenutak da iz nekog vrha p, svih d bridova vodi do istog vrha q. Ovo dopuštaju uvjeti, ali u ovom slučaju ćemo ovaj skup nazvati bridovima paket. Naše drugo ograničenje je sljedeće: ne postoji vrh r do kojeg vode dvije veze iz različitih vrhova p i q. Zašto ga možemo nametnuti? Jer ako postoje veze od p i q do r, tada će za bilo koje bojanje p,q konvergirati u vrh r nakon prve boje, i stoga su oni stabilni prijatelji. Dakle, u ovom slučaju, ne trebamo sve konstrukcije rasponskih grafova i klika, odmah dobivamo stabilne prijatelje. Stoga možemo pretpostaviti da to nije tako.

Konačno, dokažimo da uvijek postoji razapinjući graf R u kojem svi vrhovi ne leže na ciklusima, ali postoje neka netrivijalna stabla. Odaberemo neki R i pretpostavimo da svi vrhovi u njemu leže na ciklusima. Ako u grafu G svi bridovi leže u snopovima - tj. uvijek su svi d bridovi koji izlaze iz jednog vrha vodili do istog vrha - tada bi odabir R uključivao samo odabir jednog brida iz svakog snopa. U ovom slučaju, mogao bi postojati samo jedan ciklus u R (uostalom, nekoliko ciklusa u R ne bi moglo biti međusobno povezano u povezani graf G - svi bridovi G povezuju samo iste vrhove kao i bridovi R, jer ovi su ligamenti - a budući da je G povezan, to je nemoguće), a bilo koji ciklus u G jednostavno odabire druge bridove iz karika ovog ciklusa, ali zapravo je to isti ciklus, iste duljine. Ali to znači da su duljine svih ciklusa u G djeljive s ovom duljinom, što je upravo u suprotnosti s neperiodičnošću G. Stoga, ne može biti da u G svi bridovi leže na vezama, što znači da postoje neka dva brida p -- >q u R, a p-->s izvan R (trebalo nam je dugo raspravljanje o konektivima da dokažemo da neki brid iz p ne samo da ne leži u razapinjućem grafu, nego također vodi do drugog vrha s). Zatim zamijenimo p-->q s p-->s, a to će "prekinuti" ciklus, stvarajući neki netrivijalni rep u njemu. Ovaj rep će nam dati netrivijalno stablo u novom grafu.

Sada, od svih razapinjućih grafova R koji imaju netrivijalna stabla, možemo odabrati neki R koji ima maksimalan broj vrhova na ciklusima. T.e. ima vrhove koji nisu na ciklusima, ali osim ovog ograničenja, broj vrhova na ciklusima je maksimiziran. Ovaj graf ima neke vrhove maksimalne razine L, a možemo pretpostaviti da su na stablima koja vode do različitih korijena, inače smo već postigli ono što trebamo. Izaberemo jedan takav vrh x. Želimo promijeniti graf tako da ovaj vrh postane dio duže rute u stablu, dulje od L, a da se ostala stabla ne mijenjaju, i tada će maksimalna razina biti samo u jednom stablu, što je ono što smo željeti. Grafikon možete promijeniti na tri načina:

a) uzmite neki brid y-->x, i dodajte ga R, i odbacite brid y-->z koji tamo postoji;
b) uzeti brid b-->r, koji je tek zadnji na putu od x do njegovog ciklusa (r na ciklusu), i odbaciti ga, i dodati neki drugi b-->z.
c) uzmite rub c-->r, koji je dio ciklusa, i odbacite ga, te dodajte neki drugi c-->z.

Lema 7 Trachtmanova članka detaljno dokazuje da jedna (ili u nekom slučaju dvije) od ovih promjena dovode do željenog rezultata. Proces koristi i maksimalnost R (ako neka promjena vodi do grafa s većim brojem vrhova na ciklusima nego u R, to je u suprotnosti s njegovom maksimalnošću), i gore definirani uvjet da ne postoji vrh do kojeg vode dvije veze. Kao rezultat, u svakom slučaju, dobivamo graf R u kojem svi vrhovi maksimalne razine leže na jednom netrivijalnom stablu.

Ažuriranje, tjedan dana kasnije: usprkos tome, odlučio sam ovaj unos učiniti potpuno samodostatnim i također prepričati dokaz leme na koji sam se osvrnuo u prethodnom paragrafu. Bilo bi bolje to učiniti s dijagramom, ali ne želim ga crtati ili istrgnuti iz članka, pa ću pokušati riječima. Dakle, zamislimo da imamo razapinjući graf R, koji ima netrivijalna stabla, a od svih takvih grafova u njemu, najveći broj vrhova leži na ciklusima. Cilj nam je transformirati R u razapinjući graf u kojem svi vrhovi maksimalne razine leže na istom stablu; čim dobijemo takav graf u procesu isprobavanja, odmah završavamo (i nije nas briga što se maksimalni graf u smislu broja vrhova na ciklusima može izgubiti, to nam nije važno samo po sebi, koristimo ga samo u procesu). Neka je x vrh maksimalne razine L, T stablo na kojem ono leži, r vrh na ciklusu C gdje T završava, b-->r zadnji brid prije r na putu od x do ciklusa C. Možemo pretpostaviti da još ima nekih stabala koja se pridružuju ovom ciklusu ili drugih koja imaju vrhove razine L - inače je sve već učinjeno. Slijedi da ako uspijemo dobiti stablo iz T s elementom većeg stupnja od L, a ne produljiti ova druga stabla, onda smo gotovi.

Prvo, pokušajmo izvesti operaciju a) gore: uzmite neki rub y-->x u G - on postoji, jer graf je povezan i bez petlji, te ne leži u R, jer x maksimalna razina. Dodajmo to u R i izbacimo nešto y-->z koje je bilo prije. Ako y leži na stablu T, tada y-->x zatvara novi ciklus, au novom grafu više vrhova leži na ciklusima, a još uvijek postoje netrivijalna stabla (barem ona druga koja su bila u R), što je u suprotnosti s maksimalnošću R. Ako y ne leži na T, a y-->z nije dio ciklusa C, tada brisanje y-->z ne prekida ovaj ciklus, a dodavanje y-->x produljuje maksimalna razina stabla T za barem jedno, a ostala stabla se ne izdužuju, pa smo gotovi. Preostala opcija je kada y-->z leži na ciklusu C, koji je sada prekinut, i formiran je novi ciklus: od r do y, zatim y-->x, zatim od x do r duž prethodnog stabla. Duljina ovog ciklusa je l(ry)+1+L, dok je duljina starog ciklusa C bila l(ry)+1+l(zr). Novi ciklus ne može biti duži od starog, to je u suprotnosti s maksimalnošću R, pa vidimo da je L ≤ l(zr), tj. duljina trase od z do r u staroj petlji. S druge strane, u novom grafu, vrh z sada ima razinu od najmanje l(zr), a ako je ona veća od L, onda smo gotovi. Dakle, možemo pretpostaviti da je l(zr)=L. Da rezimiramo: pretpostavljamo da a) ne funkcionira, a onda znamo da y-->z leži na ciklusu C, l(zr) = L.

Sada pokušajmo s operacijom b): zamijenimo rub b-->r nekim drugim rubom b-->d. Pogledajmo gdje se nalazi novi vrh d. Ako je na stablu T, tada smo stvorili novi ciklus bez prekidanja prethodnog i opovrgli maksimalnost R. Ako je na drugom stablu, tada će najveći vrhovi od T, uključujući x, sada imati razinu veću od L, dok druga stabla neće i mi smo gotovi. Ako na drugom ciklusu, a ne C, tada ćemo sada učiniti a) zajedno s b) također a): budući da znamo da y-->z leži na C, tada će ova operacija prekinuti C, ali ne i novi ciklus na koji to je sada povezano stablo Τ, i ovo stablo će sada imati vrhove razine veće od L, i opet smo gotovi.

Preostala opcija je kada je b-->d također spojen na ciklus C, na nekom drugom mjestu osim r, ili na istom mjestu i tada d=r. Nakon što smo zamijenili b-->r sa b-->d, dobili smo istu situaciju kao i originalno - stablo T, čvor x razine L itd. - samo je stablo sada povezano s ciklusom kroz vrh d. Razmatrajući sada operaciju a), zaključujemo (pod pretpostavkom da ne radi) da je l(zd) = L, kao što smo ranije zaključili da je l(zr) = L. Ali ako je l(zd)=l( zr), tj. udaljenost duž ciklusa od z je ista do d i r, onda je ovo isti vrh: d=r. Dakle, ako b) ne radi, tada bilo koji rub iz b mora voditi do r, tj. rubovi od b tvore snop.

Konačno, razmotrite rub c-->r koji leži na ciklusu C. Budući da možemo pretpostaviti da svi bridovi iz b leže na poveznici koja vodi do r, također možemo nametnuti ograničenje spomenuto gore da ne mogu postojati dvije poveznice, što vodi do jedan vrh, ne vode svi bridovi od c do r, ali postoji neki brid c-->e. Zamijenimo c-->r sa c-->e. Gdje može ležati vrh e? Ne na stablu T, jer bi to "proširilo" ciklus C, što je u suprotnosti s maksimalnošću R. Dakle, e leži na drugom stablu, ili na drugom ciklusu, ili čak na istom ciklusu C, ali ne na vrhu r . Tada je stablo T, prije nego što se poveže s ciklusom, sada prošireno za barem jedan brid koji izlazi iz r, a možda i više (samo jedan ako e leži neposredno nakon r, a c--> e ponovno zatvara ciklus C, izvodeći iz njega samo r). To znači da je razina vrha x i ostalih maksimalnih vrhova T sada najmanje L + 1, a ostala stabla se nisu izdužila i opet imamo ono što nam treba.