Värvimisraamatu tee. Liikluseeskirjade värvimislehed. Klikid ja maksimaalsed komplektid

Poistel saad kaua töös hoida, kui kutsud nad liivakasti autodega mängima. Aga mida teha, kui väljas on külm ja lapsel on igav. Sel juhul saate alla laadida ja printida järgmised autode teemallid. Lõbu algab kõigi rõngaste, pöördete ja sirgete teede väljalõikamisega. Nendest mallidest saab laps ehitada mis tahes kujuga tee, vaid veenduge, et vajalik arv A4-lehti oleks prinditud.

Laadige alla sirge tee autode jaoks

Teil on vaja kõige rohkem neid lehti. A4 paberilehele oleme paigutanud 3 teed, mis tuleb printida ja välja lõigata. Näidake oma lapsele, kuidas lõigata teed täisnurga all, et lõigu pikkus oleks talle vajalik.

Autode tee: ring

Teede ühendamiseks vajate rõngast, mille mall on ülaltoodud, ja alustage oma infrastruktuuri ehitamist sealt.

Tee autodele: otsepööre

Esitatud pöörded võimaldavad poisil pöörata teed 90 kraadi, talle vajalikus suunas.

Mitte järsku kurvi teel autodele

Järgmine A4 mall aitab teil teed pöörata mis tahes raadiuses.

Lapse reeglite tundmine liiklust- üks peamisi tingimusi tema ohutuse tagamiseks tänaval. Paljud jalakäijad, sealhulgas täiskasvanud, suhtuvad nendesse reeglitesse üsna kergekäeliselt, mis sageli muutub erineva raskusastmega liiklusõnnetuste põhjuseks. Lapsed peavad selgelt aru saama, et asustatud alal tänaval olles on nad täieõiguslikud teeliikluses osalejad, mistõttu on liiklusreeglite järgimine nende kohustus.

Värvimislehed Liikluseeskirjad lastele.

Lapsele tänaval käitumisreeglite (teed, kõnniteed, linnatransport) õpetamine peaks algama üsna varakult. varajane iga, enne kui ta õpib iseseisvalt kõndima ja jooksma. Ja siin on väga oluline vanemate ja teiste täiskasvanute eeskuju, kellega laps tänaval on. Liiklusreegleid ei pea mitte ainult lapsele rääkima ja selgitama, vaid ka ise neid rangelt järgima. Sellel lehel esitletavad liiklusreeglite värvimislehed on mõeldud eelkõige koolieelikutele ning aitavad lastel õppida nii teel kui ka selle läheduses käitumise põhipunkte.

1. Värvimisleht Valgusfoor.

Parim koht ohutuks teeületamiseks on fooriga varustatud ülekäigurada. Valgusfoori kujutistega värvimislehed sisaldavad ka väikeseid riime, mis aitavad lastel nende kasutamise reegleid hõlpsamini meeles pidada.

• Alustage sõitu alati ainult siis, kui foorituli on roheline.
• Ärge kunagi ületage teed, kui foorid on punased või kollased, isegi kui läheduses pole ühtegi sõidukit.
• Rohelisele tulele keerates veenduge lisaks oma ohutuses – vaadake vasakule, siis paremale.

2. Värvimisleht ülekäigurada.

Õpetage oma last ületama sõidutee tänavatel ainult ülekäigurajal. Ülekäiguradade värvimislehed õpetavad lastele, kuidas teed õigesti ületada. Reguleerimata ülekäigurada, mis ei ole varustatud fooriga, nimetatakse reguleerimata.

• Ülekäigurada on teepinnale tähistatud ülekäigurajaga.
• Enne tee ületamist vaadake see hoolikalt üle ja veenduge, et läheduses pole liiklust.
• Ületa tee, ära jookse üle selle.
• Ärge ületage tänavat diagonaalselt.
• Pöörake erilist tähelepanu seisvatele sõidukitele, mis takistavad teie vaadet.
• Ülekäigurajal liikudes lõpetage telefoniga rääkimine.
• Kui läheduses on maa-aluseid või viadukte, kasutage neid kindlasti sellistes kohtades eriti intensiivselt.

3. Kõnniteed.

Kõnnitee on ette nähtud jalakäijate liiklemiseks. Õpetage lapsi õigesti käituma kõnniteedel, eriti neil, mis asuvad tiheda liiklusega piirkondades.

• Sõites mööda teed kõnniteel ärge minge sellele liiga lähedale.
• Jälgige hoolikalt võimalikke sõidukeid, mis väljuvad hoovidest ja alleedest.
• Ärge mängige kõnniteel palli ega jookske.

4. Lastele käitumisreeglitega värvimislehed linna ühistranspordis ja bussipeatustes.

Need värvimislehed õpetavad lastele ühistranspordi ohutut kasutamist.

• Peatus ühistransport- ohtlik koht, mis on tingitud võimalikust halvast vaatest teele ja suurest inimestest, kes võivad kogemata lapse kõnniteelt sõiduteele lükata. Siin peate olema eriti ettevaatlik.
• Lähenege sõiduki ustele alles pärast seda, kui see on täielikult seiskunud.
• Pärast sõidukist väljumist jätkake teed ületama alles pärast peatusest väljumist.

Lisaks neile põhilistele liiklusreeglitele tunnevad lapsed huvi liiklusmärkide värvimise vastu. Esitletavad liiklusreeglite värvimislehed sobivad mudilastele, koolieelikutele ja väiksematele õpilastele koolieas, samuti kasutamiseks lasteaedades ja algklasside tundides. Kõik liiklusreeglitega pildid on täiesti tasuta – saate neid alla laadida ja printida.

Tänu Disneyle ja Pixarile nägi 2006. aasta juunis kogu maailm koomiksit, mille kangelasteks said ainult autod.

