Bojanka cesta. Bojanke saobraćajna pravila Stabilno prijateljstvo i uvod

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

Zahvaljujući Dizniju i Piksaru, u junu 2006. ceo svet je video crtani film u kome su samo automobili postali junaci.

Automobili u crtiću Automobili žive običnim životom - jedan drži prodavnicu guma, drugi tuning studio, a neki jednostavno žive za svoje zadovoljstvo, poput hipija Fillmorea (Volkswagen T1) ili njegovog prijatelja, veterana Drugog svjetskog rata. Serge (Willys). Glavni lik filma, McQueen, zvani "Munja", sanja samo o utrkama, pobjedama i slavi. Jednom u Distriktu radijatora na poznatom američkom autoputu 66, još uvijek "zeleni" McQueen odmah svima govori koliko je brz i kul. Međutim, njegov prvi start u NASCAR trci razbija njegove iluzije. Prijatelji pomažu heroju da preživi gubitak - stari šleper Mater (GMC Pick-up), mentor Dok Hadson (Hudson Hornet) i mali Luiđi (Fiat 600), koji sanja da vidi pravi Ferrari.

Pa, gdje bismo bili bez romantične ljepotice Sally (Porsche sa šarmantnom tetovažom 911)! U velikoj mjeri zahvaljujući njima, McQueen će ipak pobijediti u trci, pobijedivši Chicoovog glavnog rivala (Plymouth Hemi Cuda). Luiđijev san će se takođe ostvariti - jednog dana će u njegovu radnju da zameni gume doći „pastuh iz Maranela“, koga je, inače, izrazio sam „Crveni baron“, Mihael Šumaher.

Važno je napomenuti da su i kreatori filma i oni koji su ga oglašavali ljudi koji se bave automobilima. Na primjer, direktor Joe Lasseter proveo je gotovo cijelo djetinjstvo u Chevrolet fabrici, gdje je njegov otac bio jedan od glavnih dizajnera. Fordov vodeći dizajner Jay Mays bio je konsultant. Pored već pomenutog sedmostrukog svetskog šampiona Formule 1 Mihaela Šumahera, u oglašavanju likova učestvovali su i zvezde NASCAR-a Richard Petty i Paul Newman, kao i legendarni trkač Michael Andretti.

Korištena je samo originalna buka automobila - na primjer, posebno za trkačke epizode, zvuk je sniman nekoliko sedmica na američkim ovalima tokom NASCAR takmičenja. Bilo je potrebno više od dvije godine za stvaranje filma, čiji je budžet bio 70 miliona dolara. Za to vrijeme napravljeno je 43 hiljade različitih skica automobila, a svaki crtež trajao je više od 17 sati. U filmu je ukupno 120 likova iz automobila - od novih Porschea i Ferrarija do antiknog Forda T.

Poznavanje pravila djeteta saobraćaja- jedan od glavnih uslova njegove sigurnosti na ulici. Mnogi pješaci, uključujući i odrasle, ova pravila shvataju prilično olako, što često postaje uzrok saobraćajnih nesreća različite težine. Djeca moraju jasno shvatiti da su, kada su na ulici u naseljenom mjestu, punopravni sudionici u saobraćaju na putevima, pa je poštivanje saobraćajnih pravila njihova odgovornost.

Bojanke Saobraćajna pravila za djecu.

Učenje djeteta pravilima ponašanja na ulici (putevi, trotoari, gradski prijevoz) treba početi u samom rane godine, prije nego što nauči samostalno hodati i trčati. I ovdje je vrlo važan primjer roditelja i drugih odraslih sa kojima je dijete na ulici. Ne samo da svom djetetu morate reći i objasniti pravila puta, već ih i sami striktno poštovati. Stranice za bojanje sa prometnim pravilima predstavljene na ovoj stranici prvenstveno su namijenjene predškolskoj djeci i pomoći će djeci da nauče osnovne točke ponašanja na putu, ali i u blizini.

1. Stranica za bojanje Semafor.

Najbolje mjesto za bezbedno prelaženje puta je pešački prelaz opremljen semaforom. Stranice za bojanje sa slikama semafora također sadrže male rime koje pomažu djeci da lakše upamte pravila njihovog korištenja.

• Uvek počnite da vozite samo kada je zeleno svetlo na semaforu.
• Nikada nemojte prelaziti cestu kada je saobraćajna signalizacija crvena ili žuta, čak i ako u blizini nema vozila.
• Prilikom skretanja na zeleno svjetlo dodatno se uvjerite u svoju sigurnost – pogledajte lijevo, pa desno.

2. Bojanka pješački prijelaz.

Naučite svoje dijete da prelazi kolovoz samo na pješačkom prelazu. Bojanke pješačkih prelaza će naučiti djecu kako pravilno preći cestu. Prelaz koji nije opremljen semaforom naziva se neregulisanim.

• Pješački prelaz je na površini puta označen zebrom.
• Prije prelaska ceste pažljivo je pregledajte i uvjerite se da u blizini nema saobraćaja.
• Pređite cestu, ne pretrčavajte je.
• Ne prelazite ulicu dijagonalno.
• Obratite posebnu pažnju na vozila koja zaklanjaju pogled.
• Kada se krećete kroz pješački prelaz, prestanite razgovarati telefonom.
• Ako u blizini ima podzemnih ili nadvožnjaka, obavezno ih koristite jer je promet posebno intenzivan na takvim mjestima.

