I grafteori beskæftiger sig vejfarvesætningen , indtil for nylig kendt som vejfarveformodningen , med timinginstruktioner . Opgaven er at finde sådanne instruktioner, at det, uanset objektets begyndelsesposition, ville være muligt at nå destinationen i netværket (som kan være bygader eller en labyrint ) [1] . I den virkelige verden kan du tænke på denne opgave som et sæt instruktioner til din ven om at komme til dit hus, uanset hvor han er nu. Sætningen har også anvendelser i symbolsk dynamik .
Lad G være en endelig , stærkt forbundet rettet graf , hvor alle toppunkter har samme udgrad k . Lad A være et alfabet, der indeholder bogstaverne 1, …, k . En timingfarvning (også kendt som en sammenklappelig farvning ) af en graf G er en mærkning af kanterne af G med bogstaver fra A , således at (1) hvert toppunkt har nøjagtig én udgående kant med den angivne etiket, og (2) for hver toppunkt v i grafen er der et ord w over A , således at alle stier i G svarende til w ender i v .
Begrebet synkroniserende farvning opstod i forbindelse med begrebet synkroniseringsord i finite automaton theory .
For at en farve skal eksistere, skal G være aperiodisk [ 2] ; det vil sige, at længderne af alle mulige cyklusser i grafen skal være relativt prime . Vejfarvesætningen siger, at aperiodicitet også er tilstrækkelig til eksistensen af en farve. Vejfarveproblemet kan således kort formuleres som følger:
Enhver endelig, stærkt forbundet aperiodisk rettet graf med konstant udgrad har en synkroniserende farve.Figuren viser en rettet graf med otte toppunkter, hvor hvert toppunkt har en ud -grad på 2 (i denne graf har hvert toppunkt også en in-grad på 2, men dette er ikke nødvendigt for at der kan eksistere en synkron farvning). Kanterne på grafen er farvet røde og blå for at danne en synkroniserende farve.
Overvej for eksempel et gulfarvet toppunkt. Uanset hvor du starter fra, hvis du følger blå-rød-rød-blå-rød-rød-blå-rød-rød-reglen, ender du i den gule top. På samme måde, hvis du følger sekvensen blå-blå-rød-blå-blå-rød-blå-blå-rød, ender du altid i den grønne top.
Vejfarvesætningen siger, at for nogle kategorier af rettede grafer eksisterer denne type farve altid.
Formodningen blev fremsat af Roy Adler og Benjamin Weiss [3] og bevist af Abram Trachtman [4] .
Delresultater eller særlige tilfælde opnået før beviset for teoremet: