Malebog vej. Download lige vej til biler

(dette indlæg kan være interessant for læsere med viden om matematik og sympatisører)

Forleden læste jeg om et interessant problem fra grafteorien - formodningen om vejfarve. Denne formodning har været åben i 37 år, men for tre år siden blev den bevist af den israelske matematiker Abraham Trachtman. Beviset viste sig at være ret elementært, og med nogle vanskeligheder (da mine hjerner havde atrofieret) kunne jeg læse og forstå det, og jeg vil endda forsøge at forklare det i dette indlæg.

Problemet kan forklares med følgende eksempel. Forestil dig et bykort, hvor du ved hvert kryds kan gå i en af ​​fire retninger - nord, syd, øst og vest. Hvis bilen starter fra et kryds og følger en liste med instruktioner - "nord, nord, øst" osv. - så kommer hun til sidst til et andet vejkryds. Er det muligt at finde en liste over anvisninger, muligvis lang, der fører maskinen til det samme sted, uanset hvor den starter? Hvis kortet ligner Manhattan - et almindeligt gitter - så nej, men måske har det en masse blindgyder og uventede vendinger?

Eller et andet eksempel. Din ven sidder fast i en labyrint, hvor han skal finde centrum, og han ringede til dig og bad om hjælp. Du ved, hvordan labyrinten fungerer, men du ved ikke, hvor din ven er. Kunne der være en række kommandoer, der helt sikkert vil bringe din ven til centrum, uanset hvor han er?

I disse to eksempler er "retningerne" på hvert punkt faste, og der findes en løsning, eller også findes den ikke. Men mere generelt spørger dette problem: Hvis vi kan vælge, hvor f.eks. "vest, nord, øst, syd" peger forskelligt i hvert kryds, kan vi så sikre eksistensen af ​​et "synkroniseringsord" - en sekvens af kommandoer, der ethvert sted vil føre til en fast?

I det generelle tilfælde, lad der være en rettet graf G med "pile" kanter mellem hjørnerne. Lad denne graf have ensartet udgrad d - det betyder, at hvert toppunkt har nøjagtigt d kanter. I dette tilfælde kan et andet tal indtaste hvert enkelt toppunkt, ikke nødvendigvis d. Lad os have et sæt d-bogstaver i et eller andet alfabet, som vi vil kalde "farver". Så er "farvningen" af grafen givet ved at tildele for hvert toppunkt alle d bogstaver for dets d udgående kanter. Så hvis vi "er" ved et eller andet toppunkt og ønsker at "gå" et sted i henhold til farven α, så vil farvelægningen altid fortælle os, hvilken kant vi skal gå til hvilket nyt toppunkt. Et "ord" er enhver sekvens af bogstaver-farver. Så, hvis der er givet en farve i grafen, og x er et toppunkt og w er et ord, så angiver xw det toppunkt, som vi kommer til fra x og efter ordet w.

Malebogen hedder synkronisering, hvis der er et ord w, der fører et hvilket som helst toppunkt x til et fast toppunkt x 0 . I dette tilfælde kaldes w synkroniserende ord. Spørgsmålet fra vejfarveproblemet er: er der altid en synkroniserende farvning? Er det altid muligt at farve kanterne på en graf på en sådan måde, at alle hjørner kan reduceres til én?

Dette problem har applikationer på flere forskellige områder, som f.eks. kan læses om på Wikipedia. Lad os sige, i datalogi, i automatteori. En farvelægningsgraf kan opfattes som en deterministisk endelig automat, hvor hjørnerne er tilstande, og kanterne angiver, hvordan man bevæger sig mellem dem. Antag, at vi kontrollerer denne maskine på afstand, sender kommandoer gennem en informationskanal, og på grund af nogle nedbrud var denne kanal forurenet, maskinen modtog nogle fejlagtige instruktioner, og nu ved vi ikke engang, hvilken tilstand den er i. Så, hvis der er et synkroniseringsord, kan vi bringe det til en kendt tilstand, uanset hvor det er nu.

Så hvornår eksisterer synkroniseringsfarvning? Formodningen om vejfarve pålægger grafen yderligere to begrænsninger (udover det faktum, at hvert hjørne har nøjagtigt d kanter). For det første skal grafen være stærkt forbundet - det betyder, at der er en rute fra et hvilket som helst toppunkt til et hvilket som helst andet. For det andet må grafen ikke være periodisk. Lad os forestille os, at alle hjørnerne i grafen kan opdeles i sæt V 1, V 2, ... V n, så enhver kant på grafen forbinder hjørner fra nogle Vi og Vi+1 eller V n og V 0. Der er ingen kanter mellem hjørnerne i hvert V, og de kan heller ikke "hoppe" mellem et hvilket som helst V, kun i rækkefølge. Sådan en graf kaldes periodisk. Det er klart, at sådan en graf ikke kan have en synkroniserende farvning, for uanset hvordan du farver den og uanset hvilke ord du bruger, vil to hjørner i forskellige V i aldrig komme sammen - de vil fortsætte med at gå i en cyklus.

Vejfarvesætningen siger, at disse forhold er tilstrækkelige: enhver ikke-periodisk, stærkt forbundet rettet graf med d kanter fra hvert toppunkt har en synkroniserende farve. Den blev først formuleret som en hypotese i 1970, og siden da har der været mange delresultater, der beviser særlige tilfælde, men det fulde bevis kom først i 2007. Det følgende er min genfortælling af næsten hele beviset (bortset fra ét teknisk lemma).

Periodicitet