3. Trotoari.

Trotoar je predviđen za pješački saobraćaj. Naučite djecu da se pravilno ponašaju na trotoarima, posebno onima koji se nalaze u područjima sa gustim saobraćajem.

• Kada vozite trotoarom uz cestu, nemojte mu se previše približavati.
• Pažljivo pratite moguća izlazak vozila iz dvorišta i uličica.
• Ne igrajte loptom na trotoaru i ne trčite.

4. Bojanke sa pravilima ponašanja dece u gradskom prevozu i na autobuskim stanicama.

Ove stranice za bojanje će naučiti djecu kako da bezbedno koriste javni prevoz.

• Stajalište javnog prevoza opasno je mjesto zbog moguće loše vidljivosti na putu i velike gomile ljudi koja može slučajno izgurati dijete s trotoara na kolovoz. Ovdje morate biti posebno oprezni.
• Prilazite vratima vozila tek nakon što se potpuno zaustavila.
• Nakon što izađete iz vozila, nastavite prelaziti cestu tek nakon što ono napusti stajalište.

Osim ovih osnovnih saobraćajnih pravila, djecu će zanimati i bojanje putokaza. Predstavljene bojanke sa saobraćajnim pravilima pogodne su za mališane, predškolce i učenike osnovnih škola, kao i za upotrebu u vrtićima i nastavi u osnovnoj školi. Sve slike sa Saobraćajnim pravilima su potpuno besplatne - možete ih preuzeti i odštampati.

Nalazite se u kategoriji stranica za bojanje cesta. Bojanku koju razmatrate naši posjetioci opisuju na sljedeći način: "" Ovdje ćete pronaći mnogo stranica za bojanje na mreži. Možete preuzeti stranice za bojanje cesta i besplatno ih odštampati. Kao što znate, kreativne aktivnosti igraju veliku ulogu u razvoju djeteta. Oni aktiviraju mentalnu aktivnost, formiraju estetski ukus i usađuju ljubav prema umjetnosti. Razvija se proces bojenja slika na temu puta fine motoričke sposobnosti, upornost i tačnost, pomaže da saznamo više o svijetu oko nas, upoznaje nas sa svim raznovrsnim bojama i nijansama. Svakog dana na našu web stranicu dodajemo nove besplatne stranice za bojanje za dječake i djevojčice, koje možete obojiti online ili preuzeti i odštampati. Zgodan katalog, sastavljen po kategorijama, olakšat će pronalaženje željene slike, a veliki izbor bojanki omogućit će vam da svaki dan pronađete novu zanimljivu temu za bojanje.

Dječake možete dugo zaokupiti ako ih pozovete da se igraju s autićima u pješčaniku. Ali šta učiniti ako je napolju hladno i detetu je dosadno. U tom slučaju možete preuzeti i odštampati sljedeće šablone cesta za automobile. Zabava će početi izrezivanjem svih prstenova, skretanja i ravnih puteva. Iz ovih šablona dijete može napraviti cestu bilo kojeg oblika, samo se pobrinite da je odštampan potreban broj potrebnih A4 listova.

Preuzmite pravi put za automobile

Trebat će vam najviše ovih listova. Na A4 list papira postavili smo 3 puta koje treba odštampati i iseći. Pokažite svom djetetu kako seče cestu pod pravim uglom kako bi dionica bila potrebna.

Put za automobile: prsten

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

Put za automobile: pravo skretanje

Prikazani zavoji će omogućiti dječaku da skrene cestu za 90 stepeni, u smjeru koji mu je potreban.

Nema oštrog skretanja na cesti za automobile

Sljedeći A4 predložak će vam pomoći da skrenete cestu u bilo kojem radijusu.

(ovaj unos može biti od interesa za čitaoce sa znanjem matematike i simpatizere)

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

Problem se može objasniti sljedećim primjerom. Zamislite kartu grada na kojoj na svakoj raskrsnici možete ići u jednom od četiri smjera - sjever, jug, istok i zapad. Ako auto krene sa neke raskrsnice i prati neku listu uputstava - "sjever, sjever, istok" itd. - onda će na kraju stići na neku drugu raskrsnicu. Da li je moguće pronaći listu uputstava, možda dugačku, koja će odvesti mašinu na isto mesto bez obzira odakle počinje? Ako mapa izgleda kao Manhattan - obična mreža - onda ne, ali možda ima puno ćorsokaka i neočekivanih skretanja?

Ili drugi primjer. Vaš prijatelj je zapeo u lavirintu u kojem treba da pronađe centar, a on vas je nazvao tražeći pomoć. Znate kako funkcioniše lavirint, ali ne znate gdje je vaš prijatelj. Može li postojati niz naredbi koje će sigurno dovesti vašeg prijatelja u centar, gdje god da se nalazi?

U ova dva primjera, "pravci" u svakoj tački su fiksni, a rješenje ili postoji ili ne postoji. Ali općenito, ovaj problem postavlja pitanje: ako možemo odabrati gdje, na primjer, "zapad, sjever, istok, jug" različito pokazuju na svakom raskršću, možemo li tada osigurati postojanje "sinhronizirane riječi" - niza naredbi koje bilo koje mjesto će dovesti do jednog fiksnog?

U opštem slučaju, neka postoji usmeren graf G sa ivicama „strelice“ između vrhova. Neka ovaj graf ima uniforman izlazni stepen d - to znači da svaki vrh ima tačno d ivica. U tom slučaju se može unijeti svaki pojedinačni vrh različite količine, opciono d. Hajde da imamo skup d slova neke abecede, koje ćemo nazvati "boje". Tada se "boja" grafa daje tako što se svakom vrhu dodijele sva d slova za njegove d izlazne ivice. Dakle, ako se „nalazimo“ na nekom vrhu, i želimo da „idemo“ negdje prema boji α, tada će nam bojanje uvijek reći koju ivicu trebamo ići do kojeg novog vrha. “Riječ” je bilo koji niz slova-boja. Zatim, ako je u grafu data boja, a x je neki vrh, a w neka riječ, tada xw označava vrh do kojeg ćemo doći počevši od x i slijedeći riječ w.

Bojanka se zove sinhronizacija, ako postoji riječ w koja vodi bilo koji vrh x do jednog fiksnog vrha x 0 . U ovom slučaju se poziva w sinkronizirajuća riječ. Pitanje koje postavlja problem bojenja puta je: da li uvijek postoji sinkronizirajuće bojenje? Da li je uvijek moguće obojiti rubove grafa na način da se svi vrhovi mogu svesti na jedan?

Ovaj problem ima primjene u nekoliko različitih područja, o čemu se može pročitati na primjer na Wikipediji. Recimo, u informatici, u teoriji automata. Graf bojanja se može smatrati determinističkim konačnim automatom, u kojem su vrhovi stanja, a ivice pokazuju kako se kretati između njih. Pretpostavimo da kontrolišemo ovu mašinu na daljinu, šaljemo komande nekim informacionim kanalom, a zbog nekih kvarova ovaj kanal je kontaminiran, mašina je dobila neke pogrešne instrukcije, a sada ni ne znamo u kakvom je stanju. Zatim, ako postoji sinkronizirana riječ, možemo je dovesti u poznato stanje, bez obzira gdje se sada nalazi.

Dakle, kada postoji sinhronizovano bojenje? Pretpostavka o bojanju puta nameće još dva ograničenja grafu (osim činjenice da svaki vrh ima tačno d rubova). Prvo, graf mora biti snažno povezan - to znači da postoji ruta od bilo kojeg vrha do bilo kojeg drugog. Drugo, grafikon ne smije biti periodičan. Zamislimo da se svi vrhovi grafa mogu podijeliti na skupove V 1, V 2, ... V n, tako da bilo koja ivica grafa povezuje vrhove iz nekih Vi i Vi+1 ili V n i V 0. Ne postoje ivice između vrhova u svakom V, a ni oni ne mogu „skakati“ između bilo kojeg V, samo redom. Takav graf se naziva periodičnim. Jasno je da takav graf ne može imati sinkronizirajuću boju, jer bez obzira na to kako ga obojite i bez obzira koje riječi koristite, dva vrha u različitim V i nikada se neće spojiti – oni će nastaviti da hodaju u ciklusu.

Teorema o bojanju puta kaže da su ovi uslovi dovoljni: bilo koji neperiodični, snažno povezani usmjereni graf sa d ivicama iz svakog vrha ima sinkronizirajuću boju. Prvi put je formulisana kao hipoteza 1970. godine, a od tada je bilo mnogo djelomičnih 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 ekvivalentnim. Graf je periodičan ako i samo ako postoji broj N>1 kojim se dijeli dužina bilo kojeg ciklusa u grafu. One. naš zahtjev neperiodičnosti je ekvivalentan činjenici da ne postoji takvo N, ili drugim riječima, najveći zajednički djelitelj dužina svih ciklusa u grafu je 1. Dokazaćemo da svaki graf koji zadovoljava ovaj uvjet ima sinhronizovano bojenje.

Dokazivanje da je periodičnost ekvivalentna uslovu „postoji N>1 kojim je podeljena dužina bilo kog ciklusa“ je trivijalno u jednom pravcu i lako u drugom. Ako ste voljni ovo prihvatiti s vjerom, možete lako preskočiti ostatak ovog pasusa; to nije važno za ostatak dokaza. Ako je graf periodičan, tj. može podijeliti vrhove na skupove V 1, V 2, ... V n, tako da ivice idu između njih duž ciklusa, onda je očito da dužina svakog ciklusa mora biti djeljiva sa n, tj. novi uslov je zadovoljen. Ovo je trivijalan pravac, ali za našu zamenu treba nam samo drugi pravac. Pretpostavimo da postoji N>1, sa kojim se dijeli dužina bilo kojeg ciklusa. Napravimo neko usmjereno razapinjuće stablo u našem grafu s korijenom na vrhu r. Do bilo kojeg vrha x postoji ruta u ovom stablu počevši od korijena dužine l(x). Sada tvrdimo da za bilo koji rub p-->q u grafu vrijedi da je l(q) = l(p) + 1 (mod N). Ako je ova tvrdnja tačna, onda odmah slijedi da sve vrhove možemo podijeliti na skupove V i prema l(x) mod N, a graf će biti periodičan. Zašto je ova izjava tačna? Ako je p-->q dio razapinjućeg stabla, onda je to očito, jer je tada jednostavno l(q) = l(p) + 1. Ako to nije slučaj, onda pišemo rute od korijena r do vrhove p,q kao R p i Rq. Neka R r također označava rutu od q natrag do r u grafu (graf je povezan, pa postoji). Tada možemo napisati dva ciklusa: R p p-->q R r , i R q R r . Prema uslovu, dužine ovih ciklusa se dele sa N, oduzimanjem i smanjenjem ukupnih vrednosti dobijamo da je l(p)+1 = l(q) mod N, što je i trebalo dokazati.

Stabilno prijateljstvo i indukcija

Neka je data određena boja grafa G. Nazovimo dva vrhovi p,q prijatelja ako ih neka riječ w dovodi u isti vrh: pw = qw. Hajde da pozovemo p,q neprijatelji, ako se “nikada ne okupe”. 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š nekog w" može doći. Stabilni prijatelji nikada neće postati neprijatelji.

Relacija stabilnosti između vrhova je, prvo, ekvivalencija (on je refleksivna, simetrična i tranzitivna), a drugo očuvana strukturom grafa: ako su p, q stabilni prijatelji, p je povezan rubom sa p, q sa q ", a ove ivice iste boje, zatim p" i q" su takođe stabilni prijatelji. To znači da je stabilno prijateljstvo kongruencija i može se podijeliti sa: kreirajte novi graf G", čiji će vrhovi biti klase ekvivalencije za stabilno prijateljstvo u G. Ako postoji barem jedan stabilan par u G, onda će G" biti manji od G. Štaviše, ako u originalnom grafu G iz svakog vrha je imao d rubova, onda će u G" to biti slučaj. Na primjer, ako je P vrh novog grafa, što je klasa ekvivalencije originalnih vrhova p1, p2... , a α je bilo koja boja, tada ivice p1--α--> q1, p2---α-->q2, itd. vode do vrhova q1, q2..., koji su u stabilnom prijateljstvu sa svakim drugi, i stoga leže u jednom novom vrhu Q, tako da sve ove ivice postaju nova ivica P --α-->Q. I tako dalje za svaku od d boja.

Štaviše, ako je G bio neperiodičan, onda je i G" takav. Na kraju krajeva - koristeći našu alternativnu definiciju periodičnosti - bilo koji ciklus u G pretvara se u ciklus u G", pa ako su sve dužine ciklusa u G" deljivo sa n > 1, onda isto važi za sve cikluse u G. Dakle, periodičnost G" implicira periodičnost G.

Pretpostavimo da smo uspjeli pronaći sinhronizirajuću boju u G. Sada se može koristiti u G umjesto boje s kojom smo započeli: svaka ivica p-->q će dobiti nova boja prema novoj boji ruba P-->Q. Malo preciznije, trebalo bi reći ovo: svakom vrhu grafa G" novo je bojenje dato nekom permutacijom svih boja π P: ivica koja je bila obojena bojom α dobija novu boju π P (α) Zatim u originalnom grafu G na svakom vrhu p iz klase stabilnosti P koristimo istu permutaciju π P da promijenimo boje njegovih rubova. Novo bojenje grafa G, općenito govoreći, definira neke nove koncepte “prijateljstva”, “ neprijateljstvo" i "stabilnost", nisu identični originalnim. Ali ipak, ako su dva vrha p, q bila stabilni prijatelji u staroj boji - pripadali su istoj klasi P - onda će i u novoj ostati stabilni prijatelji. To je zato što se bilo koji niz w koji dovodi p, q u jedan vrh može "prevesti" iz stare boje u novu ili obrnuto, koristeći permutaciju π P na svakom vrhu p duž puta. Pošto su p, q stabilni u starom bojanju i ostati tako "svim putem", svaki srednji par vrhova p n , q n duž puta od p, q do zajedničkog vrha će biti stabilan, tj. ležati unutar jednog vrha P n i stoga će dobiti istu permutaciju π P n .

Novo bojenje se sinhronizuje za G", tj. neki niz w dovodi sve vrhove u jedan vrh P. Ako sada primenimo w na novo bojanje u G, onda će svi vrhovi konvergirati negde "unutar P". Kao što je gore navedeno, svi vrhovi unutar klase P ostaju stabilni u novom bojenju, što znači da sada možemo nastaviti w, iznova i iznova spajajući preostale još odvojene parove vrhova sve dok se sve ne konvergira u jedan vrh G. Dakle, novo bojenje je sinkronizirano za G.

Iz svega ovoga proizilazi da je za dokazivanje teoreme dovoljno dokazati da u svakom grafu koji ispunjava uslove postoji boja u kojoj postoji par stabilnih prijatelja. Jer onda se sa grafa G može preći na graf G" manjih dimenzija, a takođe ispunjava sve uslove. Koristeći induktivni argument, može se pretpostaviti da je za manje grafove problem već riješen, a zatim će sinkronizirajuće bojenje za G" također biti sinkronizirano za G.

Klike i maksimalni skupovi

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

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

Ako je A klika, onda je za bilo koju riječ w Aw također klika; ovo je jasno jer neprijatelji ostaju neprijatelji. Ako je x bilo koji vrh grafa, onda postoji klika koja uključuje x. Ovo proizilazi iz činjenice da postoji neka vrsta klika A (vidi prethodni paragraf); ako je p vrh u njemu, onda postoji riječ w koja vodi od p do x, jer povezani graf; onda je Aw klika koja uključuje x.

Klikovi će nam pomoći da dokažemo da postoji bojanje sa stabilnim prijateljima - prema prethodnom odjeljku, ovo je dovoljno za dokazivanje teoreme. U ovom dijelu ćemo dokazati da ako postoje dvije klike A i B, takve da su svi vrhovi u njima zajednički osim jednog u A i jednog u B, onda su ova dva vrha stabilni prijatelji. Dakle, problem se svodi na pronalaženje boje koja sadrži klikove A i B.

Da biste bolje razumjeli kako funkcionišu klike, 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 zbroji težine svih vrhova iz kojih postoje bridovi u x, tada dobijamo d*w(x), gdje je d broj ivica iz svakog vrha. Ovo proizilazi iz linearne algebre, i ako ne znate šta je vlastita vrijednost, preskočite ostatak ovog pasusa i uzmite postojanje takvog w(x) zdravo za gotovo. Ako je M matrica grafa G (ćelija (i,j) je 1 ako postoji ivica i-->j, i 0 ako takva ivica ne postoji), onda w(x), kako sam ih opisao, su elementi svojstvenog vektora lijevo ova matrica ima za svojstvenu vrijednost d. Znamo da takav vektor postoji jer je d svojstvena vrijednost: ima trivijalni svojstveni vektor desno(1,1,....1) - ovo odmah proizilazi iz činjenice da tačno d ivica izlazi iz svakog temena.

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

Razmotrimo sada sve skupove vrhova koji se mogu dovesti zajedno u jednu tačku, tj. takav A da za neki w Aw sadrži samo jedan vrh. Oni skupovi A koji među svim takvim skupovima imaju maksimalnu težinu w(A) zvaćemo se maksimalnim skupovima. Ako je bojanje sinkronizirano, onda je cijeli graf G maksimalan skup (jedinstven), ali inače nije.

Ako je A bilo koji skup vrhova, onda je zbir svih w(Aα -1), pri čemu α prolazi preko svih d boja, jednak d*w(A) - ovo je jednostavno generalizacija glavnog svojstva težine iz jedan vrh na skup vrhova A. Ako je, pored toga, u ovom slučaju A maksimalan skup, onda svaki od w(Aα -1) ne može biti veći od w(A), jer su i ti skupovi svedeni na jedan vrh . A pošto je zbir d ovih težina jednak d*w(A), ispada da je svaki od njih jednak w(A), a svi ovi skupovi su takođe maksimalni. Odmah slijedi 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 , disjunktnih u parovima i svedenih na pojedinačne vrhove a 1 ...a n istom riječju w (u početnom slučaju bit će n=1 i samo jedan postavljen, tako da je lako pokrenuti). Jasno je da su svi a 1 ...a n međusobno različiti, jer bi inače bilo moguće dodatno proširiti maksimalni skup zbog elemenata drugog sa istim konačnim vrhom. Pretpostavimo da svi A i zajedno još nisu iscrpili sve vrhove G, i neka je x vrh izvan svih A i . Pošto je graf povezan, postoji neki put h od a 1 do x. Tada n maksimalnih skupova A i h -1 w -1 ide prema riječi whw do konačnih vrhova a 1 ...a n , a maksimalni skup A 1 ide u neki vrh Awhw = (Aw)hw = (a 1 h) w = xw. Ovaj vrh xw također se mora razlikovati od svih a 1 ...a n , jer bi inače maksimalni skup A i mogao biti dopunjen elementom x. A pošto svi ovi n+1 skupovi - svi A i h -1 w -1 plus A 1 - idu duž whw do različitih vrhova, svi su parno disjunktni. Nastavit ćemo ovo proširenje sve dok ne ostane nijedan vrh izvan skupa.

Dakle, možemo pokriti cijeli graf G disjunktnim maksimalnim skupovima. Pošto su maksimalni, svi imaju isti cijeli w max , pa je stoga njihov broj u pokrivenosti N max = w(G)/w max .

Sada razmotrite bilo koji skup A koji se sastoji od neprijatelja u paru. Na primjer, klika je primjer takvog skupa (i također ima oblik Gw). Maksimalni skup ne može sadržavati par neprijatelja, jer tada ne bi mogao konvergirati. To znači da u pokrivanju od N maksimalnih skupova svaki sadrži najviše jedan član A, tako da je veličina A najviše N max. Konkretno, to je gornja granica veličine bilo koje klike.

Neka je A klika oblika Gw, gdje je w neka riječ. Tada je G = Aw -1, i prema tome w(G) je jednak zbiru w(aw -1), pri čemu a prolazi kroz sve vrhove A. Broj članova, prema prethodnom paragrafu, nije veći od N max, a svaki skup aw -1 se može svesti na jednu tačku (u tački a sa riječju w), tako da njegova težina nije veća od maksimalnog w max . Pošto je cijela suma jednaka w(G) = N max *w max , zaključujemo da je broj članova tačno jednak N max , a svaki član je tačno jednak w max . Dokazali smo da sve klike imaju istu veličinu: tačno N max elemenata.

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

Pošto su A i B iste veličine, 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 ovi vrhovi p,q stabilni prijatelji. Ako to nije tako, onda ih neka riječ w čini neprijateljima, tj. pw i qw su neprijatelji. Kao što je gore prikazano, Aw i Bw su također klike, i očito je da opet imaju sve zajedničke elemente, osim neprijatelja pw i qw. Tada je skup Aw ∪ Bw skup neprijatelja u paru. Zaista, u njemu su svi elementi Aw u paru neprijatelji, jer je to klika; isto važi i za Bw elemente; a ostao je samo par pw,qw - takođe neprijatelji. 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 nijednog w. Drugim riječima, p i q su stabilni prijatelji.

