I grafteorin handlar vägfärgssatsen , fram till nyligen känd som vägfärgningsförmodan , med tidsinstruktioner . Uppgiften är att hitta sådana instruktioner att det, oavsett objektets initiala position, skulle vara möjligt att nå destinationen i nätverket (som kan vara stadsgator eller en labyrint ) [1] . I den verkliga världen kan du se den här uppgiften som en uppsättning instruktioner för din vän att ta sig till ditt hus, oavsett var han är nu. Teoremet har även tillämpningar inom symbolisk dynamik .
Låt G vara en ändlig starkt sammankopplad riktad graf där alla hörn har samma utgrad k . Låt A vara ett alfabet som innehåller bokstäverna 1, …, k . En timingfärgning (även känd som en hopfällbar färgning ) av en graf G är en märkning av kanterna på G med bokstäver från A så att (1) varje vertex har exakt en utgående kant med den angivna etiketten, och (2) för varje vertex v i grafen finns ett ord w över A så att alla banor i G som motsvarar w slutar i v .
Termen synkroniserande färgläggning uppstod i samband med termen synkroniseringsord i finita automatteorin .
För att en färgning ska existera måste G vara aperiodisk [ 2] ; det vill säga längden på alla möjliga cykler i grafen måste vara relativt prime . Vägfärgningssatsen säger att aperiodicitet också är tillräcklig för att det ska finnas en färgning. Således kan vägfärgningsproblemet kortfattat formuleras på följande sätt:
Varje ändlig starkt ansluten aperiodisk riktad graf med konstant utgrader har en synkroniserande färg.Figuren visar en riktad graf med åtta hörn, där varje vertex har en ut -grad på 2 (i denna graf har varje vertex också en in-grad på 2, men detta är inte nödvändigt för att en synkron färgning ska existera). Kanterna på grafen är färgade röda och blå för att bilda en synkroniserande färg.
Tänk till exempel på en gulfärgad vertex. Oavsett var du utgår från, om du följer regeln blå-röd-röd-blå-röd-röd-blå-röd-röd kommer du att hamna på den gula toppen. På samma sätt, om du följer sekvensen blå-blå-röd-blå-blå-röd-blå-blå-röd kommer du alltid att hamna på den gröna toppen.
Vägfärgningssatsen säger att för någon kategori av riktade grafer finns denna typ av färgsättning alltid.
Gissningen framfördes av Roy Adler och Benjamin Weiss [3] och bevisades av Abram Trachtman [4] .
Delresultat eller speciella fall erhållna före beviset på satsen: