Grafentheorie
Punten met lijnen ertussen: meer is een graaf niet. Toch beschrijft hetzelfde plaatje een wegenkaart, een vriendennetwerk, een molecuul en het internet, en de vragen die je erover kunt stellen, van het aantal kleuren dat nodig is tot de vraag of je hem in één haal kunt tekenen, houden wiskundigen al sinds 1736 bezig.
Hoekpunten en kanten
Een graaf heeft hoekpunten, ook wel knopen genoemd, en kanten, die elk twee hoekpunten verbinden. Waar de hoekpunten getekend worden, maakt niet uit, alleen welke paren verbonden zijn, dus dezelfde graaf kan er op papier heel verschillend uitzien. De grafen in het lab zijn enkelvoudig: geen kant van een hoekpunt naar zichzelf en hoogstens één kant tussen twee hoekpunten. Met n hoekpunten zijn er hoogstens n(n − 1) / 2 kanten mogelijk; een graaf die ze allemaal heeft, heet volledig, en K5 is de volledige graaf met vijf hoekpunten.
Graden en het handdruklemma
De graad van een hoekpunt is het aantal kanten dat erop uitkomt. Tel je alle graden op, dan krijg je precies twee keer het aantal kanten, want elke kant heeft twee uiteinden en wordt bij elk uiteinde één keer geteld. Dat is het handdruklemma: in elke groep mensen tellen de handdrukken, per persoon geteld, op tot twee keer het aantal handdrukken. Het betekent ook dat het aantal hoekpunten met een oneven graad altijd even is. Een graaf waarin elk hoekpunt dezelfde graad k heeft, heet k-regulier.
Samenhangende grafen, bomen en cykels
Een graaf is samenhangend als je via de kanten van elk hoekpunt naar elk ander hoekpunt kunt komen; anders valt hij uiteen in delen, componenten genoemd. Een cykel is een rondje dat terugkomt bij het begin zonder een hoekpunt twee keer te gebruiken, en de lengte van de kortste heet de taille. Een samenhangende graaf zonder cykel is een boom, en een boom met n hoekpunten heeft altijd precies n − 1 kanten: met één minder valt hij uiteen, met één meer heeft hij een cykel. Elke samenhangende graaf bevat een opspannende boom: een boom die alle hoekpunten bereikt met maar een deel van de kanten.
Bipartiete grafen en kleuren
Kleur de hoekpunten zo dat geen kant twee hoekpunten van dezelfde kleur verbindt. Het kleinste aantal kleuren waarmee dat lukt, is het chromatisch getal. Eén kleur is alleen genoeg als er geen kanten zijn. Twee kleuren zijn genoeg precies als de graaf bipartiet is: de hoekpunten vallen in twee groepen uiteen en elke kant loopt van de ene naar de andere. Dénes Kőnig liet in 1936 zien dat dit hetzelfde is als geen cykel van oneven lengte hebben, omdat een oneven cykel niet afwisselend twee kleuren kan krijgen. Voor drie of meer kleuren is zo'n eenvoudige toets niet bekend: bepalen of drie kleuren genoeg zijn, is NP-volledig, dus programma's gaan zoeken, net als het lab.
Een voorbeeld: de Petersengraaf
Neem een vijfhoek A–B–C–D–E met daarin een vijfpuntige ster F–H–J–G–I, en verbind elke hoek van de vijfhoek met een punt van de ster: A–F, B–G, C–H, D–I en E–J. Dat is de Petersengraaf, met 10 hoekpunten en 15 kanten. Elk hoekpunt heeft graad 3, dus de graden tellen op tot 30, twee keer 15. De kortste cykel heeft lengte 5, dus er zit geen driehoek in, maar de vijfhoek is een oneven cykel, dus de graaf is niet bipartiet en heeft 3 kleuren nodig. Elke twee hoekpunten liggen hoogstens 2 kanten uit elkaar, dus de diameter is 2. Alle tien graden zijn oneven, dus er is geen Eulerroute, en de graaf kan niet zonder kruisingen getekend worden.
Eulerpaden en de bruggen van Königsberg
De stad Königsberg had zeven bruggen die vier stukken land verbonden, en men vroeg zich af of je over elke brug precies één keer kon lopen. In 1736 liet Leonhard Euler zien dat dat niet kon, en daarmee begon de grafentheorie. Elke keer dat een wandeling door een stuk land gaat, gebruikt hij twee bruggen, dus alleen het begin en het eind mogen een oneven aantal bruggen hebben, en alle vier de stukken land van Königsberg hadden een oneven aantal. Een route die elke kant één keer gebruikt, heet nu een Eulerpad, of een Eulercircuit als hij eindigt waar hij begon. Carl Hierholzer bewees in 1873 dat de voorwaarde ook genoeg is: als alle kanten in één deel liggen en hoogstens twee graden oneven zijn, bestaat de route, en zijn methode om rondjes aan elkaar te koppelen vindt hem nog steeds.
Afstand, diameter en het complement
De afstand tussen twee hoekpunten is het kleinste aantal kanten op een pad ertussen, en de diameter is de grootste afstand in de graaf; in een graaf die niet samenhangend is, is die oneindig. Sociale netwerken hebben een kleine diameter: dat is het idee achter de six degrees of separation. Het complement van een graaf heeft dezelfde hoekpunten en verbindt precies de paren die niet verbonden waren. Van een graaf en zijn complement is er altijd minstens één samenhangend.
Ontdek het zelf
Het lab opent met de Petersengraaf in drie kleuren. Klik op Graden en controleer het handdruklemma, klik op Bipartiet om een oneven cykel te zien, laad dan de kubus en zie de twee groepen verschijnen. Laad het huis en klik op Eulerroute om te zien waar de haal moet beginnen. Teken je eigen graaf en voeg kant voor kant toe: zie de kortste cykel korter worden, de diameter dalen en het chromatisch getal stijgen als de laatste kant van een K4 erbij komt.
Veelgestelde vragen
Wat is het verschil tussen een pad, een route en een wandeling?
Een wandeling is elke reeks hoekpunten die door kanten verbonden zijn, en mag zowel hoekpunten als kanten herhalen. Een route mag hoekpunten herhalen maar geen kanten; daarom kan een Eulerroute meerdere keren door hetzelfde hoekpunt gaan. Een pad herhaalt geen van beide.
Wat is de vierkleurenstelling?
Die zegt dat elke graaf die je op papier kunt tekenen zonder dat kanten elkaar kruisen, met hoogstens vier kleuren gekleurd kan worden, zodat geen enkele landkaart meer dan vier kleuren nodig heeft. Kenneth Appel en Wolfgang Haken bewezen hem in 1976 met hulp van een computer: de eerste grote stelling die op die manier bewezen werd.
Wat is een hamiltoncykel?
Een cykel die elk hoekpunt precies één keer bezoekt, in plaats van elke kant. Het lijkt op de vraag van Euler, maar er is geen eenvoudige toets voor bekend: bepalen of een graaf er een heeft, is NP-volledig. De Petersengraaf heeft wel een hamiltonpad, maar geen hamiltoncykel.
Waar wordt grafentheorie gebruikt?
Routeplanners zoeken in wegengrafen, zoekmachines rangschikken webpagina's op hun links, compilers kleuren grafen om processorregisters te verdelen, roosters voorkomen botsingen door een graaf van conflicten te kleuren, scheikundigen tellen moleculen als grafen, en netwerken van computers, hoogspanningsleidingen en vrienden worden als grafen bestudeerd.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open het Grafentheorie-lab