Proširujući grafovi i klike

Uzmimo sve vrhove iz datog grafa G, i izaberemo samo jedan izlazni rub iz svakog vrha. Ovaj izbor određuje podgraf, koji nazivamo rasponski graf(spanding graph). Može postojati mnogo različitih dijagrama, ali hajde da razmislimo malo o tome kako oni izgledaju. Neka postoji određeni rasponski graf R. Ako uzmemo bilo koji vrh x u njemu i počnemo pratiti njegove rubove, tada ćemo svaki put imati jedan izbor, jer u R postoji samo jedna ivica koja izlazi iz svakog vrha, a prije ili kasnije ćemo zatvoriti ciklus. Možda se ovaj ciklus neće zatvoriti na x, ali će se zatvoriti negdje "dalje" - na primjer, x-->y-->z-->s-->y. Tada će "rep" do ovog ciklusa voditi od x. Ako krenemo od nekog drugog vrha, također ćemo sigurno završiti sa ciklusom - ovim ili nekim drugim. Ispostavilo se da bilo koji vrh 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 i određeni broj "obrnutih" stabala se gradi na njima: svako stablo ne počinje, već se završava u "korijenu", koji leži na jednom od ciklusa.

Možemo dodijeliti svakom vrhu grafa nivo, što odgovara njegovoj udaljenosti do ciklusa u datom rasponskom grafu R. Vrhovi koji leže na ciklusu imaju nivo 0, a vrhovi koji leže na stablu vezanom za ciklus dobijaju nivo jednak udaljenosti u njihovom stablu do „korena ” ležeći na biciklu. Neki vrhovi našeg grafa imaju maksimalni nivo L. Možda je čak jednak 0 - tj. nema drveća, samo ciklusi. Možda je veći od nule, a vrhovi ovog maksimalnog nivoa leže na svim vrstama različitih stabala, povezanih sa različitim ciklusima ili sa jednim.

Želimo odabrati rasponski graf R takav da svi vrhovi maksimalnog nivoa leže na istom stablu. Intuitivno bi se moglo vjerovati da se to može učiniti, jer ako nije - na primjer, rasuti su po različita stabla- tada možete odabrati jedan od ovih maksimalnih vrhova x i povećati njegov nivo pričvršćivanjem na R neki rub koji ide na x. Onda će se morati izbaciti neko drugo rebro, i nije činjenica da ovo neće naškoditi nečemu drugom... ali ovo je tehničko pitanje, o čemu će biti reči kasnije. Samo pokušavam da kažem da to intuitivno ne izgleda baš komplikovano.

Za sada, pretpostavimo da možemo izabrati R tako da svi vrhovi maksimalnog nivoa leže na istom stablu. Pretpostavlja se da je ovo drvo netrivijalno, tj. maksimalni nivo L > 0. Na osnovu ove pretpostavke konstruisaćemo bojanje u kome se nalaze klike A i B koje ispunjavaju uslove iz prethodnog odeljka, a to će dokazati da u ovom bojanju postoji stabilan par prijatelji.

Bojenje će biti sljedeće: odaberite neku boju α i obojite sve rubove u grafu R ovom bojom, a sve ostale ivice u grafu G nekim drugim bojama na bilo koji način (ako postoji samo jedna boja, onda R poklapa se sa G, tako da nema problema). Dakle, riječi koje se sastoje od boje α "guraju" vrhove R duž svojih stabala prema ciklusima, a zatim ih voze kroz cikluse. Ovo su jedine riječi koje će nam trebati.

Neka je x bilo koji vrh maksimalnog nivoa L u R, i neka je K bilo koja klika uključujući x; znamo da takva klika postoji. Može li K uključiti neki drugi vrh maksimalnog nivoa L? Prema našoj pretpostavci, svi takvi vrhovi se nalaze u istom stablu kao i x, što znači da ih riječ α L vodi na isto mjesto kao i x – odnosno u korijen ovog stabla koji leži na ciklusu. To znači da su svi takvi vrhovi prijatelji x i stoga ne mogu ležati u istoj kliki kao i on. Stoga, osim x, K može uključivati ​​samo vrhove nižeg nivoa.

Pogledajmo skup A = Kα L-1. Ovo je takođe klika iu njoj su svi vrhovi, osim x, dostigli neku vrstu ciklusa u R, jer svi vrhovi A, osim x, imaju nivo manji od L. Samo x ostaje izvan ciklusa, na udaljenost od tačno 1 do njegovog korijena u ciklusu. Sada uzmimo neki broj m koji je višekratnik svih dužina ciklusa u R - na primjer, proizvod svih dužina ciklusa. m ima takvu osobinu da ako je vrh y na ciklusu u R, onda ga riječ α m vraća na njegovo mjesto: yα m = y. Pogledajmo kliku B = Aα m . Svi vrhovi A, osim x, leže na ciklusima, i stoga ostaju tamo u B; i samo je x konačno ušao u svoj ciklus i tu se negdje skrasio. To znači da presjek A i B sadrži sve vrhove A osim jednog: |A| - |A∩B| = 1. Ali ovo samo znači, prema prethodnom odeljku, da naše bojenje ima stabilan par, što smo morali da dokažemo.

