In de wiskunde zijn enkele beroemde onopgeloste problemen, zoals het Vermoeden van Goldbach, de Riemannhypothese en het P-versus-NP-probleem. Er zijn veel meer openstaande vraagstukken waarvan menig persoon het bestaan níét kent. Het ‘Road Coloring Problem’ is zo’n relatief onbekend probleem. In 1970 werd dit probleem geformuleerd door Benjamin Weiss en Roy Adler. Nu is het opgelost, door Avraham Trahtman.
Het probleem
Stel je een wegennet voor dat uit acht punten bestaat die door éénrichtingswegen zijn verbonden zoals in onderstaande figuur, waarin elke weg rood of blauw is gekleurd. Bestaat er één routebeschrijving die altijd naar het gele punt leidt, onafhankelijk van je beginpunt? Het antwoord is ja: ‘blauw-rood-rood-blauw-rood-rood-blauw-rood-rood’. Wanneer je deze code volgt, kom je altijd uit in het gele punt, waar je ook begint.
Het ‘Road Coloring Problem’: bestaat er een routebeschrijving die altijd naar het gele punt leidt, ongeacht je vertrekpunt?
Zodra er een routebeschrijving bestaat die onafhankelijk van het beginpunt uitkomt in één en hetzelfde punt, bestaat er voor élke eindbestemming zo’n routebeschrijving. Zo geldt in het bovenstaande voorbeeld dat voor de groen gemarkeerde bestemming de route ‘blauw-blauw-rood-blauw-blauw-rood-blauw-blauw-rood’ altijd werkt.
Het ‘Road Coloring Problem’ zegt dat het voor een bepaalde klasse van wegennetten altijd mogelijk is om een kleuring te maken, zodat er een routebeschrijving mogelijk is naar een bepaald punt in het wegennet, onafhankelijk van het beginpunt.
Wiskundige beschrijving
Een wegennetwerk kan schematisch worden weergegeven in wat in de wiskunde een graaf genoemd wordt. De lijnen in een graaf stellen dan de wegen voor, bijvoorbeeld tussen plaatsen, of, op kleinere schaal, tussen kruispunten. De punten in de graaf die de plaatsen of kruispunten voorstellen, heten de knopen van de graaf.
Ga nu uit van een graaf die aan de volgende eisen voldoet: de graaf bestaat uit een eindig aantal knopen, de graaf is gericht (dat wil zeggen dat elke lijn slechts in één richting, aangegeven door een pijl, doorlopen kan worden), en elke knoop heeft hetzelfde aantal uitgaande lijnen (noem dat aantal k). Kun je, gebruikmakend van k verschillende kleuren, elke lijn een kleur geven zodat er, ongeacht het startpunt, voor elke knoop als bestemming een routebeschrijving (in termen van de k kleuren) mogelijk is?
Een eerste voorwaarde waaraan zo’n graaf noodzakelijk moet voldoen, is dat tussen elk tweetal knopen een pad bestaat. Het is niet moeilijk in te zien dat zonder deze eis een dergelijke routebeschrijving niet mogelijk is. Een tweede noodzakelijke voorwaarde is dat de graaf aperiodiek is. Dat betekent dat de lengte van de cykels van de graaf grootste gemeenschappelijke deler 1 hebben.
Boven: bij de linker graaf is er tussen elk tweetal knopen een pad, bij de rechter graaf niet (zo is bijvoorbeeld de zwart gekleurde knoop vanuit geen enkele andere knoop te bereiken).
Onder: de linker graaf is aperiodiek, want de cykels in deze graaf hebben lengte 5 en 6; de rechter graaf is niet aperiodiek, de periode is hier gelijk aan 3.
Deze twee noodzakelijke voorwaarden waren al bekend. Wat Avraham Trahtman nu heeft bewezen, is dat deze twee voorwaarden ook voldoende zijn. Dat betekent dat élke aperiodieke, gerichte graaf met een pad tussen elk tweetal knopen, en waarbij het aantal uitgaande lijnen voor elke knoop gelijk is, zodanig gekleurd kan worden dat er voor elke eindbestemming een routebeschrijving mogelijk is die werkt, zonder dat het ertoe doet waar je start.
Nog twee voorbeelden: bij de linker graaf leidt de route ‘blauw-rood-blauw’ altijd naar het gele punt, bij de rechter graaf leidt de route ‘blauw-rood-rood-rood’ altijd naar het gele punt.
Een late ontdekking
De meeste wiskundigen vinden hun belangrijkste resultaten voor hun veertigste. Avraham Trahtman is 63 jaar en heeft daarmee op relatief hoge leeftijd een grote vondst gedaan op wiskundegebied. In 1992 emigreerde Trahtman van Rusland naar Israël. Hoewel hij van huis uit wiskundige is, deed hij in Israël aanvankelijk ander werk, als onderhouds- en beveiligingsmedewerker. In 1995 werd hij door wiskundige Stuart Margolis naar de Bar Ilan University nabij Tel Aviv gehaald. Margolis noemt de oplossing van het Road Coloring Problem ‘one of the beautiful results’. Het artikel van Trahtman, dat sinds enkele maanden op het internet staat, zal binnenkort verschijnen in de Israel Journal of Mathematics.
Het Road Coloring Problem zal in letterlijke zin niet worden toegepast: in deze tijd waarin veel mensen beschikken over navigatie-apparatuur, is het coderen van een route om iemand de weg te wijzen, die niet eens altijd de efficiëntste is, achterhaald. Het resultaat van Trahtman kan echter wel in andere gebieden, met name de informatica, worden toegepast.
Zie ook:
- The Road Coloring Problem, het artikel van A. Trahtman (pdf; Eng,; technisch!)
Andere toepassingen van de grafentheorie:
- Sudoku en grafentheorie (Kennislinkartikel)
- Superberekening aan E8 (Kennislinkartikel)
- De tweelingbroer van de diamant (Kennislinkartikel)