Lad os først og fremmest erstatte ikke-periodicitetsbetingelsen med en anden tilsvarende. En graf er periodisk, hvis og kun hvis der er et tal N>1, som længden af ​​enhver cyklus i grafen divideres med. De der. vores ikke-periodicitetskrav svarer til, at der ikke er et sådant N, eller med andre ord, den største fælles divisor af længderne af alle cyklusser i grafen er 1. Vi vil bevise, at enhver graf, der opfylder denne betingelse, har en synkronisering af farvning.

At bevise, at periodicitet svarer til betingelsen "der er N>1, som længden af ​​enhver cyklus er divideret med" er trivielt i den ene retning og let i den anden. Hvis du er villig til at tage dette på tro, kan du nemt springe resten af ​​dette afsnit over; det betyder ikke noget for resten af ​​beviset. Hvis grafen er periodisk, dvs. kan opdele hjørnerne i mængder V 1, V 2, ... V n, så kanterne går mellem dem langs en cyklus, så er det indlysende, at længden af ​​enhver cyklus skal være delelig med n, dvs. den nye tilstand er opfyldt. Dette er en triviel retning, men til vores erstatning har vi kun brug for den anden retning. Antag, at der er N>1, som længden af ​​enhver cyklus divideres med. Lad os bygge et rettet spændingstræ i vores graf med roden i toppunktet r. Til ethvert toppunkt x er der en rute i dette træ, der starter fra roden af ​​længden l(x). Vi hævder nu, at for enhver kant p-->q i grafen gælder, at l(q) = l(p) + 1 (mod N). Hvis dette udsagn er sandt, så følger det umiddelbart, at vi kan opdele alle toppunkter i mængder V i ifølge l(x) mod N, og grafen vil være periodisk. Hvorfor er dette udsagn sandt? Hvis p-->q er en del af spændingstræet, så er dette indlysende, for så er l(q) = l(p) + 1. Hvis dette ikke er tilfældet, så skriver vi ruterne fra roden r til hjørnerne p,q som R p og Rq. Lad også R r angive en rute fra q tilbage til r i grafen (grafen er forbundet, så den eksisterer). Så kan vi skrive to cyklusser: R p p-->q R r , og R q R r . Ifølge betingelsen divideres længderne af disse cyklusser med N, subtrahering og reduktion af de samlede værdier, får vi, at l(p)+1 = l(q) mod N, hvilket er det, der skulle bevises.

Stabilt venskab og induktion

Lad en bestemt farvning af en graf G. Lad os kalde to toppunkter p, q venner, hvis et ord w bringer dem til samme toppunkt: pw = qw. Lad os kalde p,q fjender, hvis de "aldrig finder sammen." Lad os kalde p,q stabile venner, hvis de efter at have udført et ord w forbliver venner: pw kommer måske ikke til samme toppunkt som qw, men efter noget mere w" kan det komme. Stabile venner vil aldrig blive fjender.

Stabilitetsrelationen mellem toppunkter er for det første ækvivalens (den er refleksiv, symmetrisk og transitiv), og for det andet bevaret af grafens struktur: hvis p, q er stabile venner, er p forbundet med en kant til p, q til q ", og disse kanter samme farve, så er p" og q" også stabile venner. Det betyder, at et stabilt venskab er overensstemmelsen og kan divideres med: opret en ny graf G", hvis toppunkter vil være ækvivalensklasser for stabilt venskab i G. Hvis der er mindst ét ​​stabilt par i G, så vil G" være mindre end G. Desuden, hvis i den oprindelige graf havde G fra hvert hjørne d kanter, så i G" vil dette være tilfældet. For eksempel, hvis P er et hjørne af den nye graf, som er ækvivalensklassen for de oprindelige knudepunkter p1, p2... , og α er en hvilken som helst farve, så fører kanterne p1--α--> q1, p2---α-->q2 osv. alle til hjørnerne q1, q2..., som er i stabilt venskab med hver anden, og derfor ligger i ét nyt toppunkt Q, så alle disse kanter bliver en ny kant P --α-->Q. Og så videre for hver af de d farver.

Desuden, hvis G var ikke-periodisk, så er G" også det. Når alt kommer til alt - ved at bruge vores alternative definition af periodicitet - bliver enhver cyklus i G til en cyklus i G", så hvis alle længderne af cyklusserne i G" er deleligt med n > 1, så gælder det samme for alle cyklusser i G. Så periodiciteten af ​​G" indebærer periodiciteten af ​​G.

Lad os antage, at det lykkedes at finde en synkroniserende farvning i G. Den kan nu bruges i G i stedet for den farve, som vi startede med: enhver kant p-->q vil modtage en ny farve i henhold til den nye farve på kanten P -->Q. Det burde være lidt mere præcist, så: ved hvert toppunkt P af grafen G" gives en ny farvning ved en eller anden permutation af alle farver π P: en kant, der var farvet med farve α, modtager en ny farve π P (a). Så i den originale graf G, ved hvert toppunkt p fra stabilitetsklassen P bruger vi den samme permutation π P til at omfarve dens kanter. Generelt set definerer en ny farvning af grafen G nogle nye begreber om "venskab", "fjendskab" og "stabilitet", som ikke er identiske med de oprindelige. Men ikke desto mindre, hvis to hjørner p, q var stabile venner i den gamle farve - de tilhørte samme klasse P - så vil de forblive stabile venner i den nye. Dette skyldes, at enhver sekvens w, der bringer p,q til et toppunkt, kan "oversættes" fra den gamle farve til den nye eller omvendt ved at bruge permutationen π P ved hvert toppunkt p undervejs. Da p,q er stabile i den gamle farve og forbliver det "hele vejen", vil hvert mellemliggende par af knudepunkter p n , q n langs vejen fra p,q til det fælles toppunkt være stabilt, dvs. ligge inde i det ene toppunkt P n og får derfor samme permutation π P n .

Den nye farvning synkroniserer for G", dvs. en sekvens w bringer alle toppunkterne til et toppunkt P. Hvis vi nu anvender w til den nye farvning i G, så vil alle toppunkter konvergere et sted "inde i P". Som nævnt ovenfor, alle toppunkter inden for klassen P forbliver stabile i den nye farvning, hvilket betyder, at vi nu kan fortsætte w, igen og igen samle de resterende stadig adskilte knudepunkter, indtil alt konvergerer til et toppunkt G. Den nye farvning synkroniseres således for G.

Af alt dette følger det, at for at bevise sætningen er det nok at bevise, at der i enhver graf, der opfylder betingelserne, er en farve, hvor der er et par stabile venner. For så kan vi fra graf G gå til graf G" af mindre størrelse, og den opfylder også alle betingelserne. Ved hjælp af et induktivt argument kan vi antage, at for grafer af mindre størrelse er problemet allerede løst, og derefter den synkroniserende farvelægning for G" vil også synkronisere for G .

Kliker og maksimale sæt

For enhver delmængde A af toppunkter i en graf og et ord w, betegner Aw det sæt af toppunkter, som vi vil nå frem til fra alle hjørnerne af A og efter ordet w. Hvis vi starter fra alle hjørner af grafen generelt, så betegner vi dette med Gw. I denne notation betyder en synkroniserende farve, at der er w, således at Gw er et sæt af et element.

Hvis mængden af ​​hjørner A har formen Gw for nogle w, og derudover er to vilkårlige knudepunkter i A fjender, dvs. vil aldrig konvergere, lad os kalde A klike. Kliker eksisterer, fordi vi altid kan starte med hele G, tage et par vennespidser, krydse w, der forbinder dem, og reducere antallet af knudepunkter med én; fortsæt på denne måde, indtil der kun er fjender tilbage eller kun et toppunkt tilbage - også i dette tilfælde en klike, ganske enkelt triviel.

Hvis A er en klike, så er w for ethvert ord også en klike; dette er klart, fordi fjender forbliver fjender. Hvis x er et hvilket som helst toppunkt på grafen, er der en klike med x. Dette følger af, at der er en slags klike A (se forrige afsnit); hvis p er et toppunkt i det, så er der et ord w, der fører fra p til x, fordi forbundet graf; så er Aw en klike inklusive x.

Klik vil hjælpe os med at bevise, at der er en farvning med stabile venner - ifølge det foregående afsnit er dette nok til at bevise sætningen. Gennem dette afsnit vil vi bevise, at hvis der er to kliker A og B, sådan at alle hjørnerne i dem er fælles undtagen en i A og en i B, så er disse to hjørner stabile venner. Således reduceres problemet til at finde en farve, der indeholder klikerne A og B.

For bedre at forstå, hvordan kliker fungerer, er det nyttigt at tildele vægte til hjørnerne i grafen. Lad os vise, at vi har en måde at tildele en positiv vægt w(x) til hvert toppunkt x, sådan at hvis for et hvilket som helst toppunkt x summer vægten af ​​alle hjørner, hvorfra der er kanter i x, så får vi d*w(x), hvor d er antallet af kanter fra hvert toppunkt. Dette følger af lineær algebra, og hvis du ikke ved, hvad en egenværdi er, så spring resten af ​​dette afsnit over og tag eksistensen af ​​en sådan w(x) for givet. Hvis M er en matrix af en graf G (celle (i,j) er 1, hvis der er en kant i-->j, og 0, hvis der ikke er en sådan kant), så er w(x), som jeg beskrev dem, er elementer i egenvektoren venstre denne matrix har for egenværdien d. Vi ved, at en sådan vektor eksisterer, fordi d er en egenværdi: den har en triviel egenvektor til højre(1,1,....1) - dette følger umiddelbart af, at der kommer præcis d kanter ud af hvert toppunkt.

Hvis A er ethvert sæt af hjørner, så betegner w(A) summen af ​​vægtene af alle knudepunkter fra A; og w(G) er summen af ​​vægtene af alle hjørner i grafen. Derudover, hvis s er et hvilket som helst ord, så lad As -1 betegne det sæt af hjørner, som du kommer fra A til, hvis du går "i den modsatte retning" langs s, og ved hvert trin erstatter hvert hjørne med disse hjørner (hvis nogen) der går til hende i den passende farve.

Lad os nu overveje alle de sæt af hjørner, der kan bringes sammen til et punkt, dvs. sådan A, at for nogle w Aw kun indeholder et toppunkt. De sæt A, der blandt alle sådanne sæt har den maksimale vægt w(A), vil blive kaldt maksimale sæt. Hvis farvelægningen synkroniserer, så er hele grafen G et maksimalt sæt (unik), men ellers er det ikke.

Hvis A er et hvilket som helst sæt af hjørner, så er summen af ​​alle w(Aα -1), hvor α løber over alle d farver, lig med d*w(A) - dette er simpelthen en generalisering af vægtens hovedegenskab fra et toppunkt til sættet af toppunkter A. Hvis A desuden i dette tilfælde er en maksimal mængde, så kan hver af w(Aα -1) ikke være større end w(A), fordi disse mængder også er reduceret til et toppunkt . Og da summen d af disse vægte er lig med d*w(A), viser det sig, at hver af dem er lig med w(A), og alle disse sæt er også maksimale. Det følger umiddelbart, at hvis A er maksimal, så er Aw -1 også maksimal for ethvert ord w.

