(det här inlägget kan vara av intresse för läsare med kunskaper i matematik och sympatisörer)

Häromdagen läste jag om ett intressant problem från grafteorin - vägfärgningsförmodan. Denna gissning har varit öppen i 37 år, men för tre år sedan bevisades den av den israeliske matematikern Abraham Trachtman. Beviset visade sig vara ganska elementärt, och med vissa svårigheter (eftersom min hjärna atrofierades) kunde jag läsa och förstå det, och till och med försöka förklara det i det här inlägget.

Problemet kan förklaras med ett exempel. Föreställ dig en karta över staden, där du vid varje korsning kan åka i en av fyra riktningar - norr, söder, öster och väster. Om bilen startar i någon korsning och följer någon lista med riktningar - "norr, norr, öst" osv. – då kommer hon så småningom fram till någon annan korsning. Är det möjligt att hitta en sådan lista med vägbeskrivningar, kanske en lång, som leder bilen till samma plats, oavsett var den startade? Om kartan ser ut som Manhattan – ett vanligt rutnät – så nej, men det kanske finns många återvändsgränder och oväntade vändningar i den?

Eller ett annat exempel. Din vän har fastnat i en labyrint där du behöver hitta centret och ringde dig och bad om hjälp. Du vet hur labyrinten fungerar, men du vet inte var din vän är. Kan det finnas en sekvens av kommandon som definitivt kommer att leda din vän till centrum, oavsett var han är?

I dessa två exempel är "riktningarna" vid varje punkt fasta, och lösningen finns antingen eller inte. Men i ett mer allmänt fall frågar detta problem: om vi kan välja var till exempel "väst, nord, öst, syd" pekar, vid varje korsning på sitt eget sätt, kan vi då säkerställa att det finns ett "synkroniserande ord" " - en sekvens av kommandon, som från vilken plats som helst kommer att leda till en fixad?

I det allmänna fallet, låt det vara en riktad graf G - med "pil" kanter mellan hörnen. Låt denna graf ha en enhetlig utgående grad d - det betyder att exakt d kanter går ut från varje vertex. Samtidigt kan den gå in i varje enskild vertex olika mängd, valfritt d. Anta att vi har en uppsättning d bokstäver i något alfabet, som vi kommer att kalla "blommor". Sedan ges "färgningen" av grafen genom att tilldela varje vertex alla d bokstäver för d av dess utgående kanter. Så om vi är "lokaliserade" vid någon vertex, och vi vill "gå" någonstans enligt färgen α, så kommer färgningen alltid att tala om för oss vilken kant vi behöver för att gå till vilken ny vertex. Ett "ord" är vilken som helst sekvens av bokstavsfärger. Sedan, om en färgning ges i grafen, och x är någon vertex och w är något ord, så betecknar xw den vertex vi kommer fram till, med början från x och efter ordet w.

Målarboken heter synkronisering, om det finns ett ord w som leder någon vertex x till en fast vertex x 0 . I detta fall kallas w synkord. Frågan som ställs av vägfärgningsproblemet är: finns det alltid en synkron färgläggning? Är det alltid möjligt att färga kanterna på en graf på ett sådant sätt att alla hörn kan reduceras till en?

Detta problem har tillämpningar inom flera olika områden, som man kan läsa om till exempel på Wikipedia. Till exempel inom datavetenskap, inom automatteori. En graf med en färg kan ses som en deterministisk finita tillståndsmaskin där hörnen är tillstånden och kanterna anger hur man navigerar mellan dem. Anta att vi styr den här automaten på avstånd, skickar kommandon över någon informationskanal, och på grund av någon form av haveri var denna kanal förorenad, automaten fick några felaktiga instruktioner och nu vet vi inte alls vilket tillstånd den är i. Sedan, om det finns ett synkord, kan vi föra det till ett känt tillstånd, oavsett var det är nu.

Så när finns synkfärgning? Förmodan om vägfärgning lägger ytterligare två restriktioner på grafen (förutom det faktum att varje vertex har exakt d kanter). Först måste grafen vara starkt sammankopplad, vilket betyder att det finns en rutt från vilken vertex som helst till vilken som helst. För det andra får grafen inte vara periodisk. Föreställ dig att alla grafens hörn kan delas in i mängder V 1 , V 2 , ... V n , så att vilken kant som helst på grafen förbinder hörn från några V i och V i+1 eller V n och V 0 . Det finns inga kanter mellan hörnen i varje V, och de kan inte heller "hoppa" mellan något V, bara i ordning. En sådan graf kallas periodisk. Det är klart att en sådan graf inte kan ha en synkroniserande färgning, för oavsett hur du färgar den och med vilka ord du går, kommer två hörn i olika V i aldrig att mötas - de kommer att gå runt cykeln.

Vägfärgningssatsen säger att dessa förhållanden är tillräckliga: alla icke-periodiska, starkt kopplade riktade grafer med d kanter från varje vertex har en synkroniserande färg. Det formulerades först som en gissning 1970, och sedan dess har det förekommit många delresultat som bevisar särskilda fall, men ett fullständigt bevis dök upp först 2007. Det som följer är min återberättelse av nästan hela beviset (förutom ett tekniskt lemma).

Periodicitet

Låt oss först och främst ersätta icke-periodicitetsvillkoret med ett annat som är likvärdigt med det. En graf är periodisk om och endast om det finns ett tal N>1 som delar längden på en cykel i grafen. De där. vårt krav på icke-periodicitet motsvarar det faktum att det inte finns något sådant N, eller med andra ord, den största gemensamma delaren av längderna av alla cykler i grafen är 1. Vi kommer att bevisa att varje graf som uppfyller detta villkor har en synkroniserande färgläggning.

Att bevisa att periodicitet är likvärdigt med villkoret "det finns N>1 med vilken längden av varje cykel är delbar" är trivialt i en riktning och lätt i den andra. Om du är villig att ta det här på tro kan du enkelt hoppa över resten av det här stycket, det spelar ingen roll för resten av beviset. Om grafen är periodisk, dvs. Eftersom det är möjligt att dela upp hörnen i mängder V 1 , V 2 , ... V n , så att kanterna går mellan dem i en cykel, så är det uppenbart att längden på vilken cykel som helst måste vara delbar med n, d.v.s. det nya villkoret är uppfyllt. Detta är en trivial riktning, men för vår ersättning behöver vi bara den andra riktningen. Antag att det finns en sådan N>1, som delar längden på en cykel. Låt oss i vår graf bygga ett riktat spännträd (spännande träd) med en rot i vertex r. Det finns en rutt till valfri vertex x i detta träd som börjar från roten av längden l(x). Vi hävdar nu att för valfri kant p-->q i grafen, l(q) = l(p) + 1 (mod N). Om detta påstående är sant, så följer det omedelbart av det att vi kan dela upp alla hörn i mängder V i enligt l(x) mod N, och grafen kommer att vara periodisk. Varför är detta påstående sant? Om p-->q är en del av ett spännträd, så är detta uppenbart, för då är bara l(q) = l(p) + 1. Om så inte är fallet, så skriver vi vägarna från roten r till hörnen p,q som R p och R q . Låt även R r betyda rutten från q tillbaka till r i grafen (grafen hänger ihop, så den finns). Då kan vi skriva två cykler: R p p-->q R r , och R q R r . Enligt villkoret är längderna av dessa cykler delbara med N, subtraherar och annullerar de totala värdena, vi får att l(p)+1 = l(q) mod N, vilket skulle bevisas.

Stabil vänskap och induktion

Låt en färgning av grafen G ges. Låt oss kalla två hörn p,q vänner, om något ord w för dem till samma vertex: pw = qw. Låt oss kalla p,q fiender om de "aldrig möts". Låt oss kalla p,q stabila vänner om efter att ha utfört något ord w de förblir vänner: pw kanske inte kommer till samma vertex som qw, men efter lite mer w" kan den det. Stabila vänner blir aldrig fiender.

Stabilitetsrelationen mellan hörn är för det första en ekvivalens (den är reflexiv, symmetrisk och transitiv), och för det andra bevaras den av grafstrukturen: om p,q är stabila vänner, är p förenad med en kant med p" , q med q", och dessa kanter har samma färg, då är p" och q" också stabila vänner. Detta innebär att stabil vänskap är kongruens och kan delas in i det: skapa en ny graf G", vars hörn kommer att vara stabila vänskapsekvivalensklasser i G. Om det finns minst ett stabilt par i G, kommer G" att vara mindre än G i storlek. Dessutom, om i den ursprungliga grafen har G från varje vertex d kanter, då i G" kommer det att vara detsamma. Till exempel, om P är en vertex av en ny graf, vilket är ekvivalensklassen för de ursprungliga hörnen p1, p2... , och α är vilken färg som helst, då leder kanterna p1--α--> q1, p2---α-->q2, etc. alla till hörnen q1, q2..., som är i stabil vänskap med varje andra, och därför ligger i en ny vertex Q, så att alla dessa kanter blir en ny kant P --α-->Q Och så vidare för var och en av de d färgerna.

Dessutom, om G var icke-periodisk, så är G" det. För - med vår alternativa definition av periodicitet - förvandlas varje cykel i G till en cykel i G", så om alla cykellängder i G" är delbara med n > 1, då gäller samma sak för alla cykler i G. Så periodiciteten för G" antyder periodiciteten för G.

Låt oss anta att vi i G" lyckades hitta en synkroniserande färgning. Den kan nu användas i G istället för färgningen som vi började med: valfri kant p-->q kommer att få en ny färg enligt den nya färgen på kanten P-->Q. Lite mer exakt bör vi säga så: vid varje vertex P av grafen G" ges en ny färgning genom någon permutation av alla färger π P: kanten som målades med färgen α får en ny färg π P (α). Sedan i den ursprungliga grafen G, vid varje vertex p från stabilitetsklassen P, tillämpar vi samma permutation π P för att färga om dess kanter. Den nya färgningen av grafen G definierar generellt några nya begrepp om "vänskap", "fiendskap" och "stabilitet" som inte är identiska med de ursprungliga. Men ändå, om två hörn p, q var stabila vänner i den gamla färgen - tillhörde samma klass P - så kommer de att förbli stabila vänner i den nya. Detta beror på att vilken sekvens w som helst som för p,q till en vertex kan "överföras" från den gamla färgen till den nya, eller vice versa, med hjälp av permutationen π P vid varje vertex p längs vägen. Eftersom p,q är stabila i den gamla färgningen och förblir så "hela vägen", kommer varje mellanliggande hörnpar p n , q n på vägen från p,q till den gemensamma vertexen att vara stabila, d.v.s. ligger innanför samma vertex P n och får därför samma permutation π P n .

