Värityskirjan tie. Lataa suora tie autoille

(tämä artikkeli saattaa kiinnostaa matematiikan tuntevia lukijoita ja myötätuntoisia)

Toissapäivänä luin mielenkiintoisesta ongelmasta graafiteoriasta - tienväritysoletuksesta. Tämä olettamus on ollut avoin 37 vuotta, mutta kolme vuotta sitten israelilainen matemaatikko Abraham Trachtman todisti sen. Todistus osoittautui varsin alkeelliseksi, ja joillain vaikeuksilla (kun aivoni olivat surkastuneet) pystyin lukemaan ja ymmärtämään sen, ja yritän jopa selittää sen tässä postauksessa.

Ongelma voidaan selittää seuraavalla esimerkillä. Kuvittele kaupunkikartta, jonka jokaisessa risteyksessä voit mennä yhteen neljästä suunnasta - pohjoiseen, etelään, itään ja länteen. Jos auto lähtee jostain risteyksestä ja seuraa jotain ohjelistaa - "pohjoinen, pohjoinen, itä" jne. - sitten hän lopulta saapuu johonkin toiseen risteykseen. Onko mahdollista löytää luettelo, mahdollisesti pitkä, joka johtaa koneen samaan paikkaan riippumatta siitä, mistä se lähtee? Jos kartta näyttää Manhattanilta - tavalliselta ruudukolta - niin ei, mutta ehkä siinä on paljon umpikujia ja odottamattomia käänteitä?

Tai toinen esimerkki. Ystäväsi on juuttunut sokkeloon, jossa hänen on löydettävä keskus, ja hän soitti sinulle pyytääkseen apua. Tiedät kuinka sokkelo toimii, mutta et tiedä missä ystäväsi on. Voisiko olla olemassa joukko komentoja, jotka varmasti tuovat ystäväsi keskelle, missä tahansa hän on?

Näissä kahdessa esimerkissä kunkin pisteen "suunnat" ovat kiinteät, ja ratkaisu joko on olemassa tai ei. Mutta yleisemmin tämä ongelma kysyy: jos voimme valita, missä esimerkiksi "länsi, pohjoinen, itä, etelä" osoittaa kussakin risteyksessä eri tavalla, voimmeko sitten varmistaa "synkronointisanan" olemassaolon - komentosarjan, joka mikä tahansa paikka johtaa yhteen kiinteään?

Yleisessä tapauksessa olkoon suunnattu graafi G, jonka kärkien välissä on "nuoli"-reunat. Olkoon tällä graafilla tasainen ulkoaste d - tämä tarkoittaa, että jokaisella kärjellä on täsmälleen d reunaa. Tässä tapauksessa jokaiseen yksittäiseen kärkeen voi syöttää eri numero, ei välttämättä d. Olkaamme jonkin aakkoston d-kirjaimia, joita kutsumme ”väreiksi”. Sitten graafin ”väritys” saadaan antamalla kullekin kärjelle kaikki d kirjainta sen d lähtevästä reunasta. Joten jos "olemme" jossain kärjessä ja haluamme "mennä" jonnekin värin α mukaan, väritys kertoo aina, mihin reunaan meidän täytyy mennä mihinkin uuteen kärkeen. "Sana" on mikä tahansa kirjain-värisarja. Sitten, jos graafissa on annettu väritys ja x on jokin kärkipiste ja w on jokin sana, niin xw tarkoittaa kärkeä, johon päästään alkaen x:stä ja sanan w jälkeen.

Värityskirja on ns synkronoidaan, jos on sana w, joka johtaa minkä tahansa kärjen x yhteen kiinteään kärkeen x 0 . Tässä tapauksessa w:tä kutsutaan synkronoitava sana. Tienvärjäysongelman esittämä kysymys kuuluu: onko aina synkronoitava väritys? Onko aina mahdollista värittää graafin reunat siten, että kaikki kärjet voidaan pelkistää yhdeksi?

Tällä ongelmalla on sovelluksia useilla eri aloilla, joista voi lukea esimerkiksi Wikipediasta. Oletetaan, että tietojenkäsittelytieteessä, automaatioteoriassa. Väritysgraafia voidaan pitää deterministisenä äärellisenä automaattina, jossa kärjet ovat tiloja ja reunat osoittavat kuinka niiden välillä liikkuu. Oletetaan, että ohjaamme tätä konetta etäältä lähettämällä komentoja jonkin tietokanavan kautta, ja joidenkin vikojen takia tämä kanava oli saastunut, kone sai virheellisiä ohjeita, ja nyt emme edes tiedä missä tilassa se on. Sitten, jos synkronointisana on, voimme viedä sen tunnettuun tilaan riippumatta siitä, missä se on nyt.

Joten milloin synkronointivärjäys on olemassa? Tienvärjäysoletus asettaa graafille vielä kaksi rajoitusta (paitsi, että jokaisessa kärjessä on täsmälleen d reunaa). Ensinnäkin graafin on oltava vahvasti yhdistetty - tämä tarkoittaa, että mistä tahansa kärjestä on reitti mihin tahansa. Toiseksi kaavio ei saa olla jaksollinen. Kuvitellaan, että graafin kaikki kärjet voidaan jakaa joukoiksi V 1, V 2, ... V n, niin että mikä tahansa graafin reuna yhdistää pisteitä jostain Vi ja Vi+1 tai V n ja V 0. Jokaisen V:n kärkien välillä ei ole kulmia, eivätkä ne myöskään voi "hyppää" minkään V:n välillä, vain järjestyksessä. Tällaista kuvaajaa kutsutaan jaksolliseksi. On selvää, että sellaisella graafilla ei voi olla synkronoivaa väritystä, koska riippumatta siitä, kuinka värität sen ja mitä sanoja käytät, kaksi eri V i:n kärkeä eivät koskaan tule yhteen - ne jatkavat kävelyä syklissä.

Tienvärjäyslause sanoo, että nämä ehdot ovat riittävät: mikä tahansa ei-jaksollinen, vahvasti yhdistetty suunnattu graafi, jossa on d reunaa kustakin kärjestä, on synkronoitava väritys. Se muotoiltiin hypoteesiksi ensimmäisen kerran vuonna 1970, ja sen jälkeen on saatu monia osittaisia ​​tuloksia, jotka osoittavat erityistapauksia, mutta täydellinen todiste ilmestyi vasta vuonna 2007. Seuraavaksi kerron uudelleen lähes koko todistuksen (paitsi yksi tekninen lemma).

Jaksoisuus

Ensinnäkin korvataan ei-jaksollisuusehto toisella vastaavalla. Graafi on jaksollinen silloin ja vain, jos on olemassa luku N>1, jolla minkä tahansa kaavion jakson pituus jaetaan. Nuo. ei-jaksollisuusvaatimuksemme vastaa sitä tosiasiaa, että sellaista N:ää ei ole, tai toisin sanoen kaavion kaikkien syklien pituuksien suurin yhteinen jakaja on 1. Osoitamme, että millä tahansa graafilla, joka täyttää tämän ehdon, on värityksen synkronointi.

Todistaminen, että jaksollisuus vastaa ehtoa "on N>1, jolla minkä tahansa jakson pituus on jaettu" on triviaali yhdessä suunnassa ja helppo toisessa. Jos olet valmis ottamaan tämän uskon varassa, voit helposti ohittaa tämän kappaleen loput; sillä ei ole väliä muun todistuksen kannalta. Jos kuvaaja on jaksollinen, ts. voi jakaa kärjet joukoiksi V 1, V 2, ... V n niin, että reunat menevät niiden väliin sykliä pitkin, silloin on selvää, että minkä tahansa syklin pituuden on oltava jaollinen n:llä, ts. uusi ehto täyttyy. Tämä on triviaali suunta, mutta korvaamiseen tarvitsemme vain toisen suunnan. Oletetaan, että on N>1, jolla minkä tahansa jakson pituus jaetaan. Rakennetaan jokin suunnattu virittävä puu graafiimme, jonka juuri on kärjessä r. Mihin tahansa kärkeen x tässä puussa on reitti, joka alkaa pituuden l(x) juuresta. Väitetään nyt, että mille tahansa graafin reunalle p-->q pätee, että l(q) = l(p) + 1 (mod N). Jos tämä väite on tosi, niin siitä seuraa välittömästi, että voimme jakaa kaikki kärjet joukoiksi V i l(x) mod N:n mukaan, jolloin graafista tulee jaksollinen. Miksi tämä väite on totta? Jos p-->q on osa virittävää puuta, niin tämä on ilmeistä, koska silloin yksinkertaisesti l(q) = l(p) + 1. Jos näin ei ole, kirjoitetaan reitit juuresta r kärjet p,q ovat R p ja Rq. Olkoon myös R r kaaviossa reittiä q:sta takaisin r:ään (kuvaaja on yhdistetty, joten se on olemassa). Sitten voidaan kirjoittaa kaksi sykliä: R p p-->q R r ja R q R r . Ehdon mukaan näiden syklien pituudet jaettuna N:llä vähentämällä ja vähentämällä kokonaisarvot saadaan, että l(p)+1 = l(q) mod N, mikä oli todistettava.

Vakaa ystävyys ja perehtyminen

Olkoon graafin G tietty väritys. Kutsukaamme kahta kärkeä p, q ystäviksi, jos jokin sana w tuo ne samaan kärkeen: pw = qw. Kutsutaan p,q vihollisiksi, jos ne "eivät koskaan tapaa". Kutsutaan p,q:ta stabiileiksi ystäviksi, jos minkä tahansa sanan w suorittamisen jälkeen he pysyvät ystävinä: pw ei ehkä tule samaan kärkeen kuin qw, mutta muutaman lisää w":n jälkeen se voi tulla. Vakaista ystävistä ei koskaan tule vihollisia.

Piikkien välinen stabiilisuussuhde on ensinnäkin ekvivalenssi (se on refleksiivinen, symmetrinen ja transitiivinen) ja toiseksi säilyy graafin rakenteen avulla: jos p, q ovat stabiileja ystäviä, p on yhdistetty reunalla p:hen, q q:hen. ", ja nämä reunat ovat samanvärisiä, sitten p" ja q" ovat myös vakaita ystäviä. Tämä tarkoittaa, että vakaa ystävyys on yhteensopivuus ja voidaan jakaa seuraavasti: luo uusi graafi G", jonka kärjet ovat G:n vakaan ystävyyden ekvivalenssiluokkia. Jos G:ssä on vähintään yksi vakaa pari, niin G" on pienempi kuin G. Lisäksi jos alkuperäisessä graafissa G jokaisesta pisteestä oli d reunaa, niin G":ssä näin on. Esimerkiksi jos P on uuden graafin huippu, joka on alkuperäisten pisteiden p1, p2 ekvivalenssiluokka... , ja α on mikä tahansa väri, niin reunat p1--α--> q1, p2---α-->q2 jne. johtavat kaikki pisteisiin q1, q2..., jotka ovat vakaassa ystävyydessä kunkin kanssa. muut, ja siksi sijaitsevat yhdessä uudessa kärjessä Q, niin että kaikista näistä reunoista tulee uusi reuna P --α-->Q. Ja niin edelleen jokaiselle d-värille.

Lisäksi, jos G olisi ei-jaksollinen, niin myös G" on niin. Loppujen lopuksi - käyttämällä vaihtoehtoista jaksollisuuden määritelmäämme - mikä tahansa jakso G:ssä muuttuu jaksoksi G", joten jos kaikki G":n jaksojen pituudet ovat jaollinen luvulla n > 1, niin sama pätee kaikkiin G:n jaksoihin. Joten G" jaksollisuus merkitsee G:n jaksollisuutta.

Oletetaan, että onnistuimme löytämään synkronoitavan värityksen G:stä. Sitä voidaan nyt käyttää G:ssä sen värityksen sijaan, jolla aloitimme: mikä tahansa reuna p-->q saa uuden värin reunan P uuden värin mukaan. -->Q. Pitäisi olla hieman tarkempi, joten: graafin G" jokaisessa kärjessä P saadaan uusi väritys kaikkien värien permutaatiolla π P: värillä α värjätty reuna saa uuden värin π P (a). Sitten alkuperäisessä graafissa G kussakin stabiilisuusluokan P kärjessä p käytämme samaa permutaatiota π P värittämään sen reunat uudelleen. Yleisesti ottaen graafin G uusi väritys määrittelee joitain uusia käsitteitä "ystävyys", "viha" ja "vakaus", jotka eivät ole identtisiä alkuperäisten kanssa. Mutta kuitenkin, jos kaksi kärkeä p, q olivat stabiileja ystäviä vanhassa värityksessä - ne kuuluivat samaan luokkaan P - niin ne pysyvät stabiileina ystävinä uudessa. Tämä johtuu siitä, että mikä tahansa sekvenssi w, joka tuo p,q:n yhteen kärkeen, voidaan "kääntää" vanhasta värityksestä uuteen tai päinvastoin käyttämällä permutaatiota π P jokaisessa kärjessä p matkan varrella. Koska p,q ovat stabiileja vanhassa värjäyksessä ja pysyvät sellaisina "koko matkan", jokainen välipistepari p n , q n tiellä p,q:sta yhteiseen kärkeen on stabiili, ts. sijaitsevat yhden kärjen P n sisällä ja saavat siksi saman permutaation π P n .