Multifilmis Cars olevad autod elavad tavalist elu – üks peab rehvipoodi, teine ​​tuunimisstuudiot ja mõni elab lihtsalt oma lõbuks, nagu hipi Fillmore (Volkswagen T1) või tema sõber, Teise maailmasõja veteran. Serge (Willys). Filmi peategelane McQueen, hüüdnimega "Välk", unistab ainult võidusõidust, võitudest ja hiilgusest. Kord kuulsal Ameerika maanteel 66 asuvas Radiaatorite rajoonis ütleb endiselt “roheline” McQueen kohe kõigile, kui kiire ja lahe ta on. Tema esimene start NASCARi võistlusel hajutab aga tema illusioonid. Sõbrad aitavad kangelasel kaotust üle elada – vana puksiirauto Mater (GMC Pick-up), mentor Doc Hudson (Hudson Hornet) ja väike Luigi (Fiat 600), kes unistab näha ehtsat Ferrarit.

Noh, kus me oleksime ilma romantilise kaunitari Sallyta (Porsche võluva 911 tätoveeringuga)! Suuresti tänu neile võidab sõidu siiski McQueen, alistades Chico peamise rivaali (Plymouth Hemi Cuda). Samuti täitub Luigi unistus – ühel päeval tuleb tema poodi rehve vahetama “Maranello täkk”, kelle häält on muide “punane parun” ise Michael Schumacher.

Tähelepanuväärne on, et nii filmi loojad kui ka hääle andjad on autodega seotud inimesed. Näiteks direktor Joe Lasseter veetis peaaegu kogu oma lapsepõlve Chevrolet' tehases, kus tema isa oli üks peadisainereid. Fordi juhtiv disainer Jay Mays tegutses konsultandina. Lisaks juba mainitud seitsmekordsele vormel 1 maailmameistrile Michael Schumacherile osalesid tegelaste häälestamises NASCARi staarid Richard Petty ja Paul Newman ning legendaarne võidusõitja Michael Andretti.

Kasutati ainult autode originaalset müra – näiteks eriti võidusõiduepisoodide puhul salvestati heli mitu nädalat Ameerika ovaalidel NASCARi võistluste ajal. Filmi, mille eelarve oli 70 miljonit USA dollarit, loomiseks kulus üle kahe aasta. Selle aja jooksul valmis 43 tuhat erinevat auto visandit ja iga joonistamine võttis aega üle 17 tunni. Kokku on filmis 120 autotegelast – uutest Porschedest ja Ferraridest kuni antiikse Ford T-ni.

(see sissekanne võib huvi pakkuda lugejatele, kes tunnevad matemaatikat ja kaastunnet)

Teisel päeval lugesin graafiteooriast huvitavast probleemist - tee värvimise oletusest. See oletus on olnud avatud 37 aastat, kuid kolm aastat tagasi tõestas seda Iisraeli matemaatik Abraham Trachtman. Tõestus osutus üsna elementaarseks ja mõningate raskustega (kuna mu ajud olid atrofeerunud) sain selle läbi lugeda ja aru saada ning proovin seda isegi selles postituses selgitada.

Probleemi saab selgitada järgmise näitega. Kujutage ette linnakaarti, mille igal ristmikul saate liikuda ühes neljast suunast – põhja, lõuna, ida ja lääne suunas. Kui auto alustab mõnelt ristmikult ja järgib mingit juhiste loendit - “põhja, põhja, ida” jne. - siis jõuab ta lõpuks mõnele teisele ristmikule. Kas on võimalik leida juhiste loendit, mis võib olla pikk, mis viib masina samasse kohta, olenemata sellest, kust see alustab? Kui kaart näeb välja nagu Manhattan – tavaline ruudustik –, siis ei, aga võib-olla on sellel palju tupikteid ja ootamatuid pöördeid?

Või teine ​​näide. Teie sõber on takerdunud rägastikusse, kus tal on vaja keskus leida, ja ta helistas teile abi paludes. Sa tead, kuidas labürint töötab, aga sa ei tea, kus su sõber on. Kas võib olla käskude jada, mis toob teie sõbra kindlasti keskmesse, kus iganes ta ka poleks?

Nendes kahes näites on iga punkti "suunad" fikseeritud ja lahendus kas on olemas või mitte. Kuid üldisemalt küsib see probleem: kui saame valida, kuhu näiteks "lääne, põhja, ida, lõuna" igal ristmikul erinevalt osutab, kas saame siis tagada "sünkroonimissõna" olemasolu - käskude jada, mis mõni koht viib ühe fikseeritud?

Üldjuhul olgu siis suunatud graaf G, mille tippude vahel on “nool” servad. Olgu sellel graafikul ühtlane välisaste d – see tähendab, et igal tipul on täpselt d serva. Sel juhul saab sisestada iga üksiku tipu erinevad kogused, valikuline d. Olgu meil mingi tähestiku d-tähtede komplekt, mida me nimetame “värvideks”. Seejärel antakse graafi “värvus”, määrates igale tipule selle d väljuvatele servadele kõik d tähed. Nii et kui me "oleme" mõnes tipus ja tahame kuhugi "minna" vastavalt värvile α, siis värvimine ütleb meile alati, millise serva ja millise uude tippu peame minema. "Sõna" on mis tahes tähtede-värvide jada. Siis, kui graafis on antud värvus ja x on mingi tipp ja w on mingi sõna, siis xw tähistab tippu, kuhu jõuame alustades x-st ja järgides sõna w.

Värviraamatut nimetatakse sünkroonimine, kui on olemas sõna w, mis viib mis tahes tipu x ühte fikseeritud tippu x 0 . Sel juhul nimetatakse w sünkroniseeriv sõna. Teede värvimise probleemi esitab küsimus: kas alati on sünkroniseeriv värvimine? Kas graafi servi saab alati värvida nii, et kõik tipud saaks taandada üheks?

Sellel probleemil on rakendusi mitmes erinevas valdkonnas, mille kohta saab lugeda näiteks Vikipeediast. Oletame, et arvutiteaduses, automaatide teoorias. Värvimisgraafikut võib käsitleda kui deterministlikku lõplikku automaati, mille tipud on olekud ja servad näitavad, kuidas nende vahel liikuda. Oletame, et me juhime seda masinat distantsilt, saates käsklusi mingi infokanali kaudu ja mõne rikke tõttu oli see kanal saastunud, sai masin mõned ekslikud juhised ja nüüd me isegi ei tea, mis olekus see on. Seejärel saame sünkroonimissõna olemasolul viia selle teadaolevasse olekusse, olenemata sellest, kus see praegu asub.

Millal siis sünkroonimisvärvimine eksisteerib? Tee värvimise oletus seab graafile veel kaks piirangut (lisaks sellele, et igal tipul on täpselt d serva). Esiteks peab graaf olema tugevalt ühendatud – see tähendab, et igast tipust igasse teise on marsruut. Teiseks ei tohi graafik olla perioodiline. Kujutagem ette, et kõik graafi tipud saab jagada hulkadeks V 1, V 2, ... V n, nii et mis tahes graafi serv ühendab tippe mõnest Vi ja Vi+1 või V n ja V 0. Igas V-s pole tippude vahel servi ja nad ei saa ka ühegi V vahel "hüpata", ainult järjekorras. Sellist graafikut nimetatakse perioodiliseks. Selge on see, et sellisel graafikul ei saa olla sünkroniseerivat värvingut, sest olenemata sellest, kuidas sa seda värvid ja mis sõnu kasutad, ei tule kaks erinevas V i-s olevat tippu kunagi kokku - need kõnnivad tsüklis edasi.

Tee värvimise teoreem ütleb, et need tingimused on piisavad: igal mitteperioodilisel, tugevalt seotud suunatud graafil, mille igast tipust on d servad, on sünkroniseeriv värv. Esimest korda sõnastati see hüpoteesina 1970. aastal ja sellest ajast peale on erijuhtumeid tõestanud palju osatulemusi, kuid täielik tõestus ilmus alles 2007. aastal. Järgneb minu peaaegu kogu tõestuse ümberjutustamine (välja arvatud üks tehniline lemma).

Perioodilisus

Kõigepealt asendagem mitteperioodilisuse tingimus teise samaväärsega. Graafik on perioodiline siis ja ainult siis, kui on olemas arv N>1, millega jagatakse graafiku mis tahes tsükli pikkus. Need. meie mitteperioodilisuse nõue on võrdne tõsiasjaga, et sellist N ei ole, või teisisõnu, graafiku kõigi tsüklite pikkuste suurim ühisjagaja on 1. Tõestame, et igal graafikul, mis seda tingimust rahuldab, on värvimise sünkroniseerimine.

Selle tõestamine, et perioodilisus on samaväärne tingimusega "on N>1, millega iga tsükli pikkus on jagatud", on ühes suunas triviaalne ja teises suunas lihtne. Kui olete valmis seda uskuma, võite ülejäänud lõigu hõlpsalt vahele jätta. Kui graafik on perioodiline, s.t. oskab jagada tipud hulkadeks V 1, V 2, ... V n, nii et servad lähevad nende vahele mööda tsüklit, siis on ilmne, et iga tsükli pikkus peab jaguma n-ga, s.t. uus tingimus on täidetud. See on triviaalne suund, kuid meie asendamiseks vajame ainult teist suunda. Oletame, et on N>1, millega jagatakse iga tsükli pikkus. Ehitame oma graafikusse mingi suunatud ulatuva puu, mille juur asub tipus r. Mis tahes tipuni x on selles puus marsruut, mis algab pikkuse l(x) juurest. Nüüd väidame, et graafiku mis tahes serva p-->q korral kehtib l(q) = l(p) + 1 (mod N). Kui see väide on tõene, siis sellest järeldub kohe, et saame jaotada kõik tipud hulkadeks V i vastavalt l(x) mod N ja graafik on perioodiline. Miks see väide tõele vastab? Kui p-->q on osa ulatuvast puust, siis on see ilmne, sest siis lihtsalt l(q) = l(p) + 1. Kui see nii ei ole, siis kirjutame marsruudid juurest r kuni tipud p,q kui R p ja Rq. Olgu ka R r graafikus marsruut q-st tagasi r-i (graaf on ühendatud, seega on see olemas). Siis saame kirjutada kaks tsüklit: R p p-->q R r ja R q R r . Tingimuse kohaselt jagades nende tsüklite pikkused N-ga, lahutades ja vähendades summaarseid väärtusi, saame, et l(p)+1 = l(q) mod N, mis vajaski tõestamist.

Stabiilne sõprus ja sisseelamine

Olgu antud graafikule G teatud värvus tipud p,q sõbrad, kui mõni sõna w toob nad samasse tippu: pw = qw. Helistame p,q vaenlased, kui nad "ei saa kunagi kokku". Nimetagem p,q stabiilseteks sõpradeks, kui nad jäävad pärast mis tahes sõna w täitmist sõpradeks: pw ei pruugi jõuda samasse tippu kui qw, kuid pärast veel mõnda w" võib see tulla. Stabiilsetest sõpradest ei saa kunagi vaenlasi.