Den nya färgningen synkroniserar för G, det vill säga någon sekvens w för alla hörn till en vertex P. Om vi ​​nu tillämpar w på den nya färgningen i G, då konvergerar alla hörn någonstans "inuti P". Som indikerat ovan, alla hörn hörn inom klassen P förblir stabila i den nya färgningen, vilket innebär att vi nu kan fortsätta w, om och om igen att sammanföra de återstående paren av hörn som fortfarande är åtskilda, tills allt konvergerar till en vertex G. Den nya färgen är alltså synkronisering för G.

Av allt detta följer att för att bevisa satsen räcker det att bevisa att det i varje graf som uppfyller villkoren finns en färgning där det finns ett par stabila vänner . För då kan man gå från grafen G till grafen G" mindre, och den uppfyller också alla villkor. Med hjälp av det induktiva argumentet kan vi anta att för grafer av mindre storlek är problemet redan löst, och sedan synkroniseringen färgning för G" kommer också att synkroniseras för G .

Klick och maximal set

För varje delmängd A av hörn i grafen och ordet w, betecknar Aw den mängd hörn som vi kommer fram till, med början från alla hörn i A och efter ordet w. Om vi ​​utgår från alla hörn i grafen i allmänhet, så betecknar vi detta med Gw. I denna notation betyder synkronisering av färg att det finns ett w så att Gw är en uppsättning av ett element.

Om vertexmängden A har formen Gw för någon w, och dessutom är två valfria hörn i A fiender, d.v.s. aldrig konvergera, låt oss kalla A klick. Klickar existerar för att vi alltid kan börja med ett heltal G, ta ett par vännära hörn, korsa w som förbinder dem och minska antalet hörn med en; fortsätt så här tills det bara finns fiender kvar eller bara en vertex återstår - även i det här fallet en klick, bara trivial.

Om A är en klick, så är w för alla ord också en klick; detta är tydligt eftersom fiender förblir fiender. Om x är någon av grafens hörn, så finns det en klick som innehåller x. Detta följer av att det finns någon klick A (se föregående stycke); om p är ett hörn i det, så finns det ett ord w som leder från p till x, eftersom ansluten graf; då är Aw en klick inklusive x.

Klick hjälper oss att bevisa att det finns en färgning med stabila vänner - enligt föregående avsnitt är detta tillräckligt för att bevisa satsen. Genom hela det här avsnittet kommer vi att bevisa att om det finns två klick A och B, så att alla hörn i dem är gemensamma, förutom en i A och en i B, så är dessa två hörn stabila vänner. Således minskar problemet till att hitta en färg som innehåller sådana klick A och B.

För att bättre förstå hur klick fungerar är det användbart att tilldela vikter till hörn i en graf. Låt oss visa att vi har ett sätt att tilldela en positiv vikt w(x) till varje vertex x, så att om för någon vertex x summera vikterna för alla hörn som har kanter i x, då får vi d*w(x), där d är antalet kanter från varje vertex. Detta följer av linjär algebra, och om du inte vet vad ett egenvärde är, hoppa över resten av detta stycke och ta existensen av en sådan w(x) på tro. Om M är matrisen för grafen G (cell (i,j) är 1 om det finns en kant i-->j, och 0 om det inte finns någon sådan kant), då är w(x), som jag beskrev dem, är element i egenvektorn vänster denna matris för egenvärdet d. Vi vet att en sådan vektor existerar eftersom d är ett egenvärde: den har en trivial egenvektor till höger(1,1,....1) - detta följer omedelbart av att exakt d kanter kommer ut från varje vertex.

Om A är någon uppsättning av hörn, så betecknar w(A) summan av vikterna av alla hörn i A; och w(G) är summan av vikterna av alla hörn i grafen. Dessutom, om s är något ord, låt As -1 beteckna uppsättningen av hörn som du kommer till från A om du går "i motsatt riktning" längs s, och i varje steg ersätter du varje vertex med dessa hörn (om några) som går till den i lämplig färg.

Låt oss nu betrakta alla uppsättningar av hörn som kan sammanföras till en punkt, dvs. En sådan att, för vissa w, innehåller Aw bara en vertex. De uppsättningar A som bland alla sådana har den maximala vikten w(A) kallas maximala uppsättningar. Om färgningen synkroniserar är hela grafen G en maximal uppsättning (unik), men annars är den inte det.

Om A är någon uppsättning av hörn, då är summan av alla w(Aα -1), där α löper genom alla d färger, lika med d*w(A) - detta är bara en generalisering av huvudviktsegenskapen från en vertex till mängden av hörn A. Om dessutom A är den maximala mängden, kan var och en av w(Aα -1) inte vara större än w(A), eftersom dessa mängder också konvergerar till en vertex. Och eftersom summan d av dessa vikter är lika med d*w(A), visar det sig att var och en av dem är lika med w(A), och alla dessa uppsättningar är också maximala. Detta innebär omedelbart att om A är maximal så är Aw -1 också maximal för alla ord w.

Maximala uppsättningar är användbara eftersom deras disjunkta instanser kan täcka hela grafen. Låt oss bevisa det.