Uusi väritys on synkronoitu G:lle, eli jokin sekvenssi w tuo kaikki kärjet yhteen kärkeen P. Jos nyt sovelletaan w:tä uuteen G:n väritykseen, niin kaikki kärjet suppenevat jonnekin "P:n sisällä". Kuten edellä todettiin, kaikki luokan P kärjet pysyvät vakaina uudessa värityksessä, mikä tarkoittaa, että voimme nyt jatkaa w:tä kokoamalla yhteen jäljellä olevat vielä erilliset pisteparit, kunnes kaikki konvergoi yhdeksi pisteeksi G. Uusi väritys on siis synkronoitu G.

Kaikesta tästä seuraa, että lauseen todistamiseksi riittää todistaa, että missä tahansa ehdot täyttävässä graafissa on väritys, jossa on pari vakaata ystävää. Koska silloin graafista G voidaan siirtyä pienempään kuvaajaan G" ja se myös täyttää kaikki ehdot. Induktiivista argumenttia käyttäen voidaan olettaa, että pienempikokoisten graafien kohdalla ongelma on jo ratkaistu, ja sitten synkronointivärjäys G:lle" synkronoidaan myös G:lle.

Klikit ja maksimisarjat

Kaikille graafin ja sanan w pisteiden osajoukolle A Aw tarkoittaa kärkijoukkoa, johon päädymme alkaen kaikista A:n pisteistä ja seuraamalla sanaa w. Jos aloitamme yleisesti graafin kaikista pisteistä, merkitsemme tätä Gw:llä. Tässä merkinnässä synkronoitava väritys tarkoittaa, että on olemassa w, jolloin Gw on yhden elementin joukko.

Jos pistejoukolla A on muotoa Gw jollekin w:lle ja lisäksi mitkä tahansa kaksi A:n kärkeä ovat vihollisia, ts. ei koskaan lähentyisi, soitetaan A:ksi klikki. Klikit ovat olemassa, koska voimme aina aloittaa koko G:stä, ottaa kaveripisteiden parin, kulkea niitä yhdistävän w:n läpi ja vähentää kärkien määrää yhdellä; jatka näin, kunnes jäljellä on vain vihollisia tai vain yksi kärkipiste - myös tässä tapauksessa klikki, yksinkertaisesti triviaali.

Jos A on klikki, niin mille tahansa sanalle w Aw on myös klikki; Tämä on selvää, koska viholliset pysyvät vihollisina. Jos x on mikä tahansa graafin kärki, on olemassa klikki, joka sisältää x:n. Tämä johtuu siitä tosiasiasta, että on olemassa jonkinlainen klikki A (katso edellinen kappale); jos p on siinä kärkipiste, niin siellä on sana w, joka johtaa p:stä x:ään, koska kytketty kaavio; niin Aw on klikki, joka sisältää x.

Napsautukset auttavat meitä todistamaan, että on olemassa väritystä vakaiden ystävien kanssa - edellisen osan mukaan tämä riittää todistamaan lauseen. Kautta tämän osion todistamme, että jos on kaksi klikkia A ja B siten, että kaikki niiden kärjet ovat yhteisiä paitsi yksi A:ssa ja yksi B:ssä, niin nämä kaksi kärkeä ovat stabiileja ystäviä. Siten ongelma rajoittuu klikejä A ja B sisältävän värityksen löytämiseen.