Tipude vaheline stabiilsussuhe on esiteks ekvivalentsus (see on refleksiivne, sümmeetriline ja transitiivne) ja teiseks säilib graafi struktuur: kui p, q on stabiilsed sõbrad, on p ühendatud servaga p-ga, q q-ga. ", ja need servad sama värvi, siis p" ja q" on samuti stabiilsed sõbrad. See tähendab, et stabiilne sõprus on kongruentsus ja saab jagada järgmisega: luua uus graaf G", mille tipud on G-s stabiilse sõpruse ekvivalentsusklassid. Kui G-s on vähemalt üks stabiilne paar, siis on G" väiksem kui G. algses graafis G oli igast tipust d serva, siis G" puhul on see nii. Näiteks kui P on uue graafi tipp, mis on algsete tippude p1, p2 ekvivalentsusklass... , ja α on suvaline värv, siis servad p1--α--> q1, p2---α-->q2 jne viivad kõik tippudesse q1, q2..., mis on omavahel stabiilses sõpruses , ja asuvad seetõttu ühes uues tipus Q, nii et kõik need servad muutuvad uueks servaks P --α-->Q Ja nii edasi iga d värvi jaoks.

Veelgi enam, kui G oli mitteperioodiline, siis on ka G" nii. Lõppude lõpuks – kasutades meie alternatiivset perioodilisuse definitsiooni – muutub iga tsükkel G-s tsükliks G", nii et kui kõik G" tsüklite pikkused on jagub arvuga n > 1, siis kehtib sama kõigi G tsüklite kohta. Seega tähendab G" perioodilisus G perioodilisust.

Oletame, et meil õnnestus leida G-s sünkroniseeriv värv. Nüüd saab seda kasutada G-s selle värvimise asemel, millega alustasime: iga serv p-->q saab uue värvi vastavalt serva P uuele värvile. -->Q See peaks olema veidi täpsem: graafiku G" igas tipus P antakse kõigi värvide π P mingi permutatsioon: serv, mis oli värvitud värviga α, saab uue värvi π. P (a). Seejärel kasutame algses graafis G igas stabiilsusklassi P tipus p selle servade ümbervärvimiseks sama permutatsiooni π P. Üldiselt võib öelda, et graafiku G uus värvus defineerib mõned uued mõisted "sõprus", "vaen" ja "stabiilsus", mis ei ole algsete mõistetega identsed. Kuid sellest hoolimata, kui kaks tippu p, q olid vanas värvingus stabiilsed sõbrad - nad kuulusid samasse klassi P -, siis jäävad nad ka uues stabiilseteks sõpradeks. Selle põhjuseks on asjaolu, et iga jada w, mis toob p,q ühte tippu, saab "tõlkida" vanast värvimisest uude või vastupidi, kasutades permutatsiooni π P igas tipus p. Kuna p,q on vanas värvingus stabiilsed ja jäävad nii “kogu teekonnani”, siis on iga vahepealne tipupaar p n , q n teel p,q-st ühisesse tippu stabiilne, s.t. asuvad ühe tipu P n sees ja saavad seetõttu sama permutatsiooni π P n .

Uus värvus sünkroniseerub G jaoks, st mingi jada w toob kõik tipud ühte tippu P. Kui nüüd rakendada w uuele G-värvingule, siis kõik tipud koonduvad kuhugi "P sees". Nagu eespool öeldud, kõik tipud klassis P jäävad uues värvingus stabiilseks, mis tähendab, et nüüd saame jätkata w-ga, tuues ikka ja jälle kokku ülejäänud veel eraldiseisvad tipupaarid, kuni kõik koondub üheks tipuks G. Seega sünkroniseerub uus värvus G.

Sellest kõigest järeldub, et teoreemi tõestamiseks piisab, kui tõestada, et igas tingimustele vastavas graafikus on värvus, milles on paar stabiilset sõpra. Sest siis saame graafikult G minna väiksema suurusega graafikule G" ja see vastab ka kõikidele tingimustele. Kasutades induktiivset argumenti, võime eeldada, et väiksemate graafikute puhul on probleem juba lahendatud ja siis sünkroniseeriv värvimine G jaoks" sünkroonib ka G jaoks.

Klikid ja maksimaalsed komplektid

Graafi ja sõna w mis tahes tippude alamhulga A korral tähistab Aw tippude hulka, milleni jõuame alustades kõigist A tippudest ja järgnedes sõnale w. Kui alustame üldiselt kõigist graafi tippudest, siis tähistame seda Gw-ga. Selles tähistuses tähendab sünkroniseeriv värv, et on olemas w, nii et Gw on ühe elemendi hulk.

Kui tippude hulgal A on mõne w puhul vorm Gw ja lisaks on suvalised kaks tippu A-s vaenlased, s.t. ei lähe kunagi kokku, helistagem A-ks klikk. Klikid eksisteerivad, sest me saame alati alustada tervest G-st, võtta paari sõbratippe, läbida neid ühendava w ja vähendada tippude arvu ühe võrra; jätka nii, kuni järele jäävad ainult vaenlased või jääb ainult üks tipp - ka antud juhul klikk, lihtsalt triviaalne.

Kui A on klikk, siis mis tahes sõna w puhul on ka Aw klikk; see on selge, sest vaenlased jäävad vaenlasteks. Kui x on graafiku mis tahes tipp, siis on olemas klikk, mis sisaldab x-i. See tuleneb sellest, et on olemas mingisugune klikk A (vt eelmist lõiku); kui p on selles tipp, siis on p-st x-ni viiv sõna w, sest ühendatud graafik; siis Aw on klikk, mis sisaldab x-i.

Klikid aitavad meil tõestada, et stabiilsete sõpradega on värvimine olemas - eelmise jaotise kohaselt piisab sellest teoreemi tõestamiseks. Kogu selle jaotise jooksul tõestame, et kui on kaks klikki A ja B, nii et kõik nende tipud on ühised, välja arvatud üks A-s ja üks B-s, siis on need kaks tippu stabiilsed sõbrad. Seega taandub probleem klikke A ja B sisaldava värvuse leidmisele.