Izgradnja maksimalnog nivoa.

Ostaje dokazati da je uvijek moguće odabrati razmjenski graf R takav da ima netrivijalni maksimalni nivo L > 0, a svi vrhovi ovog nivoa leže na istom stablu.

Dio ovog dokaza je prilično dosadna i tehnička lema, koju sam pročitao i provjerio, ali neću je ponavljati, samo ću reći gdje se nalazi 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, recimo da G nema petlje, tj. ivice od vrha do istog vrha. Poenta je da ako postoji petlja u grafu, onda je vrlo lako pronaći sinkronizirajuću boju na drugi način. Obojimo ovu petlju nekom bojom α, a zatim, idući od ovog vrha u suprotnom smjeru "nasuprot strelicama", obojimo ivice tako da boja α uvijek vodi do ovog vrha. Pošto je graf povezan, ovo je lako urediti, a onda petlja osigurava da će neki stepen α svesti cijeli graf na ovaj vrh.

Zatim, pretpostavimo na sekundu da iz nekog vrha p sve d ivice vode do istog vrha q. Ovo dozvoljavaju uslovi, ali u ovom slučaju ćemo nazvati ovaj skup ivica hrpa. Naše drugo ograničenje je ovo: ne postoji vrh r do kojeg vode dvije veze iz različitih vrhova p i q. Zašto to možemo nametnuti? Jer ako iz p i q postoje veze u r, onda za bilo koje p,q bojanjeće konvergirati na vrhu r nakon prve boje, i stoga su stabilni prijatelji. Dakle, u ovom slučaju nam nije potrebna sva konstrukcija rasponskih grafova i klika, odmah dobijamo stabilne prijatelje. Stoga možemo pretpostaviti da to nije slučaj.

Konačno, dokazujemo da uvijek postoji rasponski graf R u kojem ne leže svi vrhovi na ciklusima, ali postoje neka netrivijalna stabla. Odaberimo neki R i pretpostavimo da svi njegovi vrhovi leže na ciklusima. Kada bi svi rubovi u grafu G bili povezani, tj. uvijek sve d ivice koje napuštaju isti vrh vode do istog vrha - tada bi izbor R uključivao samo odabir jedne ivice iz svake veze. U ovom slučaju, može postojati samo jedan ciklus u R (na kraju krajeva, nekoliko ciklusa u R ne bi se nikako moglo povezati jedan s drugim u povezanom grafu G - svi rubovi G povezuju samo iste vrhove kao i rubovi R, jer se radi o konektivima - a pošto je G povezano, to je nemoguće), i bilo koji ciklus u G jednostavno bira druge ivice iz veza ovog ciklusa, ali u suštini to je isti ciklus, iste dužine. Ali to znači da su dužine svih ciklusa u G djeljive ovom dužinom, što je upravo u suprotnosti s neperiodičnošću G. Prema tome, ne može biti da svi bridovi u G leže na vezama, što znači da postoje neka dva ruba p-- >q u R, i p-->s izvan R (trebao nam je dugačak argument o konektivima da bismo dokazali da neka ivica iz p ne samo da ne leži u rasponskom grafu, već takođe vodi do drugog temena s). Zatim zamjenjujemo p-->q sa p-->s, i to će "prekinuti" ciklus, stvarajući u njemu neku vrstu ne-trivijalnog repa. Ovaj rep će nam dati netrivijalno stablo u novom grafu.

Sada možemo izabrati između svih grafova R koji sadrže netrivijalna stabla neki R koji ima maksimalan broj vrhova na ciklusima. To je ima vrhove koji nisu na ciklusima, ali pored ovog ograničenja, broj vrhova na ciklusima je maksimiziran. U ovom grafu postoje neki vrhovi maksimalnog nivoa L i možemo pretpostaviti da se nalaze na stablima koje vode do različitih korijena, inače smo već postigli ono što nam je potrebno. Odaberimo jedan takav vrh x. Želimo promijeniti graf tako da ovaj vrh postane dio duže rute u stablu, dužeg od L, a ostala stabla se ne mijenjaju, i tada će maksimalni nivo biti samo u jednom stablu, što i želimo. Grafikon možete promijeniti na tri načina:

a) uzmite neku ivicu y-->x i dodajte je u R, i odbacite postojeću ivicu y-->z;
b) uzmite ivicu b-->r, koja je tacno posljednja na putu od x do njegovog ciklusa (r na ciklusu), i bacite je i dodajte jos neki b-->z.
c) uzmite ivicu c-->r, koja je dio ciklusa, i odbacite je, i dodajte neki drugi c-->z.

Lema 7 Trakhtmanovog rada dokazuje u detalje da jedna (ili u nekom slučaju dvije) od ovih promjena vodi do željenog rezultata. Proces koristi kako 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), tako i uvjet definiran gore da ne postoji vrh do kojeg vode dvije veze. Kao rezultat, u svakom slučaju, dobijamo graf R u kojem svi vrhovi maksimalnog nivoa leže na jednom netrivijalnom stablu.

Ažuriranje, nedelju dana kasnije: Ipak sam odlučio da ovaj unos učinim potpuno samodovoljnim i da ponovim dokaz leme na koju sam se osvrnuo u prethodnom pasusu. Bilo bi bolje da to uradim sa dijagramom, ali ne želim da ga crtam ili iščupam iz članka, pa ću pokušati sa rečima. Dakle, zamislite da imamo rasponski graf R, u kojem postoje netrivijalna stabla, i svih takvih grafova u njemu maksimalni iznos vrhovi leže na ciklusima. Cilj nam je da transformiramo R u graf u kojem svi vrhovi maksimalnog nivoa leže na istom stablu; Čim dobijemo takav graf u procesu pokušaja, odmah završavamo (i nije nas briga što se može izgubiti maksimalnost grafa u smislu broja vrhova na ciklusima, to nam nije važno u koristimo ga samo u procesu). Neka je x vrh maksimalnog nivoa L, T drvo na kojem leži, r vrh na ciklusu C gdje se završava T, b-->r posljednja ivica prije r na putu od x do ciklusa C. Možemo pretpostaviti da postoje neka druga stabla koja se pridružuju ovom ciklusu ili druga koja imaju vrhove nivoa L - inače je sve već urađeno. Iz toga slijedi da ako iz T možemo dobiti stablo sa elementom većeg stepena od L, a ne proširiti ova druga stabla, onda smo gotovi.

Prvo, pokušajmo da izvršimo operaciju a) iznad: uzmimo neku ivicu y-->x u G - ona postoji, jer Graf je povezan i bez petlji, i ne leži u R, jer x maksimalni nivo. Dodajmo ga u R, i izbacimo neke y-->z koje su bile tamo prije. Ako y leži na stablu T, onda y-->x zatvara novi ciklus, a u novom grafu više vrhova leži na ciklusima, a još uvijek postoje netrivijalna stabla (barem ona druga koja su bila u R), koja je u suprotnosti sa maksimalnošću R. Ako y ne leži na T i y-->z nije dio ciklusa C, tada uklanjanje y-->z ne prekida ovaj ciklus, ali dodavanje y-->x produžava maksimum nivo stabla T za najmanje jedan, a ostali se stabla ne izdužuju, tako da smo gotovi. Ostaje opcija kada y-->z leži na ciklusu C, koji je sada prekinut, i formira se novi ciklus: od r do y, zatim y-->x, pa od x do r duž nekadašnje drvo. Dužina ovog ciklusa je l(ry)+1+L, a dužina starog ciklusa C je bila l(ry)+1+l(zr). Novi ciklus ne može biti duži od starog, to je u suprotnosti sa maksimalnošću R, pa vidimo da je L ≤ l(zr), tj. dužina rute od z do r u staroj petlji. S druge strane, u novom grafu, vrh z sada ima nivo od najmanje l(zr), a ako je ovo veće od L, onda smo gotovi. Dakle, možemo pretpostaviti da je l(zr)=L. Da rezimiramo: pretpostavljamo da a) ne radi, a onda znamo da y-->z leži na ciklusu C, l(zr) = L.

Pokušajmo sada operaciju b): zamijenimo rub b-->r nekom drugom ivicom b-->d. Pogledajmo gdje se nalazi novi vrh d. Ako na stablu T, onda smo kreirali novi ciklus bez prekidanja prethodnog i opovrgli maksimalnost R. Ako je na drugom stablu, tada će maksimalni vrhovi T, uključujući x, sada imati nivo veći od L, i ostala stabla neće, i gotovi smo. Ako na drugom ciklusu, a ne C, onda ćemo sada uraditi, zajedno sa b) također a): pošto znamo da y-->z leži na C, tada će ova operacija podijeliti C, ali ne i novi ciklus na koji je je sada povezano stablo T, i na ovom stablu će sada biti vrhova nivoa većeg od L, i opet smo gotovi.

Preostala opcija je kada je b-->d također povezan sa ciklusom C, na nekom drugom mjestu osim r, ili na istom mjestu i tada d=r. Nakon što smo b-->r zamenili sa b-->d, dobili smo istu situaciju kao na početku - stablo T, vrh x nivoa L, itd. - samo je stablo sada povezano sa ciklusom kroz vrh d. Razmatrajući sada operaciju a), zaključujemo (pod pretpostavkom da ne radi) da je l(zd) = L, kao što smo prethodno zaključili da je l(zr) = L. Ali ako je l(zd) = l(zr), tj. rastojanje duž ciklusa od z je isto do d i r, onda je ovo isti vrh: d=r. Dakle, ako b) ne radi, onda bilo koja ivica iz b mora voditi do r, tj. ivice iz b formiraju vezu.

Konačno, uzmite u obzir rub c-->r koji leži na ciklusu C. Pošto možemo pretpostaviti da svi rubovi iz b leže na vezi koja vodi do r, također možemo nametnuti gore spomenuto ograničenje da ne mogu postojati dvije veze koje vode do jedan vrh, ne vode sve ivice iz c u r, ali postoji neka ivica c-->e. Zamenimo 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 sa maksimalnošću R. Dakle, e leži na drugom stablu ili na drugom ciklusu, ili čak na istom ciklusu C, ali ne u vrhu r. Tada je stablo T, prije nego što se pridruži petlji, sada produženo za barem jedan rub koji izlazi iz r, a možda i za više (samo za jedan ako e leži odmah iza r, a c-->e ponovo zatvara petlju C, izvodeći samo r iz njega). To znači da vrh x i ostali maksimalni vrhovi T sada imaju nivo ne manji od L+1, a druga stabla se nisu izdužila i opet smo dobili ono što nam je potrebno.