Vägfärgningsproblemet

Inom grafteori är vägfärningsproblemet ett problem som rör graffärgning. Problemet är om det är möjligt att i ett nätverk kunna skapa instruktioner som gör att man kan ta sig till en specifik punkt från alla punkter med samma instruktion.

En riktad graf med synkroniserad färgning

Problemet ställdes först av Benjamin Weiss och Roy Adler 1970. September 2007 visade Avraham Trahtman att det var möjligt att skapa såna instruktioner.

Beskrvning

Till höger finns en bild på riktad graf med åtta noder där varje nod har utgrad 2 (varje nod har också en ingrad som är 2, men det är inte nödvändigt för att en synkroniserad färgning ska finnas). Bågarna i grafen har färgats för att skapa en synkroniserad färgning.

Exempelvis, om du vill ta dig till den gula noden kan du följa färgningen "blå-röd-röd, blå-röd-röd, blå-röd-röd" var du än är i grafen och till slut, efter att ha passerat nio bågar, hamna i den gula noden. Om du istället vill komma till den gröna noden kan du följa färgningen "blå-blå-röd, blå-blå-röd, blå-blå-röd".

Matematisk beskrivning

Låt $G$ vara en ändlig riktad graf där alla noder har samma utgrad $k$ och låt $A$ vara ett alfabet med tecknen 1, ..., $k$. En synkroniserad färgning av $G$ är en färgning av bågarna i $G$ så att varje nod har exakt en utgående båge med varje färgning och det till varje nod $n$ i grafen finns ett ord $w$ av tecken i $A$ så att varje väg i $G$ som definieras av $w$ slutar i $n$.

För att en sådan färgning ska existera krävs det att man från varje nod i grafen kan komma till varje nod i grafen (att grafen är starkt sammanhängande) och att det inte finns något heltal större än ett som delar längden av alla cykler i grafen (att grafen är en aperiodisk graf). Vägfärgningssatsen säger att det även är ett tillräckligt villkor, så att:

Varje ändlig starkt sammanhängande aperiodisk graf där varje nod har samma utgrad har en synkroniserad färgning.