Klikkide töö paremaks mõistmiseks on kasulik määrata graafiku tippudele kaal. Näitame, et meil on võimalus omistada igale tipule x positiivne kaal w(x), nii et kui mis tahes tipu x jaoks Summa kõigi tippude kaalud, millest alates on x-i servad, siis saame d*w(x), kus d on iga tipu servade arv. See tuleneb lineaaralgebrast ja kui te ei tea, mis on omaväärtus, jätke ülejäänud lõik vahele ja võtke sellise w(x) olemasolu enesestmõistetavaks. Kui M on graafi G maatriks (lahter (i,j) on 1, kui on serv i-->j, ja 0, kui sellist serva pole, siis w(x), nagu ma neid kirjeldasin, on omavektori elemendid vasakule sellel maatriksil on omaväärtus d. Me teame, et selline vektor on olemas, kuna d on omaväärtus: sellel on triviaalne omavektor paremal(1,1,...1) - see tuleneb kohe sellest, et igast tipust tuleb välja täpselt d serva.

Kui A on mis tahes tippude hulk, siis w(A) tähistab kõigi A-st pärit tippude kaalude summat; ja w(G) on graafi kõigi tippude kaalude summa. Lisaks, kui s on suvaline sõna, siis tähistab As -1 tippude kogumit, kuhu tulete A-st, kui lähete mööda s-i "vastassuunas", asendades igal sammul iga tipu nende tippudega (kui neid on). mis lähevad talle sobivas värvitoonis.

Vaatleme nüüd kõiki tippude hulki, mida saab ühte punkti kokku viia, s.t. selline A, et mõne w puhul sisaldab Aw ainult ühte tippu. Neid hulki A, millel on kõigist sellistest hulkadest maksimaalne kaal w(A), nimetatakse maksimaalseteks hulkadeks. Kui värvimine on sünkroniseeriv, siis on kogu graafik G maksimaalne hulk (unikaalne), kuid muidu ei ole.

Kui A on mis tahes tippude hulk, siis kõigi w(Aα -1) summa, kus α jookseb üle kõigi d värvide, on võrdne d*w(A) - see on lihtsalt kaalu põhiomaduse üldistus. üks tipp tippude hulgale A. Kui lisaks on sel juhul A maksimaalne hulk, siis ei saa iga w(Aα -1) olla suurem kui w(A), sest ka need hulgad taandatakse üheks tipuks . Ja kuna nende kaalude summa d on võrdne d*w(A), siis selgub, et igaüks neist on võrdne w(A) ja kõik need hulgad on samuti maksimaalsed. Sellest järeldub kohe, et kui A on maksimaalne, siis Aw -1 on ka maksimaalne mis tahes sõna w korral.

Maksimaalsed komplektid on kasulikud, kuna nende mitteühendatud eksemplarid võivad katta kogu graafiku. Tõestame seda.

Olgu meil hulk maksimaalseid hulki A 1 ...A n , mis on paarikaupa disjungeeritud ja taandatud üksikuteks tippudeks a 1 ...a n sama sõna w võrra (esialgsel juhul on n=1 ja ainult üks seadistada, et seda oleks lihtne alustada). On selge, et kõik a 1 ...a n on üksteisest erinevad, sest vastasel juhul oleks võimalik maksimumhulka veelgi laiendada teise sama lõpptipuga elementide tõttu. Oletame, et kõik A i koos ei ole veel ammendanud kõiki G tippe ja olgu x tipp väljaspool kõiki A i . Kuna graafik on ühendatud, on mingi marsruut h vahemikus a 1 kuni x. Siis läheb n maksimaalset hulka A i h -1 w -1 sõna whw järgi lõpptippudesse a 1 ...a n ja maksimaalne hulk A 1 läheb mingisse tippu Awhw = (Aw)hw = (a 1 h) w = xw. Ka see tipp xw peab erinema kõigist a 1 ...a n , sest vastasel juhul võiks maksimaalset hulka A i täiendada elemendiga x. Ja kuna kõik need n+1 hulka - kõik A i h -1 w -1 pluss A 1 - lähevad mööda whw-d erinevatesse tippudesse, on nad kõik paarikaupa disjunktiivsed. Jätkame seda laiendamist seni, kuni komplektist väljapoole ei jää ühtegi tippu.

Seega saame kogu graafiku G katta disjungeeritud maksimumhulkadega. Kuna need on maksimaalsed, on neil kõigil sama kogu w max ja seetõttu on nende arv levialas N max = w(G)/w max .

Vaatleme nüüd mis tahes komplekti A, mis koosneb paarikaupa vaenlastest. Näiteks klikk on sellise hulga näide (ja sellel on ka vorm Gw). Maksimaalne kogum ei saa sisaldada paari vaenlasi, sest siis ei saaks see läheneda. See tähendab, et N maksimaalsest hulgast koosnevas kattes sisaldab igaüks maksimaalselt ühte liiget A, seega on A suurus maksimaalselt N max . Täpsemalt on see mis tahes kliki suuruse ülempiir.

Olgu A klikk kujul Gw, kus w on mingi sõna. Siis G = Aw -1 ja vastavalt w(G) on võrdne summaga w(aw -1), kus a jookseb läbi kõigi A tippude. Eelmise lõigu kohaselt on liikmete arv mitte suurem kui N max ja iga komplekti aw -1 saab taandada üheks punktiks (punktis a sõnaga w), nii et selle kaal ei ole suurem kui maksimaalne w max . Kuna kogusumma on võrdne w(G) = N max *w max , järeldame, et liikmete arv on täpselt võrdne N max ja iga liige on täpselt võrdne w max . Oleme tõestanud, et kõik klikid on ühesuurused: täpselt N max elementi.

Olgu kaks klikki A ja B, nii et A sees on kõik elemendid B-ga ühised peale ühe: |A| - |A∩B| = 1.

Kuna A ja B on ühesuurused, on meil ka |B| - |A∩B| = 1, st. A-l ja B-l on kõik ühised elemendid, välja arvatud üks tipp p-s A-s ja üks tipp q-s B-s. Tahaksime tõestada, et need tipud p,q on stabiilsed sõbrad. Kui see nii pole, siis mõni sõna w teeb neist vaenlased, s.t. pw ja qw on vaenlased. Nagu ülal näidatud, on ka Aw ja Bw klikid ja on ilmne, et neil on jällegi kõik ühised elemendid, välja arvatud vaenlased pw ja qw. Siis on hulk Aw ∪ Bw paarikaupa vaenlaste hulk. Tõepoolest, selles on kõik Aw elemendid paarikaupa vaenlased, sest see on klikk; sama kehtib ka Bw elementide kohta; ja alles jäi vaid paar pw, qw - ka vaenlased. Kuid sellel komplektil on N max +1 elementi ja eespool näitasime, et paarikaupa vaenlaste komplektis ei saa olla rohkem kui N max elementi. See on vastuolu ja seetõttu ei saa pw ja qw olla ühegi w vaenlased. Teisisõnu, p ja q on stabiilsed sõbrad.

Piiravad graafikud ja klikid

Võtame antud graafi G kõik tipud ja valime igast tipust ainult ühe väljuva serva. See valik määrab alamgraafi, mida me kutsume ulatuv graafik(läbiv graafik). Erinevaid ulatuvaid graafikuid võib olla palju, kuid mõelgem veidi, millised need välja näevad. Olgu olemas teatud ulatuv graaf R. Kui võtame selles suvalise tipu x ja hakkame järgima selle servi, siis on meil iga kord üksainus valik, sest R-s tuleb igast tipust välja ainult üks serv ja varem või hiljem sulgeme tsükli. Võib-olla see tsükkel ei sulgu x juures, vaid sulgub kuskil “kaugemal” - näiteks x-->y-->z-->s-->y. Siis viib selle tsükli “saba” x-st. Kui alustame mõnest teisest tipust, jõuame kindlasti ka tsüklini - selle või mõne teise. Selgub, et mis tahes tipp R asub tsüklil (mida võib olla mitu) või on osa tsüklisse viivast “sabast”. See tähendab, et R näeb välja selline: teatud arv tsükleid ja neile on ehitatud teatud arv "ümberpööratud" puid: iga puu ei alga, vaid lõpeb "juurega", mis asub ühel tsüklitest.

Saame omistada graafiku igale tipule tasemel, mis vastab selle kaugusele tsüklist antud ulatusgraafikus R. Tsüklil asuvate tippude tase on 0 ja tsükliga seotud puul asuvad tipud saavad taseme, mis on võrdne nende puu kaugusega "juurest". ” lamades tsiklil. Mõnel meie graafiku tipul on maksimaalne tase L. Võib-olla on see isegi võrdne 0-ga – s.o. puid pole, ainult tsiklid. Võib-olla on see suurem kui null ja selle maksimumtaseme tipud asuvad kõikvõimalikel erinevatel puudel, mis on ühendatud erinevate tsüklitega või ühega.

Soovime valida ulatuva graafiku R sellise, et kõik maksimaalse taseme tipud lebasid samal puul. Intuitiivselt võite uskuda, et seda saab teha, sest kui see nii ei ole - näiteks on need erinevate puude vahel hajutatud -, saate valida ühe nendest maksimaalsetest tippudest x ja suurendada selle taset, kinnitades R-le mõne serva. kuni x. Siis tuleb mõni teine ​​ribi välja visata ja see pole tõsiasi, et see midagi muud ei kahjusta... aga see on tehniline probleem, millest tuleb hiljem juttu. Üritan lihtsalt öelda, et see ei tundu intuitiivselt kuigi keeruline.

Oletame praegu, et saame valida R nii, et kõik maksimumtaseme tipud asuvad samal puul. Eeldatakse, et see puu on mittetriviaalne, st. maksimaalne tase L > 0. Selle eelduse põhjal konstrueerime värvingu, milles on eelmise jaotise tingimustele vastavad klikid A ja B ning see tõestab, et selles värvingus on stabiilne paar sõbrad.

Värvimine on järgmine: vali mõni värv α ja värvi kõik graafiku servad R selle värviga ja kõik teised graafiku G servad mõne muu värviga mis tahes viisil (kui on ainult üks värv, siis R langeb kokku G-ga, seega pole probleemi). Seega sõnad, mis koosnevad värvist α, "tõukavad" R tipud mööda oma puid tsüklite suunas ja juhivad need seejärel läbi tsüklite. Need on ainsad sõnad, mida me vajame.

Olgu x suvaline R-i maksimaalse taseme L tipp ja K on suvaline klikk, sealhulgas x; me teame, et selline klikk on olemas. Kas K võib sisaldada mõnda teist maksimumtaseme L tippu? Meie eelduse kohaselt on kõik sellised tipud samas puus nagu x, mis tähendab, et sõna α L viib nad samasse kohta kui x – nimelt selle puu juure, mis asub tsüklil. See tähendab, et kõik sellised tipud on x-i sõbrad ega saa seetõttu asuda temaga samas klikis. Seetõttu võib K lisaks x-ile sisaldada ainult madalama taseme tippe.

Vaatame hulka A = Kα L-1. See on ka klikk ja selles on kõik tipud, välja arvatud x, jõudnud R-s mingisugusesse tsüklisse, sest kõik A tipud, välja arvatud x, on tasemega väiksem kui L. Ainult x jääb tsüklist väljapoole, kell kaugus täpselt 1 selle juureni tsüklil. Nüüd võtame mõne arvu m, mis on kõigi R tsükli pikkuste kordne – näiteks kõigi tsükli pikkuste korrutis. m-il on selline tunnus, et kui tipp y on tsüklis R, siis sõna α m tagastab selle oma kohale: yα m = y. Vaatame klikki B = Aα m . Kõik A tipud, välja arvatud x, lebasid tsüklitel ja jäid seetõttu sinna B-sse; ja alles x astus lõpuks oma tsüklisse ja asus sinna kuhugi. See tähendab, et A ja B lõikepunkt sisaldab kõiki A tippe, välja arvatud üks: |A| - |A∩B| = 1. Kuid see tähendab eelmise jaotise kohaselt lihtsalt seda, et meie värvimisel on stabiilne paar, mida me pidime tõestama.

Maksimaalse taseme ehitamine.

Jääb üle tõestada, et alati on võimalik valida ulatuv graaf R nii, et selle mittetriviaalne maksimumtase L > 0 ja kõik selle taseme tipud asuvad samal puul.

Osa sellest tõendist on üsna igav ja tehniline lemma, mida lugesin ja kontrollisin, aga ei hakka seda kordama, vaid ütlen huvilistele lihtsalt ära, kus see artiklis asub. Aga ma ütlen teile, kuidas selle lemma juurde jõuda.

Meil on vaja kahte piirangut, mida saame graafikule G kehtestada. Esiteks oletame, et G-l pole silmust, st. servad tipust samasse tippu. Asi on selles, et kui graafikul on silmus, siis on väga lihtne leida sünkroniseerivat värvingut muul viisil. Värvime selle ahela mõne värvi α ja seejärel, minnes sellest tipust vastassuunas "noolte vastu", värvime servad nii, et värv α viib alati sellesse tippu. Kuna graaf on ühendatud, on seda lihtne korraldada ja siis tagab silmus, et teatud määral α taandab kogu graafik selle tipuni.

Järgmiseks oletame sekundiks, et mõnest tipust p viivad kõik d servad samasse tippu q. See on tingimustega lubatud, kuid sel juhul nimetame seda servade kogumit kamp. Meie teine ​​piirang on järgmine: pole ühtegi tippu r, kuhu viivad kaks linki erinevatest tippudest p ja q. Miks me saame seda kehtestada? Sest kui p-st ja q-st on seoseid r-is, siis mis tahes p,q värvimine koonduvad tipus r pärast esimest värvi ja seetõttu on nad stabiilsed sõbrad. Nii et sel juhul pole meil vaja kogu ulatuvate graafikute ja klikkide konstrueerimist, saame kohe stabiilsed sõbrad. Seetõttu võime eeldada, et see pole nii.

Lõpuks tõestame, et alati on olemas ulatuv graaf R, mille kõik tipud ei asu tsüklitel, kuid leidub ka mittetriviaalseid puid. Valime mõne R ja eeldame, et kõik selle tipud asuvad tsüklitel. Kui kõik graafi G servad oleksid ühendatud, s.t. alati kõik d servad, mis lahkuvad samast tipust, viivad samasse tippu - siis R valik hõlmaks igast lingist ühe serva valimist. Sel juhul võiks R-s olla ainult üks tsükkel (lõppude lõpuks ei saa mitu tsüklit R-s olla omavahel ühendatud graafis G - kõik G servad ühendavad ainult samu tippe, mis R servad, sest need on konnektiivid - ja kuna G on ühendatud, siis see on võimatu) ja iga tsükkel G-s valib lihtsalt selle tsükli ühendustest teised servad, kuid sisuliselt on see sama tsükkel, sama pikkusega. Kuid see tähendab, et kõigi G tsüklite pikkused jagavad selle pikkusega, mis on täpselt vastuolus G mitteperioodilisusega. Seetõttu ei saa olla, et G kõik servad asetsevad linkidel, mis tähendab, et seal on mingid kaks serva p-->q R-is ja p-->s väljaspool R-i (vajasime pikka argumenti konnektiivide kohta, tõestamaks, et mõni serv p-st ei asu mitte ainult ulatuvas graafis, vaid viib ka teise tippu s). Seejärel asendame p-->q p-->s-ga ja see "lõhkub" tsükli, luues sellesse mingi ebatriviaalse saba. See saba annab meile uues graafikus mittetriviaalse puu.

Nüüd saame valida kõigi mittetriviaalseid puid sisaldavate ulatuvate graafide R hulgast mõne R, millel on tsüklitel maksimaalne tippude arv. See on sellel on tippe, mis ei ole tsüklitel, kuid lisaks sellele piirangule on tsüklite tippude arv maksimeeritud. Sellel graafikul on mõned maksimaalse taseme L tipud ja võib eeldada, et need on erinevatele juurtele viivatel puudel, vastasel juhul oleme juba saavutanud selle, mida vajame. Valime ühe sellise tipu x. Me tahame muuta graafikut nii, et see tipp muutuks puus pikema marsruudi osaks, mis on pikem kui L, ja teised puud ei muutuks ja siis on maksimaalne tase ainult ühes puus, mida me tahame. Graafiku saate muuta kolmel viisil.

a) võta mõni serv y-->x ja lisa see R-le ning tühista olemasolev serv y-->z;
b) võta serv b-->r, mis on just viimane teekonnal x-st oma tsüklini (r tsüklil), ja viska see minema ning lisa veel mingi b-->z.
c) võtke serv c-->r, mis on tsükli osa, ja visake see ära ning lisage mõni muu c-->z.

