Israëliër Trakhtman lost 38 jaar-oud wiskundeprobleem op

Toeristen die verdwaald zijn in Japan omdat ze de straatnaamborden niet kunnen lezen, weten dat navigeren naar nieuwe plekken door straat tekens alleen betrouwbaar is wanneer ze hen feitelijk kunnen lezen. Professor Avraham Trakhtman, een Israëlische wiskundige, komt met een andere oplossing: door een 38 jaar-oude wiskunde puzzel op te lossen dat bekend staat als "Road Coloring Problem".

Einde aan bijna 40 jarig durend wiskundig debat

Door wat gedachten op papier te zetten heeft professor Trakhtman van de Bar Ilan Universiteit in Tel Aviv een einde gemaakt aan het bijna 40 jaar durend debat. Hij toonde niet alleen aan dat het Road Coloring Problem bestaat, hij schrijft ook een computer programma dat uitlegt hoe wegen te kleuren zodat het werkt in de werkelijke wereld. En terwijl de wiskunde achter de puzzel gecompliceerd is, heeft het invloeden op de vorming van nieuwe universele kleur gecodeerde stadskaarten. En het zal zelfs helpen computers beter te laten werken.

Wat is de Road Coloring Problem?

We kijken naar het speciale geval van Road Coloring waar ten minste één van de steden een uitgaande weg heeft eindigend in dezelfde stad. Stel je voor dat er N steden zijn, en Cx is elk van de steden die een weg naar zichzelf heeft. We doen de volgende visualisering:

Hou Cx in het centrum en rangschik de andere steden in lagen er omheen. Hou eerst deze steden die wegen hebben die direct leiden naar Cx in de eerste laag rond Cx. Noem deze laag L1. Hou nu de steden die wegen hebben die direct leiden naar steden van L1 in de volgende laag L2. Dus we houden alle steden in lagen rond Cx.

Het inkleuren

Voor elke andere stad C is er ten minste één uitgaande weg die leidt naar de laag die net ligt binnen de laag waarop C ligt. Kleur deze weg van C naar zijn volgende binnenste laag rood. De andere uitgaande weg van C wordt groen gekleurd. Als beide wegen van C leiden naar de volgende binnen laag, kleurt het rood of groen. Voor de centrale stad Cx, zal de zelf reikende cirkel weg rood zijn. Met dit inkleuren heeft men een constante eindige pad die leidt van iedere stad naar de centrale stad Cx. Deze opeenvolging van wegen naar de centrale stad heeft altijd de vorm van één groene gevolgd door zovele rode als er lagen zijn (een voorbeeld wordt hieronder gegeven). Voor iedere bepaalde stad C, bestaat er een vastgestelde pad van de centrale stad Cx er naartoe. Dus gegeven iedere willekeurige bestemming C', beginnend bij iedere onbekende bron C, kunnen we eerst het constante pad naar het centrum nemen en het pad van het centrum naar C'. Het pad zal dezelfde zijn voor ieder beginnende stad C en zal alleen afhangen van bestemming C'.

Voorbeeld

Er zijn 5 steden genummerd van 1 tot 5 gerangschikt in een vijfhoek en met de richting van de klok mee verbonden. 1,2,4 en 5 hebben elk één weg dat naar zichzelf cirkelt. 3-5 is een andere weg.

Bijvoorbeeld: De wegen zijn 1-2, 2-3, 3-4, 4-5, 5-1, 1-1, 2-2, 3-5, 4-4, 5-5
Er zijn twee cycli 1-2-3-5 (lengte 4) en 1-2-3-4-5 (lengte 5) - de lengtes zijn relatief oorspronkelijk. Zover we er uit kunnen opmaken, wordt dit bezit niet gebruikt in wat volgt......
We kiezen 1 als de centrale stad. De volgende laag heeft slechts 5 (omdat alleen van 5 er een directe pad is naar 1). In de volgende laag zijn er twee steden, 3 en 4. In de buitenste laag is er alleen 2. Bij het bovenstaande gekleurde schema, 2-3, 3-5, 4-5, 5-1, en 1-1 moet het rood zijn en de andere wegen zijn groen.
De volgorde GRRR neemt je naar stad 1 van uit iedere willekeurige begin stad. Wanneer we een zelfde pad hebben naar de centrale stad vanuit iedere willekeurige plek, hebben we ook een zelfde pad naar iedere vereiste bestemming vanuit iedere willekeurige plek.

Toepassing van de puzzel

Een voorbeeld hoe de puzzel zou kunnen worden toegepast is als volgt: stel je voor dat je vriend naar je stad toekomt en niet weet waar je huis ligt. Door hem een code te geven zoals , links, rechts, rechts, links, zou hij makkelijk de plaats van bestemming (jouw Huis) kunnen bereiken van ieder willekeurig vertrekpunt. Trakhtman zegt dat zo'n code bruikbaar kan zijn voor politie invallen en ook voor taxichauffeurs die naar dezelfde conferentie hal moeten. Een spoed bericht kan de bestuurder allemaal dezelfde richting geven in code en als het wordt opgevolgd zouden ze allemaal op hetzelfde punt komen zonder nadere uitleg.

Wie is Trakhtman?

Trakhtman is een bescheiden man van 63 jaar en is in 1992 vanuit Rusland naar Israël geëmigreerd. Hoewel hij wiskundige was deed hij in Israël aanvankelijk ander werk, zoals onderhoud en beveiliging. Later kwam hij op de Bar Ilan Universiteit terecht en kwam in aanraking met het concept van de Road Coloring Problem dat het eerst werd voorgesteld door een Israëlisch team in 1970 van de Hebreeuwse Universiteit in Jeruzalem. Trakhtman heeft zijn oplossing gepresenteerd in een Israëlisch vakblad. Het heeft onder wiskundigen over de hele wereld bewondering opgewekt. Of het de Nobel Prijs oplevert moet nog worden afgewacht.

Meer over technologie en wetenschap is te lezen in mijn special Technologische en wetenschappelijke ontwikkelingen in Israël. © 2008 - 2010 Etsel, gepubliceerd in Wetenschap (Nieuws uitgelicht...) op 19-02-2008. Het auteursrecht van dit artikel ligt bij de infoteur. Zonder toestemming van Etsel is vermenigvuldiging van dit artikel verboden. Meer...

Verwante artikelen

• Wiskunde, een grote mysterie?: Wiskunde is een zeer brede richting in de wetenschap. Het is een van de oudste wetenschappen en kan beschouwd worden als een formele wetenschap. Als je beknopte definitie van w…
• Vluchtelingen en migranten: Een migrant is iemand die migreert, dit wil zeggen iemand die verhuist. Het begrip wordt echter voornamelijk gebruikt voor iemand die van één land naar een ander verhuist. Hiermee…
• Tour Down Under 2008: De Australische rittenkoers is de eerste wedstrijd van het wielerseizoen. We geven u naast een korte inleiding een overzicht van de rituitslagen en klassementen.
• Iedere vergelijking gaat op: Iedere vergelijking gaat op. Het tegendeel is ook juist: iedere vergelijking loopt mank. Het is een kwestie van hoe je het bekijkt.
• Anouk - Hotel New York: Hotel New York kwam uit in 2004 en was een groot succes. Vooral de nummers ‘Girl' (girl, girl) en 'Lost' waren een grote hit. Veel nummers op deze cd zijn weer geschreven door Anouk i…

Bronnen en/of referenties

• Israel 21c - Karin Kloosterman
• Tech musings