Klikkien toiminnan ymmärtämiseksi on hyödyllistä määrittää painoarvot graafin huipuille. Osoitetaan, että meillä on tapa antaa positiivinen paino w(x) jokaiselle pisteelle x, niin että jos jollekin kärjelle x summaa kaikkien niiden kärkien painot, joista on x:n reunat, niin saadaan d*w(x), missä d on kunkin kärjen reunojen lukumäärä. Tämä seuraa lineaarisesta algebrasta, ja jos et tiedä, mikä ominaisarvo on, ohita tämän kappaleen loppuosa ja pidä tällaisen w(x):n olemassaolo itsestäänselvyytenä. Jos M on graafin G matriisi (solu (i,j) on 1, jos on reuna i-->j, ja 0, jos sellaista ei ole, niin w(x), kuten ne kuvailin, ovat ominaisvektorin elementtejä vasemmalle tällä matriisilla on ominaisarvo d. Tiedämme, että tällainen vektori on olemassa, koska d on ominaisarvo: sillä on triviaali ominaisvektori oikealla(1,1,...1) - tämä seuraa välittömästi siitä, että jokaisesta kärjestä tulee tarkalleen d reunaa.

Jos A on mikä tahansa kärkijoukko, niin w(A) tarkoittaa kaikkien A:n kärkien painojen summaa; ja w(G) on graafin kaikkien pisteiden painojen summa. Lisäksi, jos s on mikä tahansa sana, olkoon As -1 pistejoukko, johon tulet A:sta, jos kuljet "vastakkaiseen suuntaan" s:tä pitkin, jokaisessa vaiheessa korvaamalla jokainen kärki niillä pisteillä (jos sellaisia ​​on) jotka menevät hänelle sopivalla värillä.

Tarkastellaan nyt kaikkia kärkijoukkoja, jotka voidaan yhdistää yhteen pisteeseen, ts. sellainen A, että joillekin w:lle Aw sisältää vain yhden kärjen. Niitä joukkoja A, joilla kaikista sellaisista joukoista on maksimipaino w(A), kutsutaan maksimijoukoiksi. Jos väritys on synkronoitu, niin koko graafi G on maksimijoukko (ainutlaatuinen), mutta muuten se ei ole.

Jos A on mikä tahansa kärkijoukko, niin kaikkien w(Aα -1) summa, jossa α kulkee kaikkien d värien yli, on yhtä suuri kuin d*w(A) - tämä on yksinkertaisesti yleistys painon pääominaisuudesta. yksi kärki pisteiden joukkoon A. Jos lisäksi tässä tapauksessa A on maksimijoukko, niin jokainen w(Aα -1) ei voi olla suurempi kuin w(A), koska myös nämä joukot pelkistyvät yhdeksi kärjeksi . Ja koska näiden painojen summa d on yhtä suuri kuin d*w(A), käy ilmi, että jokainen niistä on yhtä suuri kuin w(A), ja kaikki nämä joukot ovat myös maksimaalisia. Tästä seuraa välittömästi, että jos A on maksimi, niin Aw -1 on myös maksimi mille tahansa sanalle w.

Maksimijoukot ovat hyödyllisiä, koska niiden erillään olevat esiintymät voivat kattaa koko kaavion. Todistetaan se.

Olkoon joukko maksimijoukkoja A 1 ...A n , jotka disjunktoidaan pareittain ja on pelkistetty yksittäisiksi pisteiksi a 1 ...a n samalla sanalla w (alkutapauksessa on n=1 ja vain yksi asettaa, jotta se on helppo aloittaa). On selvää, että kaikki a 1 ...a n ovat erilaisia, koska muuten maksimijoukkoa voitaisiin laajentaa entisestään toisen saman loppupisteen elementtien takia. Oletetaan, että kaikki A i eivät ole vielä käyttäneet kaikkia G:n pisteitä, ja olkoon x kaikkien A i:n ulkopuolella oleva kärki. Koska kuvaaja on yhdistetty, on olemassa jokin reitti h pisteestä a pisteeseen x. Sitten n maksimijoukkoa A i h -1 w -1 menee sanan whw mukaan loppupisteisiin a 1 ...a n , ja maksimijoukko A 1 menee johonkin kärkeen Awhw = (Aw)hw = (a 1 h) w = xw. Tämän kärjen xw täytyy myös poiketa kaikista a 1 ...a n , koska muuten maksimijoukkoa A i voitaisiin täydentää alkiolla x. Ja koska kaikki nämä n+1 joukot - kaikki A i h -1 w -1 plus A 1 - kulkevat whw:tä pitkin eri pisteisiin, ne ovat kaikki pareittain disjunkteja. Jatkamme tätä laajennusta, kunnes joukon ulkopuolelle ei jää yhtään kärkeä.

Voimme siis peittää koko graafin G disjunkteilla maksimijoukoilla. Koska ne ovat maksimaalisia, niillä kaikilla on sama koko w max , ja siksi niiden lukumäärä peittoalueella on N max = w(G)/w max .

Tarkastellaan nyt mitä tahansa joukkoa A, joka koostuu pareittain vihollisista. Esimerkiksi klikki on esimerkki tällaisesta joukosta (ja sen muoto on myös Gw). Maksimijoukko ei voi sisältää vihollisparia, koska silloin se ei voisi lähentyä. Tämä tarkoittaa, että N maksimijoukon peitossa jokainen sisältää enintään yhden jäsenen A, joten A:n koko on enintään N max . Tarkemmin sanottuna se on minkä tahansa klikkin koon yläraja.

Olkoon A muotoa Gw oleva klikki, jossa w on jokin sana. Silloin G = Aw -1, ja vastaavasti w(G) on yhtä suuri kuin summa w(aw -1), jossa a kulkee A:n kaikkien kärkien läpi. Edellisen kappaleen mukaan termien määrä on enintään N max, ja jokainen joukko aw -1 voidaan pienentää yhteen pisteeseen (pisteessä a sanalla w), joten sen paino ei ole suurempi kuin maksimi w max . Koska koko summa on yhtä suuri kuin w(G) = N max *w max , päätämme, että termien määrä on täsmälleen yhtä suuri kuin N max ja jokainen termi on täsmälleen yhtä suuri kuin w max . Olemme osoittaneet, että kaikilla klikkeillä on sama koko: täsmälleen N max elementtiä.

Olkoon kaksi klikkausta A ja B siten, että A:n sisällä kaikki elementit ovat yhteisiä B:n kanssa paitsi yksi: |A| - |A∩B| = 1.

Koska A ja B ovat samankokoisia, meillä on myös |B| - |A∩B| = 1, ts. A:lla ja B:llä on kaikki yhteiset alkiot, paitsi yksi kärki p A:ssa ja yksi kärki q B:ssä. Haluamme todistaa, että nämä kärjet p,q ovat stabiileja ystäviä. Jos näin ei ole, jokin sana w tekee heistä vihollisia, ts. pw ja qw ovat vihollisia. Kuten yllä näkyy, Aw ja Bw ovat myös klikkejä, ja on selvää, että niillä on taas kaikki yhteiset elementit, paitsi viholliset pw ja qw. Sitten joukko Aw ∪ Bw on joukko vihollisia pareittain. Todellakin, siinä kaikki Aw:n elementit ovat pareittain vihollisia, koska se on klikki; sama pätee Bw-elementteihin; ja vain pari pw,qw jäi - myös vihollisia. Mutta tässä joukossa on N max +1 elementtiä, ja edellä osoitimme, että pareittain vihollisilla ei voi olla enempää kuin N max elementtiä. Tämä on ristiriita, ja siksi pw ja qw eivät voi olla minkään w:n vihollisia. Toisin sanoen p ja q ovat vakaita ystäviä.

Kaaviot ja klikkit

Otetaan kaikki pisteet annetusta graafista G ja valitaan vain yksi lähtevä reuna kustakin pisteestä. Tämä valinta määrittää aligraafin, jota kutsumme ulottuva kaavio(kattava kaavio). Kaavioita voi olla monia erilaisia, mutta mietitäänpä vähän, miltä ne näyttävät. Olkoon tietty virittävä graafi R. Jos otamme sen minkä tahansa kärjen x ja alamme seurata sen reunoja, niin meillä on joka kerta yksi vaihtoehto, koska R:ssä kustakin kärjestä tulee vain yksi reuna, ja ennemmin tai myöhemmin suljemme syklin. Ehkä tämä sykli ei sulkeudu kohdassa x, vaan sulkeutuu jossain "edemmäs" - esimerkiksi x-->y-->z-->s-->y. Sitten tämän syklin "häntä" johtaa x:stä. Jos aloitamme jostain toisesta kärjestä, päädymme varmasti myös sykliin - tähän tai johonkin toiseen. Osoittautuu, että mikä tahansa kärki R joko sijaitsee syklissä (joita voi olla useita) tai on osa "häntä", joka johtaa sykliin. Tämä tarkoittaa, että R näyttää tältä: tietty määrä syklejä ja tietty määrä "käänteisiä" puita rakennetaan niille: jokainen puu ei ala, vaan päättyy "juureen", joka sijaitsee yhdessä syklistä.

Voimme määrittää kullekin graafin kärjelle taso, joka vastaa sen etäisyyttä sykliin tietyssä ulottuvassa graafissa R. Kierroksella sijaitsevien kärkien taso on 0, ja sykliin liitetyssä puussa olevat kärjet saavat tason, joka on yhtä suuri kuin niiden puun etäisyys "juureen" ”makaa pyörällä. Joillakin graafimme pisteillä on maksimitaso L. Ehkä se on jopa yhtä suuri kuin 0 - ts. ei ole puita, vain pyöriä. Ehkä se on suurempi kuin nolla, ja tämän maksimitason kärjet sijaitsevat kaikenlaisissa erilaisissa puissa, jotka on kytketty eri sykleihin tai yhteen.

Haluamme valita virittävän graafin R siten, että kaikki maksimitason kärjet ovat samassa puussa. Intuitiivisesti voidaan uskoa, että näin voidaan tehdä, koska jos näin ei ole - esimerkiksi ne ovat hajallaan eri puiden poikki -, voidaan valita yksi sellaisista maksimipisteistä x ja nostaa sen tasoa kiinnittämällä R:ään jonkin verran reunaa. x:lle. Sitten joku toinen kylkiluu täytyy heittää ulos, eikä se ole tosiasia, ettei se vahingoita jotain muuta... mutta tämä on tekninen kysymys, josta keskustellaan myöhemmin. Yritän vain sanoa, että se ei vaikuta kovin monimutkaiselta intuitiivisesti.

Oletetaan nyt, että voimme valita R:n niin, että kaikki maksimitason kärjet ovat samassa puussa. Tämän puun oletetaan olevan ei-triviaali, ts. maksimitaso L > 0. Tämän oletuksen perusteella rakennetaan väritys, jossa on edellisen osan ehdot täyttäviä klikejä A ja B, mikä todistaa, että tässä värjäyksessä on vakaa pari ystävät.

Väritys tulee olemaan seuraava: valitse jokin väri α ja värjää kaikki graafin R reunat tällä värillä ja kaikki muut graafin G reunat joillakin muilla väreillä millä tahansa tavalla (jos väriä on vain yksi, niin R on sama kuin G , joten ongelmaa ei ole). Siten sanat, jotka koostuvat väristä α "työntävät" R:n kärjet puissaan kohti syklejä ja ajavat ne sitten syklien läpi. Nämä ovat ainoat sanat, joita tarvitsemme.

Olkoon x mikä tahansa R:n maksimitason L kärkipiste ja olkoon K mikä tahansa klikki, mukaan lukien x; tiedämme, että sellainen klikki on olemassa. Voiko K sisältää jonkin muun huipputason L huippupisteen? Oletuksemme mukaan kaikki tällaiset kärjet ovat samassa puussa kuin x, mikä tarkoittaa, että sana α L vie ne samaan paikkaan kuin x - eli tämän puun juureen, joka sijaitsee syklissä. Tämä tarkoittaa, että kaikki tällaiset kärjet ovat x:n ystäviä, eivätkä siksi voi olla samassa klikissä sen kanssa. Siksi K voi sisältää x:n lisäksi vain alemman tason pisteitä.

Katsotaan joukkoa A = Kα L-1. Tämä on myös klikki, ja siinä kaikki kärjet paitsi x ovat saavuttaneet jonkinlaisen syklin R:ssä, koska kaikilla A:n pisteillä, paitsi x:llä, on taso pienempi kuin L. Vain x jää syklin ulkopuolelle, klo. etäisyys täsmälleen 1 sen juureen syklissä. Otetaan nyt jokin luku m, joka on R:n kaikkien syklin pituuksien monikerta - esimerkiksi kaikkien syklin pituuksien tulo. m:llä on sellainen ominaisuus, että jos kärki y on syklissä R:ssä, niin sana α m palauttaa sen paikalleen: yα m = y. Katsotaanpa klikkausta B = Aα m . Kaikki A:n kärjet, paitsi x, olivat sykleissä ja pysyivät siksi siellä B:ssä; ja vain x astui lopulta kiertokulkunsa ja asettui sinne jonnekin. Tämä tarkoittaa, että A:n ja B:n leikkauspiste sisältää kaikki A:n pisteet paitsi yhtä: |A| - |A∩B| = 1. Mutta tämä tarkoittaa vain edellisen osion mukaan, että värityksillämme on vakaa pari, mikä meidän piti todistaa.

Maksimitason rakentaminen.

On vielä todistettava, että on aina mahdollista valita virittävä graafi R siten, että sen ei-triviaali maksimitaso L > 0 ja tämän tason kaikki kärjet ovat samassa puussa.

Osa tästä todisteesta on melko tylsä ​​ja tekninen lemma, jonka luin ja tarkistin, mutta en toista sitä, kerron vain kiinnostuneille, missä se on artikkelissa. Mutta kerron sinulle, kuinka pääset tähän lemmaan.

Tarvitsemme kaksi rajoitusta, jotka voimme asettaa graafille G. Oletetaan ensin, että G:llä ei ole silmukoita, ts. reunat kärjestä samaan kärkeen. Asia on siinä, että jos kaaviossa on silmukka, niin synkronoiva väritys on erittäin helppo löytää toisella tavalla. Väritetään tämä silmukka värillä α, ja sitten tästä kärjestä päinvastaiseen suuntaan "nuolia vasten" värjätään reunat niin, että väri α johtaa aina tähän kärkeen. Koska graafi on yhdistetty, tämä on helppo järjestää, ja sitten silmukka varmistaa, että jokin aste α pienentää koko graafin tähän kärkeen.

Oletetaan seuraavaksi hetkeksi, että jostain pisteestä p kaikki d reunat johtavat samaan kärkeen q. Tämän sallivat ehdot, mutta tässä tapauksessa kutsumme tätä reunajoukkoa kimppu. Toinen rajoitteemme on tämä: ei ole kärkeä r, johon kaksi linkkiä eri pisteistä p ja q johtavat. Miksi voimme määrätä sen? Koska jos konnektiivit siirtyvät p:stä ja q:stä r:ään, niin millä tahansa värjäyksellä p q suppenee kärjessä r ensimmäisen värin jälkeen, ja siksi ne ovat vakaita ystäviä. Joten tässä tapauksessa emme tarvitse kaikkea ulottuvien kuvaajien ja klikkien rakentamista, vaan saamme heti vakaat ystävät. Siksi voimme olettaa, että näin ei ole.

Lopuksi todistetaan, että aina on olemassa virittävä graafi R, jonka kaikki kärjet eivät sijaitse sykleissä, mutta on olemassa joitain ei-triviaaleja puita. Valitaan jokin R ja oletetaan, että sen kaikki kärjet ovat sykleissä. Jos kaikki graafin G reunat olisivat yhteydessä toisiinsa, ts. aina kaikki d reunat, jotka lähtevät samasta kärjestä, johtivat samaan kärkipisteeseen - silloin R:n valinta edellyttäisi vain yhden reunan valitsemista jokaisesta linkistä. Tässä tapauksessa R:ssä voisi olla vain yksi sykli (loppujen lopuksi useita sykliä R:ssä ei voi mitenkään olla yhteydessä toisiinsa yhdistetyssä graafissa G - kaikki G:n reunat yhdistävät vain samat kärjet kuin R:n reunat, koska nämä ovat konnekiveja - ja koska G on kytketty, tämä on mahdotonta), ja mikä tahansa sykli G:ssä yksinkertaisesti valitsee muut reunat tämän syklin kytkennöistä, mutta pohjimmiltaan se on sama sykli, samanpituinen. Mutta tämä tarkoittaa, että G:n kaikkien syklien pituudet ovat jaollisia tällä pituudella, mikä on täsmälleen ristiriidassa G:n epäjaksollisuuden kanssa. Siksi ei voi olla niin, että kaikki G:n reunat ovat linkeillä, mikä tarkoittaa, että särmiä on noin kaksi. p-->q R:ssä ja p-->s R:n ulkopuolella (tarvitsimme pitkän argumentin konnekiiveista todistaaksemme, että jokin p:n reuna ei vain ole virittävässä graafissa, vaan johtaa myös toiseen kärkeen s). Sitten korvaamme p-->q p-->s:llä, ja tämä "katkaisee" kierteen luoden siihen jonkinlaisen ei-triviaalin hännän. Tämä häntä antaa meille ei-triviaalin puun uudessa kaaviossa.

Nyt voimme valita kaikista ei-triviaalisia puita sisältävistä virittävistä graafeista R jonkin R:n, jolla on maksimipistemäärä syklissä. Tuo on siinä on pisteitä, jotka eivät ole sykleissä, mutta tämän rajoituksen lisäksi syklien kärkien määrä on maksimoitu. Tässä graafissa on joitain maksimitason L pisteitä, ja voimme olettaa, että ne ovat eri juurille johtavissa puissa, muuten olemme jo saavuttaneet tarvitsemamme. Valitaan yksi tällainen kärkipiste x. Haluamme muuttaa graafia niin, että tästä kärjestä tulee osa pidempää reittiä puussa, pidempi kuin L, ja muut puut eivät muutu, ja silloin maksimitaso on vain yhdessä puussa, mitä haluamme. Voit muuttaa kaaviota kolmella tavalla:

a) ota jokin reuna y-->x ja lisää se R:ään ja hylkää olemassa oleva reuna y-->z;
b) ota reuna b-->r, joka on vain viimeinen polulla x:stä sen sykliin (r syklissä), ja heitä se pois ja lisää jotain muuta b-->z.
c) ota reuna c-->r, joka on osa sykliä, ja hylkää se ja lisää jotain muuta c-->z.

Trakhtmanin paperin lemma 7 osoittaa yksityiskohtaisesti, että yksi (tai joissain tapauksissa kaksi) näistä muutoksista johtaa haluttuun tulokseen. Prosessi käyttää sekä R:n maksimaalisuutta (jos jokin muutos johtaa graafiin, jossa on suurempi määrä pisteitä syklissä kuin R:ssä, tämä on ristiriidassa sen maksimaalisuuden kanssa), että edellä määriteltyä ehtoa, että ei ole kärkeä, johon kaksi linkkiä johtaa. Tuloksena joka tapauksessa saadaan graafi R, jossa kaikki maksimitason kärjet ovat yhdessä ei-triviaalipuussa.

Päivitys viikon kuluttua: Päätin kuitenkin tehdä tästä merkinnästä täysin omavaraisen ja myös toistaa edellisessä kappaleessa mainitsemani lemman todisteen. Olisi parempi tehdä tämä kaaviolla, mutta en halua piirtää sitä tai repiä sitä pois artikkelista, joten yritän sanoin. Kuvittele siis, että meillä on virittävä graafi R, jossa on ei-triviaaleja puita, ja kaikista siinä olevista graafista suurin määrä pisteitä on syklillä. Pyrimme muuttamaan R:n virittäväksi graafiksi, jossa kaikki maksimitason kärjet ovat samassa puussa; Heti kun saamme sellaisen graafin kokeiluvaiheessa, lopetamme heti (eikä me välitä siitä, että graafin maksimaalisuus syklien kärkien lukumäärässä voi kadota, se ei ole meille tärkeää itse, käytämme sitä vain prosessissa). Olkoon x maksimitason L kärki, T puu, jolla se sijaitsee, r syklin C kärki, johon T päättyy, b-->r viimeinen reuna ennen r:tä polulla x:stä sykliin C. Voimme olettaa, että tähän kiertoon liittyy muita puita tai muita, joilla on L-tason kärkipisteet - muuten kaikki on jo tehty. Tästä seuraa, että jos voimme saada T:stä puun, jonka alkio on suurempi kuin L, emmekä jatka näitä muita puita, niin olemme valmiita.

