] >
Het abstracte karakter maakt dat de wiskunde geschikt is voor het maken van modellen van realistische zaken. Dat kunnen zaken zijn uit de techniek, de economie, de natuurwetenschappen, etc., maar ook uit de natuur of het dagelijks leven. Het wiskundige model is een abstractie waarbij dingen die als niet essentieel worden gezien, zijn weggelaten. Het wiskundig model leent zich voor logisch redeneren. Eigenschappen van zo’n model laten zich vertalen in uitspraken over realistische zaken. Dit is de algemene situatie bij het toepassen van wiskunde. Hier beschouwen we zo’n eenvoudige wiskundige structuur: een graaf.
Bij een gezelschap van personen geldt voor elk tweetal dat er twee elkaar uitsluitende mogelijkheden zijn: ze kennen elkaar of ze kennen elkaar niet. Willen we aangeven wat de situatie is, dan kunnen we alle tweetallen van personen die elkaar kennen, opsommen. Willen we weten of elk tweetal een gemeenschappelijke kennis heeft in dit gezelschap, dan is het verder niet van belang dat het om personen gaat, laat staan hoe ze heten, wat hun geslacht is en of ze wel of niet aardig zijn. Nummeren we de personen met bijv. t/m , dan kunnen we verder alles wat van belang is vastleggen door de tweetallen op te sommen, bijv. , , , , , , , , , , , . Meer hoef je niet te weten om te kunnen concluderen dat er in dit gezelschap personen zijn zonder gemeenschappelijke kennis in het gezelschap: persoon kent alleen , en ; persoon kent alleen , en . Van de situatie kun je een plaatje tekenen: stippen voor de personen (of getallen) en verbindingslijntjes als ze elkaar kennen.
Zo’n plaatje is handig als je een goed overzicht van de situatie wilt hebben. Je ziet ook dat je hetzelfde zou krijgen als je de hoekpunten van een kubus neemt en als eigenschap van een tweetal hoekpunten: door een ribbe (van de kubus) verbonden zijn. Ook krijg je het door de zijvlakken van een regelmatig achtvlak (een octaëder) te nemen en als eigenschap van een tweetal zijvlakken: aan elkaar grenzen. De structuur die we hier hebben gekregen is een voorbeeld van een graaf. Een graaf bestaat uit een verzameling (de hoekpunten van de graaf) tezamen met een verzameling van deelverzamelingen ervan die elk uit twee elementen bestaan (de ribben van de graaf). Het is een typisch voorbeeld van een wiskundige structuur: een verzameling met daarbij nog iets dat aan bepaalde eisen moet voldoen. We geven een meer precieze definitie.
1.8 Definitie. Een graaf is een eindige verzameling tezamen met een verzameling bestaande uit deelverzamelingen van die elk precies twee elementen hebben. De elementen van noemen we de hoekpunten van de graaf, die van de ribben. Het meervoud van graaf is grafen.
In het hierboven beschreven geval hebben we dus en
Een graaf bestaat dus uit twee verzamelingen: de verzameling van de hoekpunten van en die van de ribben van . Ribben zijn niets anders dan tweetallen (verschillende) hoekpunten. De verzameling van de hoekpunten van een graaf noteren we ook wel als en die van de ribben als .
Dit is een eerste voorbeeld van een abstracte wiskundige structuur. Het begrip ‘graaf’ is geheel beschreven in termen van verzamelingen. Er is niets anders vastgelegd van de hoekpunten dan dat ze een verzameling vormen. Over de aard van deze hoekpunten weten we verder niets. De definitie vertelt je wat je moet hebben wil je kunnen spreken van een graaf.
1.9 Voorbeeld. Een bekend puzzeltje bestaat uit het verschuiven van van t/m genummerde vierkante blokjes op een veld van bij vierkanten. Het is de kunst om, uitgaande van een willekeurige beginsituatie, zo te schuiven dat de blokjes op volgorde liggen en dat het vakje rechtsonder leeg is, zoals afgebeeld in Figuur 1.6. Je zou een graaf van de situatie kunnen maken: de hoekpunten zijn de toestanden van het spel en de ribben geven aan dat je door één keer schuiven van de ene toestand in de andere kunt komen. We gaan er geen plaatje van maken: er zijn hoekpunten en nog meer ribben. Deze puzzel, met in de beginstand alleen de blokjes en verwisseld, werd in 1878 door Sam Loyd geïntroduceerd onder de naam ‘14-15 puzzle’. Om de puzzel te analyseren is het beter om er meer structuur in te ontdekken dan alleen die van een graaf. We doen dat in hoofdstuk 10, paragraaf 10.5.
Een sterk vereenvoudigde versie van het spel bestaat uit blokjes op een veld van bij . Er zijn dan slechts toestanden. Vanuit iedere toestand kun je precies twee andere bereiken. Ga je schuiven, dan schuif je terug waar je vandaan komt of je schuift verder. Het is steeds duidelijk wat je moet doen en na enig schuiven is het wel duidelijk of je de blokjes in de goede volgorde kunt krijgen. Iedere toestand kun je aangeven door de getallen , , en in een volgorde te plaatsen, bijvoorbeeld om de toestand mee aan te geven die in Figuur 1.7 is afgebeeld: in vakje , in vakje en in vakje . De gebruiken we om aan te geven welk vakje leeg is. Van een toestand in een andere kom je door in de notatie de te verwisselen met een van de andere, maar dat mag niet als de twee getallen in de posities en staan, en ook niet als zij in de posities en staan. In Figuur 1.8 een plaatje van deze graaf.
Je ziet dat de toestanden in twee soorten voorkomen: in de helft van de gevallen kun je de goede volgorde bereiken. Bij de puzzel met 15 blokjes is hetzelfde het geval. Dat is moeilijker om in te zien.
1.10 Voorbeeld (Toren van Hanoi). Bij de Toren van Hanoi met schijven hoort een graaf : de hoekpuntenverzameling tezamen met de ribbenverzameling . (Dus en .) Van een graaf kun je een plaatje maken met stippen voor de hoekpunten en verbindingslijntjes tussen de stippen voor de ribben. Figuur 1.9 is een plaatje van de graaf . Deze graaf is samenhangend, d.w.z. je kunt via de ribben van ieder hoekpunt naar ieder ander hoekpunt komen. Is het hoekpunt linksonder en het hoekpunt bovenin , dan blijkt uit de graaf dat je in zetten van de stand naar de stand kunt komen. Omdat de graaf samenhangend is, kun je beginnend bij iedere stand in iedere andere stand komen door het doen van zetten.