Het vakgebied grafentheorie is voor de puzzelmaker zowaar een goudmijn. In deze blogpost willen we een onverwacht open vraagstuk delen in de vorm van een (printklare) puzzel. Heb je nog nooit van grafen gehoord, geen zorgen, onze introductie tot het domein is voldoende om dit verhaal te kunnen volgen. Bovendien leer je in deze post ook een nieuwe, belangrijke klasse van grafen kennen.
Welke grafen nemen we onder de loep? Zoals de titel al weggeeft, gaat het over zogenaamde bomen. Dit zijn samenhangende grafen die geen enkele cykel bevatten, zoals de voorbeelden hieronder. Ze hebben als kenmerkende eigenschap dat er tussen elke twee toppen precies één pad bestaat — er bestaat er zeker één want de graaf is samenhangend, en mochten er twee of meer bestaan, dan kun je daar een verboden cykel in herkennen.
Bomen zijn belangrijk in de grafentheorie omdat die een soort “skelet” vormen voor grotere samenhangende grafen. Door uit zo’n algemenere graaf cykels te elimineren door zolang als nodig bogen weg te knippen, hou je immers precies een boom over (een opspannende boom). De figuur hieronder illustreert dat dat vaak op heel veel manieren kan! Het idee heeft ook praktische toepassingen. In bijvoorbeeld bestandsuitwisselingen over een netwerk van computers zijn cykels bijzonder ongewenst: ze zorgen voor onnodige extra transmissies, of zelfs overbelasting van het netwerk doordat computers telkens opnieuw data in een rondje doorsturen! De standaardmanier om dit probleem aan te pakken, maakt gebruik van opspannende bomen in de vorm van het Spanning Tree Protocol.
Nog een belangrijke eigenschap van abstracte bomen is dat die telkens één top meer heeft dan het aantal bogen. Dat is niet zo lastig in te zien. Een boom heeft immers altijd toppen van graad 1 (zogenaamde bladeren). Door zo’n blad te snoeien, verkrijgen we een kleinere boom met één top en één boog minder. Dat kunnen we herhalen tot er slechts een enkele top overblijft. Met andere woorden, een boom met n bogen heeft precies n + 1 toppen.
Daar kunnen we volgend speels vraagstukje uit halen. We kunnen in de n + 1 toppen van een boom elk een verschillend label uit de n + 1 getallen {0, 1, 2, …, n} invullen. Voor elke boog berekenen we dan het verschil tussen de getallen in de twee eindtoppen. De uitkomsten kunnen elk van de waarden {1, 2, …, n} bedragen. Wanneer elk van die getallen precies één keer optreedt bij een zekere boog, dan noemen we de labeling gracieus. Hieronder staan enkele voorbeelden met n = 5 (dus 5 bogen en 6 toppen) die de bedoeling duidelijk maken — de eerste twee zijn gracieus, de derde niet.
De opgave is nu eenvoudig: kun je elke boom een gracieuze labeling van de toppen toekennen? Of kortweg, is elke boom gracieus?
Het probleem klinkt eenvoudig genoeg, wiskundigen hebben voor tal van speciale families bomen inderdaad kunnen aantonen dat zulke bijzondere labelingen altijd bestaan, computerzoektochten hebben gigantisch veel exemplaren gecontroleerd, maar een algemene oplossing voor alle bomen is nog niet gekend. Er verschijnen regelmatig nieuwe preprints met claims van bewijzen … maar die blijken steevast fouten of gaten te bevatten. Het vermoeden dat elke boom gracieus is, staat bekend als het vermoeden van Ringel–Kotzig (naar Gerhard Ringel en Anton Kotzig). Oorspronkelijk werden gracieuze labelingen eigenlijk voor algemene grafen ingevoerd door Alexander Rosa (1). Hij sprak over β-valuaties; het was Solomon Golomb die hun charmantere naam invoerde.
Probeer zelf eens! Hieronder staan alle elf mogelijke bomen met 7 toppen afgebeeld. Kun je in elk van de voorbeelden de getallen 0 tot en met 6 invullen in de toppen volgens de voorgeschreven spelregels? Je kan een printklare pdf via deze link downloaden.
Een interessante familie van bomen waarvoor het vermoeden geverifieerd werd, zijn de zogenaamde rupsgrafen. Dat zijn bomen die niet al te veel afwijken van een enkel pad: er moet één centrale “ruggengraat” zijn, waarop rechtstreeks nog bladeren mogen ontspruiten. Iets rigoureuzer, alle toppen moeten hoogstens op afstand 1 liggen van een centraal pad. Tussen de exemplaren met 7 toppen is er slechts één boom die geen rupsgraaf is — vind je terug dewelke? Naarmate het aantal toppen toeneemt en bomen steeds complexer kunnen worden en verder vertakken, worden de rupsgrafen steeds zeldzamer.
A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed.
Frank Harary & Allen Schwenk (2)
Dat alle rupsen gracieuze bomen zijn, is al terug te vinden in het originele werk van Rosa (1) en is elegant genoeg om hier te vermelden. Het steunt op de observatie dat rupsgrafen kunnen worden getekend volgens een soort schoenvetervoorstelling, waaruit een expliciete en systematische labeling kan worden opgesteld. Hieronder staat een illustratie, in de vorm van twee weergaven van eenzelfde rupsgraaf (met het centrale pad gemarkeerd). In de voorstelling rechts zie je dat de bogen van boven naar beneden telkens precies één top zakken, hetzij aan de linkerkant, hetzij aan de rechterkant. De toplabels zijn zó opgesteld dat dan ook de booglabels telkens precies één zakken, van 17 bovenaan tot 1 onderaan. We laten het aan de gemotiveerde lezer om de details uit te werken!