Trakhtmani töö 7. lemma tõestab üksikasjalikult, et üks (või mõnel juhul kaks) neist muutustest viib soovitud tulemuseni. Protsess kasutab nii R maksimaalsust (kui mingi muudatus toob kaasa graafiku, mille tippude arv on tsüklitel suurem kui R-s, on see vastuolus selle maksimaalsusega) kui ka ülalpool defineeritud tingimust, mille kohaselt ei ole tippu, kuhu kaks linki viivad. Selle tulemusena saame igal juhul graafi R, milles kõik maksimumtaseme tipud asuvad ühel mittetriviaalsel puul.

Värskendus nädala pärast: Sellegipoolest otsustasin teha selle sissekande täiesti iseseisvaks ja jutustada ümber ka lemma tõestuse, millele eelmises lõigus viitasin. Parem oleks seda teha diagrammi abil, kuid ma ei taha seda joonistada ega artiklist välja rebida, nii et proovin sõnadega. Kujutage ette, et meil on ulatuv graaf R, milles on mittetriviaalsed puud, ja kõigist sellistest graafikutest on maksimaalne tippude arv tsüklitel. Meie eesmärk on teisendada R haaravaks graafiks, milles kõik maksimaalse taseme tipud asuvad samal puul; Niipea kui proovimise käigus saame sellise graafiku, lõpetame kohe (ja meid ei huvita, et graafiku maksimumi tippude arvu osas tsüklitel võib kaduma minna, see pole meile oluline ise, kasutame seda ainult protsessis). Olgu x maksimaalse taseme L tipp, T puu, millel see asub, r tipp tsüklil C, kus T lõpeb, b-->r viimane serv enne r-i teel x-st tsüklisse C. Võime eeldada, et selle tsükliga liituvad veel mõned puud või teised, millel on L taseme tipud - muidu on kõik juba tehtud. Sellest järeldub, et kui me saame T-st puu, mille element on suurem kui L, ja ei pikenda neid teisi puid, siis oleme valmis.

Esmalt proovime teha ülaltoodud tehte a): võta G-s mingi serv y-->x - see on olemas, sest Graafik on ühendatud ja ilma silmusteta ning ei asu R-s, sest x maksimaalne tase. Lisame selle R-le ja viskame välja mingi y-->z, mis seal enne oli. Kui y asub puul T, siis y-->x sulgeb uue tsükli ja uues graafis on tsüklitel rohkem tippe ja veel on mittetriviaalsed puud (vähemalt need teised, mis olid R-s), mis on vastuolus R maksimaalsusega. Kui y ei asu T-l ja y-->z ei ole osa tsüklist C, siis y-->z eemaldamine seda tsüklit ei katkesta, kuid y-->x lisamine pikendab maksimumi puu T tase vähemalt ühe võrra ja teistel puud ei pikene, nii et oleme valmis. Ülejäänud variant on siis, kui y-->z lamas tsüklil C, mis on nüüdseks katkenud ja on tekkinud uus tsükkel: r-st y-ni, siis y-->x, siis x-st r-ni mööda endist puud. Selle tsükli pikkus on l(ry)+1+L ja vana tsükli C pikkus oli l(ry)+1+l(zr). Uus tsükkel ei saa olla pikem kui vana, see on vastuolus R maksimaalsusega, seega näeme, et L ≤ l(zr), s.o. marsruudi pikkus z-st r-ni vanas ahelas. Teisest küljest on uues graafikus tipu z tase vähemalt l(zr) ja kui see on suurem kui L, siis oleme valmis. Seega võime eeldada, et l(zr)=L. Kokkuvõtteks: eeldame, et a) ei tööta ja siis teame, et y-->z asub tsüklil C, l(zr) = L.

