Vägfärgningsproblemet
Från Rilpedia
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.
Problemet ställdes först av Benjamin Weiss och Roy Adler 1970[1]. September 2007 visade Avraham Trahtman att det var möjligt att skapa såna instruktioner[2].
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 tecknena 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 nog i grafen (att grafen är starkt kopplad) och att det inte finns något heltal 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 starkt kopplad aperiodisk graf där varje nod har samma utgrad har en synkroniserad färgning.
Referenser
- ↑ R.L. Adler, B. Weiss. Similarity of automorphisms of the torus. Memoires of the American Mathematical Society, Vol 98. 1970.
- ↑ Trahtman, Avraham. ”The road coloring problem”. http://front.math.ucdavis.edu/0709.0099.