Maksimale sæt er nyttige, fordi usammenhængende forekomster af dem kan dække hele grafen. Lad os bevise det.

Lad os have et sæt maksimale mængder A 1 ...A n , adskilt i par og reduceret til enkelte hjørner a 1 ...a n med det samme ord w (i det indledende tilfælde vil der være n=1 og kun én indstillet, så det er nemt at starte). Det er klart, at alle a 1 ...a n er forskellige fra hinanden, for ellers ville det være muligt at udvide maksimummængden yderligere på grund af elementerne i en anden med samme slutspids. Antag, at alle A i tilsammen endnu ikke har opbrugt alle toppunkterne i G, og lad x være et toppunkt uden for alle A i. Da grafen er forbundet, er der en rute h fra a 1 til x. Så går n maksimale mængder A i h -1 w -1 ifølge ordet whw til de sidste hjørner a 1 ...a n , og den maksimale mængde A 1 går til et eller andet toppunkt Awhw = (Aw)hw = (a 1 h) w = xw. Dette toppunkt xw må også adskille sig fra alle a 1 ...a n , for ellers kunne den maksimale mængde A i suppleres med et element x. Og da alle disse n+1 sæt - alle A i h -1 w -1 plus A 1 - går langs whw til forskellige hjørner, er de alle parvis usammenhængende. Vi fortsætter denne udvidelse, indtil der ikke er nogen hjørner tilbage uden for sættet.

Så vi kan dække hele grafen G med usammenhængende maksimalmængder. Da de er maksimale, har de alle det samme hele w max , og derfor er deres antal i dækningen N max = w(G)/w max .

Overvej nu ethvert sæt A, der består af parvise fjender. For eksempel er en klike et eksempel på et sådant sæt (og har også formen Gw). Et maksimalt sæt kan ikke indeholde et par fjender, for så kunne det ikke konvergere. Det betyder, at i en dækning af N max maksimale sæt indeholder hver højst et element A, så størrelsen af ​​A er højst N max . Konkret er det en øvre grænse for størrelsen af ​​enhver klike.

Lad A være en klike af formen Gw, hvor w er et ord. Så er G = Aw -1, og derfor er w(G) lig med summen w(aw -1), hvor a løber gennem alle hjørnerne af A. Antallet af led er ifølge det foregående afsnit ikke mere end N max, og hvert sæt aw -1 kan reduceres til et punkt (i punkt a med ordet w), så dets vægt ikke er større end den maksimale w max . Da hele summen er lig med w(G) = N max *w max , konkluderer vi, at antallet af led er nøjagtigt lig med N max , og hvert led er nøjagtigt lig med w max . Vi har bevist, at alle kliker har samme størrelse: nøjagtigt N max elementer.

Lad der være to kliker A og B, således at alle elementer inden for A er fælles med B undtagen én: |A| - |A∩B| = 1.

Da A og B har samme størrelse, har vi også |B| - |A∩B| = 1, dvs. A og B har alle elementer til fælles, bortset fra et toppunkt p i A og et toppunkt q i B. Vi vil gerne bevise, at disse toppunkter p,q er stabile venner. Hvis dette ikke er tilfældet, så gør et eller andet ord w dem til fjender, dvs. pw og qw er fjender. Som vist ovenfor er Aw og Bw også kliker, og det er tydeligt, at de igen har alle elementer til fælles, bortset fra fjenderne pw og qw. Så er sættet Aw ∪ Bw sættet af parvise fjender. Ja, i den er alle elementerne i Aw parvise fjender, fordi det er en klike; det samme gælder for Bw-elementerne; og kun parret pw,qw var tilbage - også fjender. Men dette sæt har N max +1 elementer, og ovenfor viste vi, at ethvert sæt af parvise fjender ikke kan have mere end N max elementer. Dette er en selvmodsigelse, og derfor kan pw og qw ikke være fjender af nogen w. Med andre ord er p og q stabile venner.

Omspændende grafer og kliker

Lad os tage alle hjørnerne fra en given graf G og kun vælge én udgående kant fra hvert hjørne. Dette valg bestemmer en undergraf, som vi kalder spændende graf(spændende graf). Der kan være mange forskellige spændende grafer, men lad os tænke lidt over, hvordan de ser ud. Lad der være en bestemt spændende graf R. Hvis vi tager et hvilket som helst toppunkt x i den og begynder at følge dets kanter, så vil vi hver gang have et enkelt valg, fordi der i R kun kommer én kant ud af hvert toppunkt, og før eller senere vil vi lukke cyklus. Måske vil denne cyklus ikke lukke ved x, men lukke et sted "længere" - for eksempel x-->y-->z-->s-->y. Så vil "halen" til denne cyklus føre fra x. Hvis vi starter fra et andet toppunkt, ender vi også helt sikkert med en cyklus - denne eller en anden. Det viser sig, at ethvert toppunkt R enten ligger på en cyklus (som der kan være flere af), eller er en del af den "hale", der fører til en cyklus. Det betyder, at R ser sådan ud: et vist antal cyklusser, og et vist antal "omvendte" træer er bygget på dem: hvert træ begynder ikke, men slutter ved "roden", som ligger på en af ​​cyklusserne.

Vi kan tildele hvert hjørne af grafen niveau, svarende til dens afstand til cyklussen i en given spændingsgraf R. Toppunkter, der ligger på cyklussen, har niveau 0, og toppunkter, der ligger på træet, der er knyttet til cyklussen, modtager et niveau, der er lig med afstanden i deres træ til "roden" ” liggende på cyklus. Nogle hjørner af vores graf har et maksimalt niveau L. Måske er det endda lig med 0 - dvs. der er ingen træer, kun cyklusser. Måske er det større end nul, og hjørnerne af dette maksimale niveau ligger på alle mulige forskellige træer, forbundet med forskellige cyklusser eller til en.

Vi ønsker at vælge en spændende graf R således, at alle hjørner af det maksimale niveau lå på det samme træ. Intuitivt kan man tro, at dette kan lade sig gøre, for hvis dette ikke er tilfældet - for eksempel er de spredt ud over forskellige træer - så kan man vælge et af sådanne maksimale toppunkter x og øge dets niveau ved at fastgøre en kant til R til x. Så skal nogle andre ribben smides ud, og det er ikke en kendsgerning, at det ikke vil skade noget andet... men dette er et teknisk problem, som vil blive diskuteret senere. Jeg prøver bare at sige, at det intuitivt ikke virker særlig kompliceret.

Lad os indtil videre antage, at vi kan vælge R, så alle toppunkterne på det maksimale niveau ligger på det samme træ. Dette træ antages at være ikke-trivielt, dvs. det maksimale niveau L > 0. Ud fra denne antagelse vil vi konstruere en farvning, og i den er der kliker A og B, der opfylder betingelserne i det foregående afsnit, og dette vil bevise, at der i denne farvning er et stabilt par af venner.

Farvningen vil være som følger: vælg en farve α, og farve alle kanterne i grafen R med denne farve, og alle andre kanter i grafen G med nogle andre farver på nogen måde (hvis der kun er én farve, så R falder sammen med G , så der er ikke noget problem). Ord, der består af farven α, "skubber" således hjørnerne af R langs deres træer mod cyklerne og driver dem derefter gennem cyklerne. Det er de eneste ord, vi får brug for.

Lad x være et hvilket som helst toppunkt på maksimalt niveau L i R, og lad K være en hvilken som helst klike inklusive x; vi ved, at sådan en klike findes. Kan K inkludere et andet toppunkt for det maksimale niveau L? Ifølge vores antagelse er alle sådanne hjørner i samme træ som x, hvilket betyder, at ordet α L fører dem til samme sted som x - nemlig til roden af ​​dette træ, som ligger på cyklussen. Det betyder, at alle sådanne hjørner er venner af x, og derfor ikke kan ligge i samme klike som den. Derfor kan K udover x kun omfatte toppunkter på et lavere niveau.

Lad os se på mængden A = Kα L-1. Dette er også en klike, og i den har alle hjørnerne, undtagen x, nået en form for cyklus i R, fordi alle hjørnerne i A, undtagen x, har et niveau mindre end L. Kun x forbliver uden for cyklussen, kl. en afstand på præcis 1 til dens rod på cyklussen. Lad os nu tage et tal m, der er et multiplum af alle cykluslængder i R - for eksempel produktet af alle cykluslængder. m har en sådan egenskab, at hvis toppunktet y er på en cyklus i R, så returnerer ordet α m det til sin plads: yα m = y. Lad os se på kliken B = Aα m . Alle hjørner af A, undtagen x, lå på cyklusser og forblev derfor der i B; og kun x kom endelig ind i dens cyklus og slog sig ned der et sted. Det betyder, at skæringspunktet mellem A og B indeholder alle hjørner af A undtagen ét: |A| - |A∩B| = 1. Men det betyder bare, ifølge det foregående afsnit, at vores farve har et stabilt par, hvilket vi skulle bevise.

Opbygning af det maksimale niveau.

Det er tilbage at bevise, at det altid er muligt at vælge en spændende graf R, således at den har et ikke-trivielt maksimumniveau L > 0, og alle hjørnerne af dette niveau ligger på det samme træ.

En del af dette bevis er et ret kedeligt og teknisk lemma, som jeg læste og tjekkede, men jeg vil ikke gentage det, jeg vil bare sige, hvor det er i artiklen for dem, der er interesserede. Men jeg vil fortælle dig, hvordan du kommer til dette lemma.

Vi skal bruge to begrænsninger, som vi kan pålægge grafen G. Lad os først sige, at G ikke har nogen sløjfer, dvs. kanter fra et toppunkt til samme toppunkt. Pointen er, at hvis der er en løkke i grafen, så er det meget nemt at finde en synkroniserende farvelægning på en anden måde. Lad os farve denne sløjfe en eller anden farve α, og derefter, gå fra dette toppunkt i den modsatte retning "mod pilene", farve kanterne, så farve α altid fører til dette toppunkt. Fordi grafen er forbundet, er dette let at arrangere, og så sikrer løkken, at en vis grad α vil reducere hele grafen til dette toppunkt.

Antag dernæst et sekund, at fra et eller andet toppunkt p fører alle d kanter til det samme toppunkt q. Dette er tilladt af betingelserne, men i dette tilfælde vil vi kalde dette sæt af kanter flok. Vores anden begrænsning er denne: der er ingen toppunkt r, hvortil to led fra forskellige toppunkter p og q fører. Hvorfor kan vi påtvinge det? For hvis bindeled går fra p og q til r, så vil q for enhver farve p, konvergere ved toppunktet r efter den første farve, og derfor er de stabile venner. Så i dette tilfælde har vi ikke brug for al konstruktionen af ​​spændende grafer og kliker, vi får stabile venner med det samme. Derfor kan vi antage, at dette ikke er tilfældet.

Endelig beviser vi, at der altid eksisterer en spændende graf R, hvor ikke alle toppunkter ligger på cyklusser, men der er nogle ikke-trivielle træer. Lad os vælge noget R og antage, at alle dets toppunkter ligger på cyklusser. Hvis alle kanter i graf G var forbundet, dvs. altid alle d kanter, der forlader det samme toppunkt, førte til det samme toppunkt - så ville valget af R involvere blot at vælge en kant fra hvert led. I dette tilfælde kunne der kun være én cyklus i R (trods alt kunne flere cykler i R umuligt være forbundet med hinanden i en forbundet graf G - alle kanterne på G forbinder kun de samme hjørner som kanterne på R, fordi disse er forbindelser - og da G er forbundet, er dette umuligt), og enhver cyklus i G vælger simpelthen andre kanter fra forbindelserne i denne cyklus, men i bund og grund er det den samme cyklus, af samme længde. Men det betyder, at længderne af alle cyklusser i G er delelige med denne længde, hvilket netop modsiger ikke-periodiciteten af ​​G. Derfor kan det ikke være, at alle kanter i G ligger på led, hvilket betyder, at der er nogle to kanter p-- >q i R, og p-->s uden for R (vi havde brug for et langt argument om connectives for at bevise, at en kant fra p ikke kun ikke ligger i spændingsgrafen, men også fører til et andet toppunkt s). Så erstatter vi p-->q med p-->s, og dette vil "bryde" cyklussen og skabe en form for ikke-triviel hale i den. Denne hale vil give os et ikke-trivielt træ i den nye graf.

Nu kan vi vælge mellem alle spændende grafer R, der indeholder ikke-trivielle træer, nogle R, der har det maksimale antal hjørner i cyklusser. Det er den har toppunkter, der ikke er på cyklus, men udover denne begrænsning er antallet af toppunkter på cykler maksimeret. Der er nogle hjørner af det maksimale niveau L i denne graf, og vi kan antage, at de er på træerne, der fører til forskellige rødder, ellers har vi allerede opnået det, vi har brug for. Lad os vælge et sådant toppunkt x. Vi vil ændre grafen, så dette toppunkt bliver en del af en længere rute i træet, længere end L, og de andre træer ændrer sig ikke, og så vil det maksimale niveau kun være i ét træ, hvilket er det vi ønsker. Du kan ændre grafen på tre måder:

a) tag en kant y-->x og føj den til R, og kasser den eksisterende kant y-->z;
b) tag kanten b-->r, som bare er den sidste på stien fra x til dens cyklus (r på cyklussen), og smid den væk, og tilføj noget andet b-->z.
c) tag kanten c-->r, som er en del af cyklussen, og kasser den, og tilføj noget andet c-->z.

Lemma 7 i Trakhtmans papir beviser i detaljer, at en (eller i nogle tilfælde to) af disse ændringer fører til det ønskede resultat. Processen bruger både maksimaliteten af ​​R (hvis en eller anden ændring fører til en graf med et større antal hjørner på cyklusser end i R, modsiger dette dens maksimalitet), og betingelsen defineret ovenfor, at der ikke er noget toppunkt, hvortil to led fører. Som et resultat får vi under alle omstændigheder en graf R, hvor alle toppunkterne for det maksimale niveau ligger på et ikke-trivielt træ.

Opdatering en uge senere: Jeg besluttede ikke desto mindre at gøre dette indlæg fuldstændigt selvforsynende og også genfortælle beviset på det lemma, som jeg henviste til i det foregående afsnit. Det ville være bedre at gøre dette med et diagram, men jeg vil ikke tegne det eller rive det ud af artiklen, så jeg prøver med ord. Så forestil dig, at vi har en spændende graf R, hvor der er ikke-trivielle træer, og af alle sådanne grafer i den, ligger det maksimale antal hjørner i cyklusser. Vi sigter mod at transformere R til en spændende graf, hvor alle toppunkter af maksimumniveauet ligger på det samme træ; Så snart vi får sådan en graf i færd med at prøve, afslutter vi straks (og vi er ligeglade med, at grafens maksimalitet i form af antallet af hjørner på cyklusser kan gå tabt, det er ikke vigtigt for os i selv, bruger vi det kun i processen). Lad x være toppunktet for det maksimale niveau L, T træet det ligger på, r toppunktet på cyklus C hvor T slutter, b-->r sidste kant før r på stien fra x til cyklus C. Vi kan antage, at der er nogle andre træer, der slutter sig til denne cyklus eller andre, der har toppunkter på niveau L - ellers er alt allerede blevet gjort. Det følger heraf, at hvis vi fra T kan få et træ med et element af større grad end L, og ikke forlænge disse andre træer, så er vi færdige.

Lad os først prøve at udføre operation a) ovenfor: tag en kant y-->x i G - den eksisterer, fordi Grafen er forbundet og uden sløjfer, og ligger ikke i R, pga x maksimalt niveau. Lad os tilføje det til R og smide nogle y-->z ud, der var der før. Hvis y ligger på et træ T, så lukker y-->x en ny cyklus, og i den nye graf ligger flere toppunkter på cyklusser, og der er stadig ikke-trivielle træer (i hvert fald de andre, der var i R), som modsiger maksimaliteten af ​​R. Hvis y ikke ligger på T og y-->z ikke er en del af en cyklus C, så bryder fjernelse af y-->z ikke denne cyklus, men tilføjelse af y-->x forlænger maksimum niveauet af træet T med mindst én, og andre bliver træerne ikke længere, så vi er færdige. Den resterende mulighed er, når y-->z lå på cyklus C, som nu er brudt, og en ny cyklus er dannet: fra r til y, derefter y-->x, så fra x til r langs det tidligere træ. Længden af ​​denne cyklus er l(ry)+1+L, og længden af ​​den gamle cyklus C var l(ry)+1+l(zr). Den nye cyklus kan ikke være længere end den gamle, dette modsiger maksimaliteten af ​​R, så vi ser at L ≤ l(zr), dvs. længden af ​​ruten fra z til r i den gamle sløjfe. På den anden side, i den nye graf, har toppunktet z nu et niveau på mindst l(zr), og hvis dette er større end L, så er vi færdige. Så vi kan antage, at l(zr)=L. For at opsummere: vi antager, at a) ikke virker, og så ved vi, at y-->z ligger på cyklus C, l(zr) = L.