Låt oss ha en uppsättning maximala mängder A 1 ...A n som inte skär varandra i par och reduceras till enkla hörn a 1 ...an med samma ord w (i initialfallet kommer det att finnas n=1 och endast en uppsättning, så det är lätt att starta). Det är tydligt att alla a 1 ...a n skiljer sig från varandra, eftersom det annars skulle vara möjligt att utöka den maximala mängden ännu mer med element från en annan med samma slutliga vertex. Antag att alla A i tillsammans ännu inte har uttömt alla hörn av G, och låt x vara en vertex utanför alla A i . Eftersom grafen är sammankopplad finns det en rutt h från a 1 till x. Sedan går n maximala mängder A ih -1 w -1 med ordet whw till de sista hörnen a 1 ...an , och den maximala mängden A 1 går till någon vertex Awhw = (Aw)hw = (a 1 h)w = xw. Denna vertex xw måste också skilja sig från alla a 1 ...a n , för annars skulle den maximala mängden A i kunna kompletteras med elementet x. Och eftersom alla dessa n + 1 uppsättningar - alla A i h -1 w -1 plus A 1 - går längs whw till olika hörn, är de alla parvis disjunkta. Vi kommer att fortsätta denna expansion tills det inte finns några hörn utanför uppsättningen.

Så vi kan täcka hela grafen G med disjunkta maximala mängder. Eftersom de är maximala har de alla samma totala w max , och därför är deras antal i täckningen N max = w(G)/w max .

Tänk nu på vilken uppsättning A som helst som består av parvisa fiender. Till exempel är en klick ett exempel på en sådan uppsättning (och har även formen Gw). Det kan inte finnas ett par fiender inom den maximala uppsättningen, för då kunde den inte konvergera. Följaktligen, i en täckning av Nmax maximala uppsättningar, innehåller var och en högst en medlem av A, så storleken på A är som mest Nmax. I synnerhet är detta en övre gräns för storleken på en klick.

Låt A vara en klick av formen Gw, där w är något ord. Då är G = Aw -1 , och följaktligen är w(G) lika med summan w(aw -1), där a löper genom alla hörn av A. Enligt föregående stycke är antalet termer som mest N max , och varje uppsättning aw -1 kan reduceras till en punkt (till punkten a med ordet w), så dess vikt är inte större än den maximala w max . Eftersom hela summan är w(G) = N max *w max , drar vi slutsatsen att antalet termer är exakt N max , och varje term är exakt w max . Vi har bevisat att alla klick har samma storlek: exakt N max element.

Låt det finnas två klick A och B, så att inuti A är alla element gemensamma med B, utom ett: |A| - |A∩B| = 1.

Eftersom A och B har samma storlek har vi också |B| - |A∩B| = 1, dvs. A och B har alla element gemensamma utom en vertex p i A och en vertex q i B. Vi skulle vilja bevisa att dessa hörn p,qär stabila vänner. Om så inte är fallet, så gör något ord w dem till fiender, d.v.s. pw och qw är fiender. Som visas ovan är Aw och Bw också klicker, och det är uppenbart att de återigen har alla element gemensamt, förutom fienderna pw och qw. Sedan är uppsättningen Aw ∪ Bw uppsättningen av parvisa fiender. Sannerligen, i den är alla delar av Aw parvisa fiender, eftersom det är en klick; detsamma gäller för elementen Bw; och bara ett par pw, qw återstod - även fiender. Men denna uppsättning har N max +1 element, och ovan visade vi att alla parvisa fiender inte kan ha mer än N max element. Detta är en motsägelse, och därför kan inte pw och qw vara fiender för någon w. Med andra ord, p och q är stabila vänner.

Spännande grafer och klickar

Låt oss ta alla hörn från en given graf G och välja endast en utgående kant från varje hörn. Ett sådant val definierar en subgraf, som vi kallar spännande graf(spännande graf). Det kan finnas många olika övergripande grafer, men låt oss fundera lite på hur de ser ut. Låt det finnas någon spännande graf R. Om vi ​​tar någon vertex x i den och börjar följa dess kanter, så kommer vi varje gång att ha det enda valet, för i R kommer bara en kant ut ur varje vertex, och förr eller senare kommer vi att nära cykeln. Kanske kommer den här cykeln inte att stängas vid x, utan stängas någonstans "längre" - till exempel x-->y-->z-->s-->y. Sedan kommer från x att leda "svans" till denna cykel. Om vi ​​utgår från någon annan topp kommer vi också definitivt till en cykel - den här eller någon annan. Det visar sig att valfri hörn av R antingen ligger på en cykel (som det kan finnas flera av), eller är en del av "svansen" som leder till cykeln. Det betyder att R ser ut så här: ett visst antal cykler, och ett visst antal "omvända" träd är byggda på dem: varje träd börjar inte, utan slutar i en "rot" som ligger på en av cyklerna.

Till varje hörn av grafen kan vi tilldela nivå, motsvarande dess avstånd från cykeln i den givna spännande grafen R. Topppunkter som ligger på cykeln har nivå 0, och hörn som ligger på trädet kopplat till cykeln får en nivå som är lika med avståndet i deras träd till "roten" "liggande på cykel. Vissa hörn i vår graf har en maximal nivå L. Kanske är den i allmänhet lika med 0 - dvs. det finns inga träd, bara cykler. Kanske är det större än noll, och hörnen för denna maximala nivå ligger på alla möjliga olika träd kopplade till olika cykler eller till en.

Vi vill välja en spännande graf R på ett sådant sätt att alla hörn av maximal nivå ligger på samma träd. Intuitivt kan man tro att detta kan göras, för om så inte är fallet - till exempel är de utspridda i olika träd - så kan man välja en av sådana maximala hörn x och öka dess nivå genom att fästa till R någon kant som går till x. Då måste någon annan kant kastas ut, och det är inte säkert att det inte skadar något annat... men det är en teknisk fråga, mer om det senare. Jag försöker bara säga att det inte intuitivt ser särskilt komplicerat ut.

Antag för tillfället att vi kan välja R så att alla hörn av maximal nivå ligger i samma träd. Detta träd antas vara icke-trivialt, dvs. den maximala nivån L > 0. Baserat på detta antagande kommer vi att konstruera en färg med klick A och B i den, som uppfyller villkoren i föregående avsnitt, och detta kommer att bevisa att denna färgsättning har ett stabilt kompispar.

Färgningen blir som följer: vi väljer någon färg α, och vi färgar alla kanter i grafen R i denna färg och alla andra kanter i grafen G - i några andra färger på något sätt (om det bara finns en färg, då sammanfaller R med G så inga problem). Ord som består av färgen α "förflyttar" således R:s hörn längs sina träd mot cyklerna och driver dem sedan längs cyklerna. Vi behöver bara sådana ord.

Låt x vara valfri hörn av maximal nivå L i R, och låt K vara vilken klick som helst som inkluderar x; vi vet att det finns en sådan klick. Kan K inkludera någon annan vertex på maximal nivå L? Enligt vårt antagande är alla sådana hörn i samma träd som x, vilket betyder att ordet α L leder dem till samma plats som x - nämligen till roten av detta träd som ligger på cykeln. Därför är alla sådana hörn vänner till x och kan därför inte ligga i samma klick med den. Därför, förutom x, kan K endast inkludera hörn på lägre nivå.

Låt oss titta på mängden A = Kα L-1 . Detta är också en klick, och i den har alla hörn, förutom x, nått några av sina cykler i R, eftersom alla hörn i A, förutom x, har en nivå som är mindre än L. Endast x är fortfarande utanför cykeln, på ett avstånd av exakt 1 till dess rot på cykeln. Låt oss nu ta ett tal m som är en multipel av alla cykellängder i R - till exempel produkten av alla cykellängder. m har en sådan egenskap att om ett hörn y är på en cykel i R, så returnerar ordet α m det till sin plats: yα m = y. Låt oss titta på klicken B = Aα m . Alla hörn av A, utom x, låg i cykler och stannade därför kvar i B; och bara x gick till slut in i sin cykel och slog sig ner där någonstans. Detta betyder att skärningspunkten mellan A och B innehåller alla hörn av A, utom en: |A| - |A∩B| = 1. Men detta betyder bara, enligt föregående avsnitt, att vår färgsättning har ett stabilt par, vilket skulle bevisas.

Bygger den maximala nivån.

Det återstår att bevisa att det alltid är möjligt att välja en spännande graf R så att den har en icke-trivial maximinivå L > 0, och alla hörn på denna nivå ligger i samma träd.

En del av detta bevis är ett ganska tråkigt och tekniskt lemma som jag har läst och kollat, men jag ska inte återberätta det, jag säger bara var det står i tidningen för den som är intresserad. Men jag ska berätta hur du kommer till detta lemma.

Vi kommer att behöva två restriktioner som vi kan lägga på grafen G. Först säger vi att det inte finns några loopar i G, d.v.s. kanter från en vertex till samma vertex. Poängen är att om det finns en slinga i grafen så är det väldigt lätt att hitta den synkroniserande färgningen på annat sätt. Låt oss måla den här slingan i någon färg α, och sedan, från denna vertex i motsatt riktning "mot pilarna", kommer vi att färga kanterna så att färgen α alltid leder till denna vertex. Eftersom grafen är ansluten är detta lätt att ordna, och då säkerställer slingan att en viss styrka av α kommer att föra hela grafen till denna vertex.

Anta sedan för en sekund att från någon vertex p, leder alla d kanter till samma vertex q. Detta är tillåtet av villkoren, men i det här fallet kommer vi att kalla denna uppsättning kanter bunt. Vår andra begränsning är denna: det finns ingen vertex r till vilken två länkar leder från olika hörn p och q. Varför kan vi påtvinga det? För om det finns länkar från p och q till r, så för alla färg p,q konvergera till vertex r efter den första färgen, och därför är de stabila vänner. Så i det här fallet behöver vi inte all konstruktion av spännande grafer och klickar, vi får stabila vänner direkt. Därför kan vi anta att så inte är fallet.

Låt oss slutligen bevisa att det alltid finns en spännande graf R där inte alla hörn ligger på cykler, men det finns några icke-triviala träd. Vi väljer något R och antar att alla hörn i det ligger på cykler. Om i grafen G ligger alla kanter i buntar - d.v.s. alltid alla d kanter som går ut från en vertex ledde till samma vertex - att välja R skulle innebära att man bara väljer en kant från varje bunt. I det här fallet kan det bara finnas en cykel i R (trots allt kunde flera cykler i R inte kopplas till varandra i en sammankopplad graf G - alla kanter på G förbinder bara samma hörn som kanterna på R, eftersom dessa är ligament - och eftersom G är ansluten är detta omöjligt), och varje cykel i G väljer helt enkelt andra kanter från länkarna i denna cykel, men i själva verket är det samma cykel, samma längd. Men detta betyder att längderna av alla cykler i G är delbara med denna längd, vilket bara motsäger icke-periodiciteten hos G. Därför kan det inte vara så att alla kanter i G ligger på band, vilket betyder att det finns några två kanter p -- >q i R, och p-->s utanför R (vi behövde ett långt argument om kopplingar för att bevisa att någon kant från p inte bara inte ligger i den spännande grafen, utan också leder till en annan vertex s). Sedan ersätter vi p-->q med p-->s, och detta kommer att "bryta" cykeln och skapa en icke-trivial svans i den. Denna svans kommer att ge oss ett icke-trivialt träd i den nya grafen.

Nu, från alla spännande grafer R som har icke-triviala träd, kan vi välja något R som har det maximala antalet hörn på cyklerna. T.e. den har hörn inte på cykler, men bortsett från denna begränsning är antalet hörn på cykler maximerat. Den här grafen har några hörn på maximal nivå L, och vi kan anta att de är på träd som leder till olika rötter, annars har vi redan uppnått det vi behöver. Vi väljer en sådan vertex x. Vi vill ändra grafen på ett sådant sätt att denna vertex blir en del av en längre rutt i trädet, längre än L, och resten av träden inte förändras, och då blir maxnivån i endast ett träd, vilket är vad vi vill. Du kan ändra grafen på tre sätt:

a) ta någon kant y-->x, och lägg till den till R, och kassera kanten y-->z som finns där;
b) ta kanten b-->r, som bara är den sista på vägen från x till dess cykel (r på cykeln), och släng den och lägg till några andra b-->z.
c) ta kanten c-->r, som är en del av cykeln, och kassera den, och lägg till några andra c-->z.

Lemma 7 i Trachtmans artikel bevisar i detalj att en (eller i något fall två) av dessa förändringar leder till det önskade resultatet. Processen använder både maximaliteten av R (om någon förändring leder till en graf med ett större antal hörn på cykler än i R, motsäger detta dess maximalitet), och det villkor som definieras ovan att det inte finns någon vertex som två anslutningar leder till. Som ett resultat får vi i alla fall en graf R där alla hörn av den maximala nivån ligger på ett icke-trivialt träd.

Uppdatering, en vecka senare:ändå bestämde jag mig för att göra detta inlägg helt självförsörjande och även återberätta beviset på det lemma som jag hänvisade till i föregående stycke. Det skulle vara bättre att göra detta med ett diagram, men jag vill inte rita det eller riva det ur artikeln, så jag ska försöka med ord. Så låt oss föreställa oss att vi har en spännande graf R, som har icke-triviala träd, och av alla sådana grafer i den högsta belopp hörn ligger på cykler. Vi strävar efter att omvandla R till en spännande graf där alla hörn av maximal nivå ligger på samma träd; så fort vi försöker få en sådan graf slutar vi omedelbart (och vi bryr oss inte om att den maximala grafen när det gäller antalet hörn på cykler kan gå förlorad, det är inte viktigt för oss i sig, vi använder det bara i processen). Låt x vara spetsen för maxnivån L, T trädet som den ligger på, r spetsen på cykeln C där T slutar, b-->r sista kanten före r på vägen från x till cykeln C. Vi kan anta att det fortfarande finns några träd som ansluter sig till denna cykel eller andra som har nivå L hörn - annars är allt redan gjort. Det följer att om vi lyckas få ett träd från T med ett element av högre grad än L, och inte förlänger dessa andra träd, så är vi klara.

Låt oss först försöka utföra operation a) ovan: ta någon kant y-->x i G - den finns, eftersom grafen är sammankopplad och utan loopar, och ligger inte i R, eftersom x maxnivå. Låt oss lägga till det i R och kasta ut lite y-->z som fanns där tidigare. Om y ligger på trädet T, så stänger y-->x en ny cykel, och i den nya grafen ligger fler hörn på cykler, och det finns fortfarande icke-triviala träd (åtminstone de andra som var i R), vilket motsäger maximaliteten för R. Om y inte ligger på T, och y-->z inte är en del av cykeln C, så bryter inte denna cykel om y-->z raderas, och att lägga till y-->x förlängs den maximala nivån för trädet T med minst en, och de andra träden förlängs inte, så vi är klara. Det återstående alternativet är när y-->z låg på cykeln C, som nu har brutits, och en ny cykel har bildats: från r till y, sedan y-->x, sedan från x till r längs det tidigare trädet. Längden på denna cykel är l(ry)+1+L, medan längden på den gamla cykeln C var l(ry)+1+l(zr). Den nya cykeln kan inte vara längre än den gamla, detta motsäger maximaliteten för R, så vi ser att L ≤ l(zr), d.v.s. sträckans längd från z till r i den gamla slingan. Å andra sidan, i den nya grafen, har vertex z nu en nivå på minst l(zr), och om denna är större än L så är vi klara. Så vi kan anta att l(zr)=L. För att sammanfatta: vi antar att a) inte fungerar, och då vet vi att y-->z ligger på cykeln C, l(zr) = L.

Låt oss nu prova operation b): ersätt kanten b-->r med någon annan kant b-->d. Låt oss se var den nya vertex d ligger. Om på trädet T, skapade vi en ny cykel utan att bryta den föregående, och motbevisade maximaliteten för R. Om på ett annat träd, kommer de maximala hörnen för T, inklusive x, nu att ha en nivå som är större än L, medan andra träd kommer inte, och vi är klara. Om på en annan slinga än C, så kommer vi nu att göra a) tillsammans med b) eftersom vi vet att y-->z ligger på C, kommer denna operation att bryta C, men inte den nya slingan som nu är kopplad till trädet Τ , och detta träd kommer nu att ha hörn på en nivå större än L, och vi är klara igen.

Det återstående alternativet är när b-->d också kopplas till cykeln C, på någon annan plats än r, eller på samma plats och då d=r. Efter att vi bytte ut b-->r med b-->d fick vi samma situation som ursprungligen - träd T, nod x på nivå L osv. - endast trädet är nu kopplat till cykeln genom vertex d. Med tanke på nu operation a), drar vi slutsatsen (förutsatt att det inte fungerar) att l(zd) = L, precis som vi tidigare drog slutsatsen att l(zr) = L. Men om l(zd)=l( zr), dvs. avståndet längs cykeln från z är detsamma till d och r, då är detta samma vertex: d=r. Så, om b) inte fungerar, så måste vilken kant som helst från b leda till r, dvs. kanter från b bildar en bunt.

Betrakta slutligen kanten c-->r som ligger på cykeln C. Eftersom vi kan anta att alla kanter från b ligger på länken som leder till r, kan vi också införa begränsningen som nämnts ovan att det inte kan finnas två länkar , vilket leder till en vertex, inte alla kanter från c leder till r, men det finns någon kant c-->e. Låt oss ersätta c-->r med c-->e. Var kan vertex e ligga? Inte på trädet T, eftersom det skulle "förlänga" cykeln C, vilket motsäger maximaliteten för R. Så e ligger på ett annat träd, eller på en annan cykel, eller till och med på samma cykel C, men inte vid vertex r . Sedan förlängs nu trädet T, innan det kopplas till cykeln, med minst en kant som utgår från r, och kanske mer (endast en om e ligger direkt efter r, och c--> e stänger cykeln C igen, härleder endast r från det). Detta betyder att nivån på vertex x och andra maximala hörn T nu är minst L + 1, och de andra träden har inte förlängts, och återigen har vi det vi behöver.

Uppdatering av webbplatsen
10.12.2006 15:46
För fans av bilar och tecknade serier - målarbok från tecknade bilar.

Tack vare Disney och Pixar såg hela världen i juni 2006 en tecknad serie där bara bilar blev hjältar.

Bilar i den tecknade filmen Cars ("Cars") lever ett vanligt liv - den ena har en gummiaffär, den andra en trimstudio, och några lever bara för sitt eget nöje, som hippien Fillmore (Volkswagen T1) eller hans vän - en veteranen från andra världskriget Serge (Willys). Huvudpersonen i bilden McQueen, med smeknamnet "Lightning", drömmer bara om racing, segrar och ära. Väl i Radiator District på den berömda US Highway 66 berättar den "gröna" McQueen omedelbart för alla hur snabb och cool han är. Men den första starten i NASCAR-loppet skingra hans illusioner. Vänner hjälper hjälten att överleva förlusten - den gamla Meiter-dragbilen (GMC Pick-up), mentorn Doc Hudson (Hudson Hornet) och lilla Luigi (Fiat 600), som drömmer om att se en riktig Ferrari.

Tja, var utan den romantiska skönheten Sally (Porsche med en charmig 911-tatuering)! Till stor del tack vare dem kommer McQueen fortfarande att vinna loppet och besegra huvudrivalen Chico (Plymouth Hemi Cuda). Luigis dröm kommer också att gå i uppfyllelse - en dag kommer en "hingst från Maranello" att ringa in i hans butik för att byta däck, vilket för övrigt uttrycktes av "Röde baronen" Michael Schumacher själv.

Det är anmärkningsvärt att både skaparna av bilden och de som uttryckte den är personer som är inblandade i bilar. Till exempel tillbringade regissören Joe Lasseter större delen av sin barndom på Chevroletfabriken, där hans far var en av chefsdesignerna. Jay Mays, den ledande designern av Ford-koncernen, agerade som konsult. Förutom den redan nämnda sjufaldige Formel 1-världsmästaren Michael Schumacher, var NASCAR-stjärnorna Richard Petty och Paul Newman, samt den legendariske racerföraren Michael Andretti, med och uttryckte hjältarna.

Endast det ursprungliga billjudet användes - till exempel, speciellt för racingavsnitt, spelades ljudet in i flera veckor på amerikanska ovaler under NASCAR-tävlingar. Det tog mer än två år att skapa bilden, vars budget var 70 miljoner USD. Under denna tid skapades 43 tusen olika skisser av bilar, och varje ritning tog mer än 17 timmar. Det finns totalt 120 bilkaraktärer i filmen, från nya Porscher och Ferraris till antika Ford T.

