Spoiler alert: deze blogpost bevat de oplossing, of althans een aanzienlijke hint, voor de Topolinkpuzzels!
De aandachtige lezer die onze eerste blogpost over grafentheorie heeft gelezen, herkent wellicht al een graaf in de opgave van de Topolinkpuzzel. Inderdaad, het gaat in essentie over de twee grafen hieronder. Herinner je dat de precieze tekening van de toppen en bogen irrelevant is en verschillende tekeningen dus dezelfde graaf kunnen voorstellen … maar de puzzel bestaat erin om de twee grafen in kwestie op een “mooie” manier te tekenen, zonder dat twee bogen elkaar snijden, en daarvoor is grafentheorie nog steeds een uitermate geschikt framework.
De twee grafen in kwestie zijn natuurlijk niet willekeurig gekozen. De computerchips rechts vormen een voorbeeld van een complete graaf, met de definiërende eigenschap dat elke twee toppen met elkaar verbonden zijn. Je kan zo’n complete graaf tekenen op zoveel toppen als je maar wil; voor \(n\) toppen noteren we de resulterende graaf als \(K_n\). Hieronder zie je dus \(K_1\), \(K_2\), tot en met \(K_6\).
Ook de huisjes en energiecentrales links vormen niet zomaar de eerste de beste graaf. De toppen komen duidelijk in twee soorten (zwarte huisjes versus gekleurde centrales). Bogen tussen toppen van dezelfde soort ontbreken, maar wel is elke top van de ene soort verbonden met elke top van de andere soort. Zo’n graaf noemen we een complete bipartiete graaf, en noteren we als \(K_{m,n}\) als de twee klassen uit \(m\) en \(n\) toppen bestaan. Het concrete examplaar in de puzzel is dus \(K_{3,3}\) en staat ook gekend als de nutsgraaf (utility graph), net omwille van het optreden in deze puzzel.
Nu we de twee grafen in de spotlight wat beter kennen, keren we terug naar de opgave: zoek een voorstelling van de grafen waarin geen twee bogen elkaar snijden. Een graaf die je zo kan tekenen op een blad papier, heet een planaire graaf. Denk eraan dat je een graaf op meerdere manieren kan tekenen, zodat een voorstelling mét kruising niet automatisch betekent dat de graaf niet planair is! De complete graaf \(K_4\) hierboven bijvoorbeeld staat er getekend als een vierkant met twee (snijdende) diagonalen. Toch is \(K_4\) planair, want die kan ook getekend worden met één “diagonaal” langs de buitenkant, waarmee snijpunten vermeden worden.
De hele puzzel komt dus eigenlijk neer op de vraag: zijn de grafen \(K_{3,3}\) en \(K_5\) planair?
Laat het antwoord daarop nu net negatief zijn … Straffer zelfs, twee sterk gerelateerde stellingen in de grafentheorie drukken uit dat \(K_{3,3}\) en \(K_5\) op een zekere manier de kleinste niet-planaire grafen zijn: de stellingen van Kuratowski (1) en Wagner (2). Ze stellen dat elke niet-planaire graaf ergens binnenin een zekere kopie van \(K_{3,3}\) of \(K_5\) moet bevatten; de stelling van Kuratowski zegt concreet het volgende.
Vertrek vanuit \(K_{3,3}\) of \(K_5\). Voeg nieuwe toppen toe op de bestaande bogen, nieuwe toppen daarbuiten, nieuwe bogen, of een combinatie daarvan. Dan is de resulterende graaf niet-planair, en omgekeerd, elke niet-planaire graaf kan uit dit proces worden verkregen. (In het bijzonder zijn \(K_{3,3}\) en \(K_5\) zelf niet-planair.)
De ene richting is best intuïtief: als een graaf niet-planair is, dan zal dat alleen maar zo blijven door toppen en bogen toe te voegen. Het is vooral de andere richting die dit een straffe stelling maakt. Over het algemeen is het relatief makkelijk om aan te tonen dat een graaf planair is: zoek gewoon een geschikte voorstelling. Aantonen dat een graaf niet-planair is, is een stuk moeilijker. Hoe kun je immers zeker zijn, zelfs na veel proberen, dat er niet toch stiekem een voorstelling te tekenen valt zonder snijpunten? Daar is de stelling van Kuratowski (of de nauw verwante stelling van Wagner) uitermate geschikt voor: illustreer dat je er een \(K_{3,3}\) of \(K_5\) in kan terugvinden, en klaar!
Een eenvoudig voorbeeld. Aangezien de complete graaf \(K_5\) al niet-planair is, hoeft het niet te verbazen dat nog grotere complete grafen dat zeker niet zijn. Inderdaad, hieronder zie je bijvoorbeeld hoe je \(K_6\) kan opbouwen door één extra top en een aantal bogen toe te voegen aan \(K_5\).
Ook de Petersengraaf (zie de eerste blogpost) is niet-planair. Om dat te staven, beginnen we bij \(K_{3,3}\) in een wat scheefgetrokken weergave, voegen we middenin drie bogen drie nieuwe toppen toe, en verbinden we die met nog een nieuwe centrale top. Het resultaat is (een voorstelling van) de Petersengraaf.
Toegegeven, het is niet altijd makkelijk om een van de twee verboden grafen te herkennen in een grotere graaf, en daar is de stelling van Wagner iets geschikter voor. We laten de geïnteresseerde lezer de details opzoeken, maar essentieel gebeurt daar het omgekeerde: vertrek vanuit de grotere graaf, snoei toppen en bogen weg, en trek aaneensluitende bogen samen. Als het resultaat een van diezelfde twee grafen \(K_{3,3}\) of \(K_5\) is, dan was de initiële graaf niet-planair.
Leuk weetje trouwens, waarvoor staat de letter \(K\) in de notaties voor complete (bipartiete) grafen? Er zijn bronnen die beweren dat de oorsprong ligt in het Duitse woord komplett, maar in het Duits wordt een complete graaf een vollständiger Graph genoemd … Andere bronnen stellen dat de \(K\) juist een eerbetoon is aan de Poolse wiskundige Kazimierz Kuratowski!
In elk geval, terug naar de puzzel. Betekenen de stellingen van Kuratowski en Wagner nu niet dat er geen voorstelling bestáát zonder snijpunten, en de puzzel dus geen oplossing heeft!? Wel, op een blad papier of een ander vlak oppervlak is dat inderdaad het geval … maar een koffietas is anders!
De reden dat de Topolinkpuzzel wél oplosbaar is, is een extra feature van een tas. Je kan het oor van de tas benutten om een kruising te vermijden, door een van de bogen recht doorheen het oor te tekenen, en de andere eroverheen. Hieronder zie je hoe je zo de complete graaf met vijf toppen op een koffietas krijgt. Ga maar na, elke top is reglementair verbonden met elke andere top. Ook voor de nutsgraaf \(K_{3,3}\) kun je het oor van de tas uitbuiten voor een voorstelling zonder snijdende bogen, maar deze opgave laten we aan de puzzelaar over!
Voor nog grotere en complexere grafen zal één oor of handvat niet volstaan voor een snijpuntloze voorstelling, en heb je een tweede, derde, of zelfs nog meer handvaten nodig. Het minimale aantal benodigde handvaten wordt het genus van de graaf genoemd. Een planaire graaf heeft er helemaal geen nodig en heeft aldus genus 0. De grafen \(K_5\) en \(K_{3,3}\) hebben genus 1. Ook voor de complete grafen \(K_6\) en \(K_7\) volstaat één handvat, maar \(K_8\) heeft al genus 2 en \(K_9\) genus 3. Dat betekent dat je de opgave kunt uitbreiden naar zes of zeven computerchips, maar dat het voor acht toppen niet lukt zonder een speciale tas met twee oren.
Het is wellicht geen verrassing dat zeven toppen allemaal onderling verbinden, zelfs op een koffietas met oor, nog geen evidente opgave is. Je moet nog steeds 21 bogen correct uitgepuzzeld krijgen doorheen en over dat handvat! De figuur hieronder geeft weer hoe je de klus kunt klaren op een adequaat vervormd handvat (tot een soort donut); de vijf bogen aan de rechterzijde lopen horizontaal rondom door, en de zes bogen aan de bovenzijde lopen verticaal langs de binnenkant.
| Parameter \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Genus van \(K_n\) | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 8 |
De tabelwaarden lijken wat willekeurig, maar Gerhard Ringel en John Youngs vonden een exacte formule (3) voor het genus van een complete graaf.
\[\gamma(K_n) = \Bigl\lceil \frac{(n-3)(n-4)}{12} \Bigr\rceil \]
De vierkantige haakjes betekenen hier “afronden naar boven”. Ook voor de complete bipartiete grafen is er zo’n formule (4).
\[\gamma(K_{m,n}) = \Bigl\lceil \frac{(m-2)(n-2)}{4} \Bigr\rceil \]
Zo blijkt niet alleen \(K_{3,3}\) genus 1 te hebben, maar bijvoorbeeld ook \(K_{3,6}\) en \(K_{4,4}\). Je kan de puzzel dus uitbreiden tot drie energiecentrales en vier, vijf of zelfs zes huisjes, of vier centrales en vier huisjes, maar niet meer (zonder extra handvaten). Ook hier wordt de puzzel zo natuurlijk alleen maar uitdagender!
Wiskundig gezien is hiermee de kous af … maar bij een concrete realisatie komt nog wel wat meer kijken. In een volgende blogpost lees je alles over échte koffietassen, vaatwasmachines, whiteboardstiften, en alle nog te stoppen gaatjes in die spreekwoordelijke kous. Wordt vervolgd!
- Kazimierz Kuratowski, Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, vol. 15, no. 1, p. 271–283, 1930. (↩)
- Klaus Wagner, Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, vol. 114, p. 570–590, 1937. (↩)
- Gerhard Ringel, John Youngs, Solution of the Heawood map-coloring problem. Proceedings of the National Academy of Sciences of the USA, vol. 60, 1968, p. 438–445. (↩)
- Gerhard Ringel, Das Geschlecht des vollständiger Paaren Graphen. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 28, p. 139–150, 1965. (↩)