Lad os nu prøve operation b): udskift kanten b-->r med en anden kant b-->d. Lad os se, hvor det nye toppunkt d ligger. Hvis på træet T, så skabte vi en ny cyklus uden at bryde den forrige, og modbeviste maksimaliteten af ​​R. Hvis på et andet træ, så vil de maksimale toppunkter for T, inklusive x, nu have et niveau større end L, og de andre træer vil ikke, og vi er færdige. Hvis på en anden cyklus, ikke C, så vil vi nu sammen med b) også gøre a): da vi ved, at y-->z ligger på C, så vil denne operation opdele C, men ikke den nye cyklus, som den er nu forbundet træ T, og på dette træ vil der nu være toppunkter på et niveau større end L, og vi er færdige igen.

Den resterende mulighed er, når b-->d også er forbundet til cyklus C, et andet sted end r, eller samme sted og så d=r. Efter at vi havde erstattet b-->r med b-->d, fik vi samme situation som oprindeligt - træ T, toppunkt x på niveau L osv. - kun træet er nu forbundet med cyklussen gennem toppunktet d. I betragtning af nu operation a), konkluderer vi (forudsat at det ikke virker), at l(zd) = L, ligesom vi tidligere konkluderede, at l(zr) = L. Men hvis l(zd) = l( zr), dvs. afstanden langs cyklussen fra z er den samme til d og r, så er dette det samme toppunkt: d=r. Så hvis b) ikke virker, så skal enhver kant fra b føre til r, dvs. kanterne fra b danner et led.

Overvej til sidst kanten c-->r, der ligger på cyklus C. Da vi kan antage, at alle kanter fra b ligger på forbindelsen, der fører til r, kan vi også pålægge den ovenfor nævnte begrænsning, at der ikke kan være to led, hvilket fører til et toppunkt, ikke alle kanter fra c fører til r, men der er nogen kant c-->e. Lad os erstatte c-->r med c-->e. Hvor kan vertex e ligge? Ikke på træ T, fordi det ville "forlænge" cyklussen C, hvilket modsiger maksimaliteten af ​​R. Så e ligger på et andet træ eller på en anden cyklus, eller endda på den samme cyklus C, men ikke ved toppunktet r. Så er træet T, før det slutter sig til løkken, nu forlænget med mindst én kant, der udgår fra r, og måske med mere (kun med én, hvis e ligger umiddelbart efter r, og c-->e lukker løkken C igen, der kun udleder r fra det). Det betyder, at toppunktet x og andre maksimale toppunkter T nu har et niveau, der ikke er mindre end L+1, og at andre træer ikke er blevet forlænget, og igen fik vi, hvad vi har brug for.

Takket være Disney og Pixar så hele verden i juni 2006 en tegneserie, hvor kun biler blev heltene.

Bilerne i tegnefilmen Cars lever et almindeligt liv - en driver en dækbutik, en anden driver et tuning-studie, og nogle lever simpelthen for deres egen fornøjelse, som hippie Fillmore (Volkswagen T1) eller hans ven, en veteran fra Anden Verdenskrig. Serge (Willys). Filmens hovedperson, McQueen, med tilnavnet "Lyn", drømmer kun om væddeløb, sejre og ære. En gang i Radiator District på den berømte amerikanske Highway 66 fortæller den stadig "grønne" McQueen straks alle, hvor hurtig og cool han er. Men hans første start i et NASCAR-løb fjerner hans illusioner. Venner hjælper helten med at overleve tabet - den gamle trækvogn Mater (GMC Pick-up), mentor Doc Hudson (Hudson Hornet) og lille Luigi (Fiat 600), der drømmer om at se en rigtig Ferrari.

Nå, hvor ville vi være uden den romantiske skønhed Sally (Porsche med en charmerende 911-tatovering)! I høj grad takket være dem vil McQueen stadig vinde løbet og besejre Chicos vigtigste rival (Plymouth Hemi Cuda). Luigis drøm vil også gå i opfyldelse - en dag kommer en "hingst fra Maranello", der i øvrigt er udtrykt af den "røde baron" selv, Michael Schumacher, til hans butik for at skifte dæk.

Det er bemærkelsesværdigt, at både skaberne af filmen og dem, der har givet udtryk for den, er mennesker involveret i biler. For eksempel tilbragte direktør Joe Lasseter næsten hele sin barndom på Chevrolet-fabrikken, hvor hans far var en af ​​chefdesignerne. Fords førende designer Jay Mays fungerede som konsulent. Ud over den allerede nævnte syvdobbelte Formel 1-verdensmester Michael Schumacher var NASCAR-stjernerne Richard Petty og Paul Newman samt den legendariske racerkører Michael Andretti med til at give udtryk for karaktererne.

Kun den originale støj fra bilerne blev brugt - for eksempel blev lyden, især til racer-episoder, optaget i flere uger på amerikanske ovaler under NASCAR-konkurrencer. Det tog mere end to år at skabe filmen, hvis budget var 70 millioner USD. I løbet af denne tid blev 43 tusinde forskellige skitser af biler skabt, og hver tegning tog mere end 17 timer. Der er i alt 120 bilkarakterer i filmen – fra nye Porscher og Ferrarier til en antik Ford T.

Et barns viden om færdselsreglerne er en af ​​hovedbetingelserne for hans sikkerhed på gaden. Mange fodgængere, herunder voksne, tager disse regler ret let, hvilket ofte bliver årsag til trafikulykker af varierende sværhedsgrad. Børn skal klart forstå, at når de er på gaden i et befolket område, er de fuldgyldige deltagere i vejtrafikken, derfor er overholdelse af færdselsreglerne deres ansvar.

Farvelægningssider Færdselsregler for børn.

At lære et barn reglerne for adfærd på gaden (veje, fortove, bytransport) bør begynde i en meget tidlig alder, før han lærer at gå og løbe på egen hånd. Og her er eksemplet med forældre og andre voksne, som barnet er på gaden med, meget vigtigt. Du skal ikke kun fortælle og forklare færdselsreglerne til dit barn, men også selv nøje overholde dem. Trafikreglernes farvelægningssider præsenteret på denne side er primært beregnet til førskolebørn og vil hjælpe børn med at lære de grundlæggende adfærdspunkter på vejen såvel som i nærheden af ​​den.

1. Farvelægningsside Trafiklys.

Det bedste sted at krydse vejen sikkert er et fodgængerfelt udstyret med et lyskryds. Malesider med billeder af trafiklys indeholder også små rim, der hjælper børn med lettere at huske reglerne for at bruge dem.

• Begynd altid kun at køre, når lyskrydset er grønt.
• Kryds aldrig vejen, når trafiksignalerne er røde eller gule, selvom der ikke er nogen køretøjer i nærheden.
• Når du drejer til grønt lys, skal du desuden sørge for din sikkerhed - se til venstre og derefter til højre.

2. Malebog fodgængerfelt.

Lær dit barn kun at krydse vejbanen ved et fodgængerfelt. Farvelægningssider af fodgængerfelter vil lære børn, hvordan man krydser vejen korrekt. En overgang, der ikke er udstyret med et lyskryds, kaldes ureguleret.

• Fodgængerfeltet er markeret på vejbanen med et krydsfelt.
• Inden du krydser vejen, skal du omhyggeligt inspicere den og sikre dig, at der ikke er trafik i nærheden.
• Kryds vejen, løb ikke over den.
• Kryds ikke gaden diagonalt.
• Vær særlig opmærksom på stationære køretøjer, der blokerer dit udsyn.
• Hold op med at tale i telefon, når du bevæger dig gennem et fodgængerfelt.
• Hvis der er underjordiske eller overkørsler i nærheden, skal du sørge for at bruge dem; trafikken er særlig intens på sådanne steder.

3. Fortove.

Fortovet er beregnet til fodgængertrafik. Lær børn at opføre sig korrekt på fortove, især dem, der er placeret i områder med tæt trafik.

• Når du kører på fortovet langs vejen, må du ikke komme for tæt på det.
• Overvåg omhyggeligt mulige køretøjer, der forlader gårdhaver og stræder.
• Spil ikke bold på fortovet eller løb.

4. Malesider med adfærdsregler for børn i byens offentlige transportmidler og ved busstoppesteder.

Disse farvelægningssider vil lære børn, hvordan man sikkert bruger offentlig transport.

• Et offentligt transportstoppested er et farligt sted på grund af et muligt dårligt udsyn til vejen og en stor menneskemængde, der ved et uheld kan skubbe et barn af fortovet ud på vejbanen. Her skal du være særlig forsigtig.
• Nærm dig først bilens døre, når den er helt standset.
• Når du er steget ud af køretøjet, skal du først krydse vejen, efter at den har forladt stoppestedet.

Ud over disse grundlæggende færdselsregler vil børn være interesserede i at farve vejskilte. De præsenterede trafikregler farvelægningssider er velegnede til småbørn, førskolebørn og folkeskoleelever samt til brug i børnehaver og grundskoletimer. Alle billeder med Trafikregler er helt gratis - du kan downloade og printe dem.

Du kan holde drenge beskæftiget i lang tid, hvis du inviterer dem til at lege med biler i sandkassen. Men hvad skal man gøre, hvis det er koldt udenfor, og barnet keder sig. I dette tilfælde kan du downloade og udskrive følgende vejskabeloner til biler. Det sjove begynder med at skære alle ringe, sving og lige veje ud. Ud fra disse skabeloner kan et barn bygge en vej af enhver form; bare sørg for, at det nødvendige antal påkrævede A4-ark udskrives.

Download lige vej til biler

Du skal bruge mest af disse ark. På et A4-ark har vi placeret 3 veje, der skal printes og klippes ud. Vis dit barn, hvordan man skærer vejen i rette vinkler for at få sektionen til den længde, han har brug for.

Vej til biler: ring

For at forbinde vejene skal du bruge en ring, hvis skabelon er præsenteret ovenfor, og begynd at bygge din infrastruktur derfra.

Vej for biler: ligesving

De præsenterede sving giver drengen mulighed for at dreje vejen 90 grader i den retning, han har brug for.

Ikke et skarpt sving på vejen for biler

Følgende A4-skabelon hjælper dig med at dreje vejen i enhver radius.