Du är på vägmålarsidan. Målarbok du tittar på beskrivs av våra besökare så här "" Här hittar du en hel del målarbok online. Du kan ladda ner vägmålarbok och även skriva ut dem gratis. Som ni vet spelar kreativa aktiviteter en stor roll i barnets utveckling. De aktiverar mental aktivitet, bildar en estetisk smak och ingjuter en kärlek till konst. Processen att färglägga bilder på vägens tema utvecklas finmotorik, uthållighet och noggrannhet, hjälper dig att lära dig mer om världen omkring dig, introducerar dig till alla olika färger och nyanser. Varje dag lägger vi till nya gratis målarbok för pojkar och tjejer på vår hemsida, som du kan färglägga online eller ladda ner och skriva ut. En bekväm katalog sammanställd av kategorier gör det lättare att hitta rätt bild, och ett stort urval av målarsidor gör att du kan hitta ett nytt intressant ämne för färgläggning varje dag.

Du kan hålla pojkarna sysselsatta länge om du bjuder in dem att leka med bilar i sandlådan. Men tänk om det är kallt ute, barnet har tråkigt. I det här fallet kan du ladda ner och skriva ut följande bilvägsmallar. Det roliga börjar med att skära ut alla ringar, svängar och raka vägar. Från dessa mallar kan ett barn bygga en väg av vilken form som helst, se bara till att rätt antal nödvändiga A4-ark skrivs ut.

Ladda ner rak väg för bilar

Dessa ark kommer att behövas mest av allt. På ett ark i A4-format placerade vi 3 vägar som ska skrivas ut och klippas ut. Visa ditt barn hur man skär vägen i rät vinkel för att få sektionen till den längd han behöver.

Väg för bilar: ring

För att ansluta vägarna behöver du en ring, vars mall presenteras ovan, och börja bygga din infrastruktur från den.

Bilväg: Raktsväng

De presenterade svängarna gör att pojken kan svänga vägen i 90 grader, i den riktning han behöver.

Inte en skarp vägsväng för bilar

Följande A4-mall hjälper till att vända vägen oavsett radie.

Barnets kunskap om reglerna trafik- ett av huvudvillkoren för hans säkerhet på gatan. Många fotgängare, inklusive vuxna, är ganska oseriösa när det gäller att följa dessa regler, som ofta blir orsaken till trafikolyckor av olika svårighetsgrad. Barn måste tydligt förstå att de är på gatan i byn fullvärdiga medlemmar trafik, så att följa trafikreglerna är deras ansvar.

Målarbok Vägregler för barn.

Att lära ett barn beteendereglerna på gatan (vägar, trottoarer, stadstransporter) bör börja i mycket tidig ålder, innan han lär sig att gå och springa på egen hand. Och här är exemplet med föräldrar och andra vuxna som barnet är på gatan med mycket viktigt. Du måste inte bara berätta och förklara vägreglerna för ditt barn, utan också strikt följa dem själv. Trafikreglernas målarbok på denna sida är främst avsedda för förskolebarn och kommer att hjälpa barn att lära sig grunderna för beteende på vägen, såväl som i närheten.

1. Målarbok för trafikljus.

Det bästa stället att korsa vägen på ett säkert sätt är vid ett övergångsställe försett med trafikljus. Målarbok för trafikljus innehåller också små rim för att hjälpa barn att komma ihåg reglerna för att använda det lättare.

• Börja alltid bara köra när trafikljuset lyser grönt.
• Korsa aldrig vägen på röda eller gula trafiksignaler, även om det inte finns några fordon i närheten.
• När du tänder det gröna ljuset, se dessutom till att du är säker - titta till vänster och sedan till höger.

2. Färgläggning av övergångsstället.

Lär ditt barn att korsa körbanan endast vid ett övergångsställe. Målarbok över övergångsställen kommer att lära barn att korsa vägen på rätt sätt. En korsning som inte är utrustad med trafikljus kallas oreglerad.

• Övergångsstället är markerat på vägytan med en zebra.
• Innan du korsar vägen, inspektera den noggrant, se till att det inte finns någon trafik i närheten.
• Korsa vägen, spring inte över.
• Gå inte över gatan.
• Var särskilt uppmärksam på stående fordon som blockerar din sikt.
• Sluta prata i telefon när du går över ett övergångsställe.
• Om det finns underjordiska eller förhöjda passager i närheten, se till att använda dem, på sådana platser är trafiken särskilt intensiv.

3. Trottoarer.

Trottoaren är avsedd för gångtrafik. Uppmuntra barn att bete sig korrekt på trottoarer, särskilt de som ligger i områden med tät trafik.

• När du kör på trottoaren längs vägen, kom inte för nära den.
• Observera noga den möjliga utfarten av bilar från gårdar, gränder.
• Spela inte boll på trottoaren, spring inte.

4. Målarbok med uppföranderegler för barn i stadstrafik och vid busshållplatser.

Dessa målarbok kommer att lära barn reglerna för säker användning av kollektivtrafik.

• Hållplats för kollektivtrafiken - farlig plats på grund av den möjliga dåliga sikten över vägen och en stor folkmassa som av misstag kan knuffa barnet från trottoaren ut på vägbanan. Här måste du vara extra försiktig.
• Närma dig transportens dörrar först efter att den har stannat helt.
• Efter att ha lämnat fordonet, fortsätt att korsa vägen först efter att det har lämnat hållplatsen.

Utöver dessa grundläggande vägregler kommer barn att vara intresserade av att färga trafikskyltar. De presenterade målarboken enligt trafikreglerna är lämpliga för småbarn, förskolebarn och yngre elever. skolålder, samt för användning på dagis och lektioner i grundskola skolor. Alla bilder med Vägreglerna är helt gratis – de går att ladda ner och skriva ut.