Nüüd proovime operatsiooni b): asenda serv b-->r mõne teise servaga b-->d. Vaatame, kus asub uus tipp d. Kui puul T, siis lõime uue tsükli eelmist katkestamata ja lükkasime ümber R maksimaalsuse. Kui teisel puul, siis on T maksimaalsetel tippudel, sealhulgas x-il, L-st suurem tase ja teised puud ei tee seda ja oleme valmis. Kui mõnes teises tsüklis, mitte C, teeme nüüd koos b)-ga ka a): kuna teame, et y-->z asub C-l, siis see tehe jagab C, kuid mitte uut tsüklit, milleks see on nüüd ühendatud puu T ja sellel puul on nüüd L-st suurema tasemega tipud ja oleme jälle valmis.

Ülejäänud variant on siis, kui b-->d on samuti ühendatud tsükliga C, mõnes muus kohas kui r või samas kohas ja siis d=r. Pärast b-->r asendamist b-->d-ga saime sama olukorra nagu algselt - puu T, taseme L tipp x jne. - ainult puu on nüüd ühendatud tsükliga läbi tipu d. Arvestades nüüd tehtet a) järeldame (eeldusel, et see ei tööta), et l(zd) = L, nii nagu varem järeldasime, et l(zr) = L. Aga kui l(zd) = l( zr), s.t. kaugus tsüklist z-st on sama punktini d ja r, siis on see sama tipp: d=r. Seega, kui b) ei tööta, siis peab iga serv b-st viima r-ni, s.t. servad punktist b moodustavad lingi.

Lõpuks vaatleme serva c-->r, mis asub tsüklil C. Kuna võib eeldada, et kõik b-st pärinevad servad asuvad lingil, mis viib r-ni, võime kehtestada ka ülalmainitud piirangu, et kahte linki ei saa olla, mis viivad üks tipp, kõik servad c-st ei vii r-ni, vaid on mingi serv c-->e. Asendame c-->r c-->e-ga. Kus võib tipp e asuda? Mitte puul T, sest see "pikendaks" tsüklit C, mis on vastuolus R maksimaalsusega. Seega asub e teisel puul või teisel tsüklil või isegi samal tsüklil C, kuid mitte tipus r. Siis pikendatakse puud T, enne kui see tsükliga liitub, vähemalt ühe r-st lähtuva serva võrra ja võib-olla rohkemgi (ainult ühe võrra, kui e asub vahetult pärast r-i ja c-->e sulgeb tsükli C uuesti, tuletades sellest ainult r). See tähendab, et tipu x ja teiste maksimaalsete tippude T tase ei ole nüüd väiksem kui L+1 ja teised puud pole pikenenud ning saime jälle selle, mida vajame.