Ensin yritetään tehdä yllä oleva operaatio a): otetaan jokin G:n reuna y-->x - se on olemassa, koska Kaavio on yhdistetty ja ilman silmukoita, eikä se ole R:ssä, koska x maksimitaso. Lisätään se R:ään ja heitetään pois y-->z, joka oli siellä aiemmin. Jos y on puussa T, niin y-->x sulkee uuden syklin ja uudessa graafissa on enemmän pisteitä sykleissä, ja vielä on ei-triviaaleja puita (ainakin ne muut, jotka olivat R:ssä), jotka on ristiriidassa R:n maksimaalisuuden kanssa. Jos y ei ole T:ssä ja y-->z ei ole osa sykliä C, niin y-->z:n poistaminen ei katkaise tätä sykliä, mutta y-->x:n lisääminen laajentaa maksimiarvoa puun taso T vähintään yhdellä, ja toisissa puut eivät pidennä, joten olemme valmiita. Jäljellä oleva vaihtoehto on, kun y-->z makaa syklillä C, joka on nyt katkennut ja uusi sykli on muodostunut: r:stä y:hen, sitten y-->x, sitten x:stä r:ään entisen puun mukaan. Tämän syklin pituus on l(ry)+1+L ja vanhan syklin C pituus oli l(ry)+1+l(zr). Uusi sykli ei voi olla pidempi kuin vanha, tämä on ristiriidassa R:n maksimaalisuuden kanssa, joten näemme, että L ≤ l(zr), ts. reitin pituus z:stä r:hen vanhassa silmukassa. Toisaalta uudessa graafissa kärjen z taso on nyt vähintään l(zr), ja jos tämä on suurempi kuin L, niin olemme valmiita. Voimme siis olettaa, että l(zr)=L. Yhteenvetona: oletetaan, että a) ei toimi, ja sitten tiedämme, että y-->z on syklillä C, l(zr) = L.

Kokeillaan nyt operaatiota b): korvaa reuna b-->r jollain toisella reunalla b-->d. Katsotaan missä uusi kärki d sijaitsee. Jos puussa T, niin loimme uuden syklin rikkomatta edellistä ja kumoimme R:n maksimaalisuuden. Jos toisessa puussa, niin T:n maksimipisteillä, mukaan lukien x, on nyt taso suurempi kuin L, ja muut puut eivät, ja olemme valmiita. Jos toisessa syklissä, ei C, niin tehdään nyt b):n ohella myös a): koska tiedämme, että y-->z on C:ssä, niin tämä operaatio jakaa C:n, mutta ei uutta sykliä, johon se on nyt yhdistetty puu T, ja tässä puussa on nyt L:tä suuremman tason kärjet, ja olemme taas valmiit.

Jäljellä oleva vaihtoehto on, kun b-->d on myös kytketty kiertoon C, jossain muussa paikassa kuin r, tai samassa paikassa ja sitten d=r. Kun korvasimme b-->r:n b-->d:llä, saimme saman tilanteen kuin alun perin - puu T, tason L kärki x jne. - vain puu on nyt kytketty kiertoon kärjen d kautta. Tarkasteltaessa nyt operaatiota a) päätämme (olettaen, että se ei toimi), että l(zd) = L, aivan kuten aiemmin päätimme, että l(zr) = L. Mutta jos l(zd) = l( zr), ts. etäisyys sykliä pitkin z:stä on sama d:hen ja r:iin, silloin tämä on sama kärki: d=r. Joten jos b) ei toimi, minkä tahansa b:n reunan on johdettava r:ään, ts. b:n reunat muodostavat linkin.

Lopuksi tarkastellaan syklissä C olevaa reunaa c-->r. Koska voidaan olettaa, että kaikki b:n reunat ovat r:ään johtavassa linkissä, voidaan myös asettaa edellä mainittu rajoitus, että kahta linkkiä ei voi olla, mikä johtaa yksi kärki, kaikki reunat c:stä eivät johda r:ään, mutta on olemassa jokin reuna c-->e. Korvataan c-->r c-->e:llä. Missä vertex e voi olla? Ei puussa T, koska se "pidentää" sykliä C, mikä on ristiriidassa R:n maksimaalisuuden kanssa. Joten e sijaitsee toisessa puussa tai toisessa syklissä tai jopa samassa syklissä C, mutta ei kärjessä r. Sitten puuta T, ennen kuin se liittyy silmukkaan, jatketaan nyt ainakin yhdellä r:stä lähtevällä reunalla ja ehkä useammalla (vain yhdellä, jos e on välittömästi r:n jälkeen, ja c-->e sulkee silmukan C uudelleen, johdetaan siitä vain r). Tämä tarkoittaa, että kärjellä x ja muilla maksimipisteillä T on nyt taso vähintään L+1, eivätkä muut puut ole pidentyneet, ja taas saimme mitä tarvitsemme.

Disneyn ja Pixarin ansiosta koko maailma näki kesäkuussa 2006 sarjakuvan, jossa vain autoista tuli sankareita.

Cars-sarjakuvan autot elävät tavallista elämää - toinen pyörittää rengasliikettä, toinen viritysstudiota, ja jotkut vain elävät omaksi ilokseen, kuten hippi Fillmore (Volkswagen T1) tai hänen ystävänsä, toisen maailmansodan veteraani. Serge (Willys). Elokuvan päähenkilö McQueen, lempinimeltään "Salama", haaveilee vain kilpailusta, voitoista ja kunniasta. Kerran kuuluisan American Highway 66:n Radiator Districtissä vielä ”vihreä” McQueen kertoo heti kaikille, kuinka nopea ja viileä hän on. Hänen ensimmäinen lähtönsä NASCAR-kilpailussa kuitenkin hälventää hänen illuusionsa. Ystävät auttavat sankaria selviytymään menetyksestä - vanha hinausauto Mater (GMC Pick-up), mentori Doc Hudson (Hudson Hornet) ja pieni Luigi (Fiat 600), joka haaveilee näkevänsä oikean Ferrarin.

No, missä olisimme ilman romanttista kaunotar Sallya (Porsche hurmaavalla 911-tatuoinnilla)! Suurelta osin heidän ansiostaan ​​McQueen voittaa kilpailun voittaen Chicon pääkilpailijan (Plymouth Hemi Cuda). Luigin unelma myös toteutuu - jonain päivänä "Maranellon ori", jota muuten itse "Red Baron" Michael Schumacher on äänestänyt, tulee hänen myymäläänsä vaihtamaan renkaita.

On huomionarvoista, että sekä elokuvan luojat että sen esittäjät ovat henkilöitä, jotka ovat mukana autoissa. Esimerkiksi ohjaaja Joe Lasseter vietti melkein koko lapsuutensa Chevroletin tehtaalla, jossa hänen isänsä oli yksi pääsuunnittelijoista. Fordin johtava suunnittelija Jay Mays toimi konsulttina. Jo mainitun seitsenkertaisen Formula 1 -maailmanmestarin Michael Schumacherin lisäksi hahmojen äänittämiseen osallistuivat NASCAR-tähdet Richard Petty ja Paul Newman sekä legendaarinen kilpailija Michael Andretti.

Vain autojen alkuperäistä melua käytettiin - esimerkiksi erityisesti kilpailujaksoissa ääni nauhoitettiin useiden viikkojen ajan amerikkalaisille soikeille NASCAR-kilpailujen aikana. Elokuvan luominen kesti yli kaksi vuotta, ja sen budjetti oli 70 miljoonaa USD. Tänä aikana luotiin 43 tuhatta erilaista luonnosta autoista, ja jokainen piirustus kesti yli 17 tuntia. Elokuvassa on yhteensä 120 autohahmoa - uusista Porscheista ja Ferrariista antiikkiseen Ford T:hen.

Lapsen tieliikennesääntöjen tuntemus on yksi hänen turvallisuutensa tärkeimmistä edellytyksistä kadulla. Monet jalankulkijat, myös aikuiset, suhtautuvat näihin sääntöihin melko kevyesti, mikä aiheuttaa usein vaihtelevan vakavuuden liikenneonnettomuuksia. Lasten on ymmärrettävä selvästi, että asuessaan kadulla he ovat täysimääräisesti tieliikenteessä mukana, joten liikennesääntöjen noudattaminen on heidän vastuullaan.

Värityssivut Liikennesäännöt lapsille.

Kadulla käyttäytymissääntöjen (tiet, jalkakäytävät, kaupunkiliikenne) opettaminen lapselle tulee aloittaa hyvin varhaisessa iässä, ennen kuin hän oppii kävelemään ja juoksemaan yksin. Ja tässä vanhempien ja muiden aikuisten esimerkki, joiden kanssa lapsi on kadulla, on erittäin tärkeä. Sinun ei tarvitse vain kertoa ja selittää liikennesääntöjä lapsellesi, vaan myös noudattaa niitä tarkasti itse. Tällä sivulla esitetyt liikennesääntöjen värityssivut on tarkoitettu ensisijaisesti esikoululaisille ja auttavat lapsia oppimaan käyttäytymisen peruskohdat tiellä ja sen lähellä.

1. Värityssivu Liikennevalo.

Paras paikka turvallisesti ylittää tie on liikennevalolla varustettu jalankulkutie. Liikennevalokuvia sisältävät värityssivut sisältävät myös pieniä riimejä, joiden avulla lapset muistavat helpommin niiden käytön säännöt.

• Aloita ajaminen vasta, kun liikennevalo palaa vihreänä.
• Älä koskaan ylitä tietä, kun liikennevalot ovat punaisia ​​tai keltaisia, vaikka lähellä ei olisi ajoneuvoja.
• Kun käännyt vihreään valoon, varmista lisäksi turvallisuutesi - katso vasemmalle, sitten oikealle.

2. Värityssivu jalankulkutie.

Opeta lapsesi ylittämään ajorata vain jalankulkusilta. Jalankulkijoiden ylitysten värityssivut opettavat lapsille kuinka ylittää tie oikein. Risteystä, jota ei ole varustettu liikennevalolla, kutsutaan sääntelemättömäksi.

• Jalankulkutie on merkitty tien pintaan suojatietä.
• Ennen tien ylittämistä tarkasta se huolellisesti ja varmista, ettei lähistöllä ole liikennettä.
• Ylitä tie, älä juokse sen yli.
• Älä ylitä katua vinottain.
• Kiinnitä erityistä huomiota paikallaan oleviin ajoneuvoihin, jotka estävät näkyvyyden.
• Lopeta puhelimessa puhuminen, kun liikut jalankulkurajan yli.
• Jos lähistöllä on maanalaisia ​​tai ylikulkusiltaja, muista käyttää niitä, sillä liikenne on niissä erityisen vilkasta.

3. Jalkakäytävät.

Jalkakäytävä on tarkoitettu jalankulkijoille. Opeta lapsia käyttäytymään oikein jalkakäytävillä, erityisesti niillä alueilla, joilla on vilkasta liikennettä.

• Kun ajat jalkakäytävällä tietä pitkin, älä mene liian lähelle sitä.
• Tarkkaile tarkasti mahdollisia ajoneuvoja, jotka poistuvat pihoilta ja kujilta.
• Älä pelaa palloa jalkakäytävällä tai juokse.

4. Värityssivut lasten käyttäytymissäännöillä kaupungin julkisessa liikenteessä ja bussipysäkeillä.

Nämä värityssivut opettavat lapsille turvallisen julkisen liikenteen käytön.

• Joukkoliikenteen pysäkki on vaarallinen paikka mahdollisen huonon tienäkymän ja suuren ihmisjoukon vuoksi, joka voi vahingossa työntää lapsen jalkakäytävältä tielle. Tässä sinun on oltava erityisen varovainen.
• Lähesty ajoneuvon ovia vasta, kun se on täysin pysähtynyt.
• Ajoneuvosta noustuaan lähde ylittämään tien vasta sen jälkeen, kun se on poistunut pysäkiltä.

Näiden perusliikennesääntöjen lisäksi lapset ovat kiinnostuneita liikennemerkkien värittämisestä. Esitellyt liikennesääntöjen värityssivut sopivat taaperoille, esikoululaisille ja alakoululaisille sekä käytettäväksi päiväkodeissa ja ala-asteen tunneilla. Kaikki kuvat liikennesäännöillä ovat täysin ilmaisia ​​- voit ladata ja tulostaa ne.

Voit pitää pojat kiireisenä pitkään, jos kutsut heidät leikkimään autojen kanssa hiekkalaatikkoon. Mutta mitä tehdä, jos ulkona on kylmä ja lapsella on tylsää. Tässä tapauksessa voit ladata ja tulostaa seuraavat autojen tiemallit. Hauskuus alkaa leikkaamalla kaikki renkaat, käännökset ja suorat tiet. Näistä malleista lapsi voi rakentaa minkä muotoisen tien tahansa; varmista vain, että tarvittava määrä tarvittavia A4-arkkeja tulostetaan.

Lataa suora tie autoille

Tarvitset suurimman osan näistä levyistä. Olemme sijoittaneet A4-arkille 3 tietä, jotka on tulostettava ja leikattava. Näytä lapsellesi, kuinka tie leikataan suorassa kulmassa, jotta osasta tulee hänen tarvitsemansa pituus.

Tie autoille: rengas

Teiden yhdistämiseen tarvitset renkaan, jonka malli on esitetty yllä, ja aloita infrastruktuurin rakentaminen sieltä.

Tie autoille: suora käännös

Esitetyt käännökset antavat pojan kääntää tietä 90 astetta hänen tarvitsemaansa suuntaan.

Ei jyrkkää käännettä tiellä autoille

Seuraava A4-malli auttaa sinua kääntämään tietä millä tahansa säteellä.