-
Regulier
-
Volledig
Grafentheorie-lab
Een graaf is een verzameling punten, hoekpunten genoemd, verbonden door lijnen, kanten genoemd. Teken er hier een met een paar klikken en het lab vertelt je wat voor graaf het is: uit hoeveel delen hij bestaat, of het een boom is, met hoe weinig kleuren hij toe kan, of je hem in één haal kunt tekenen, en meer. Klik op een eigenschap om die in je graaf te zien, verander een kant en kijk hoe de antwoorden veranderen. Klik op een lege plek om een hoekpunt toe te voegen. Klik op een hoekpunt en dan op een ander om ze met een kant te verbinden; doe het nog eens om de kant weer weg te halen. Sleep een hoekpunt om het te verplaatsen. Zet de klik op Wist en klik op een hoekpunt of een kant om die te verwijderen. Als er een hoekpunt geselecteerd is, verwijdert Delete het en laat Esc het los. Klik op een eigenschap om die in de graaf te tonen. Voorbeeld laadt een bekende graaf, Willekeurige graaf maakt er een, Ordenen spreidt de hoekpunten uit en Complement verbindt precies de paren die nog niet verbonden waren. Ctrl+Z maakt een stap ongedaan.
Hoe het werkt
- Klik op een lege plek om een hoekpunt toe te voegen. Klik op een hoekpunt en dan op een ander om ze te verbinden; doe het nog eens om de kant weer weg te halen. Sleep een hoekpunt om het te verplaatsen.
- Lees de eigenschappen onder de graaf en klik op een ervan om die te tonen: een kleuring, de twee groepen, een Eulerroute, een opspannende boom, de kortste cykel of de diameter.
- Laad een voorbeeld zoals de Petersengraaf, maak een willekeurige graaf, neem het complement, of zet de klik op Wist om hoekpunten en kanten te verwijderen.
Wat de eigenschappen betekenen
De graad van een hoekpunt is het aantal kanten dat erop uitkomt. Een graaf is samenhangend als je vanuit elk hoekpunt via de kanten elk ander hoekpunt kunt bereiken, en een boom als hij samenhangend is en geen cykel heeft. Hij is bipartiet als de hoekpunten in twee groepen uiteenvallen en elke kant van de ene groep naar de andere loopt, en dat is precies het geval als hij geen cykel van oneven lengte heeft. Het chromatisch getal is het kleinste aantal kleuren waarmee buren altijd verschillende kleuren krijgen. De lengte van de kortste cykel heet de taille, en de diameter is de grootste afstand tussen twee hoekpunten, geteld in kanten.
Tekenen in één haal
Een Eulerroute gebruikt elke kant precies één keer. Leonhard Euler zag in 1736, bij de zeven bruggen van Königsberg, wat er in de weg staat: elke keer dat een route door een hoekpunt gaat, gebruikt hij twee van zijn kanten. Dus óf elke graad is even, en de route kan eindigen waar hij begon, óf precies twee graden zijn oneven, en de route moet van het ene naar het andere van die twee hoekpunten lopen. Carl Hierholzer bewees later dat dit, samen met de eis dat alle kanten in één deel liggen, ook genoeg is. Laad het huis-voorbeeld en zoek uit waar de haal moet beginnen.
Veelgestelde vragen
Wat is een graaf in de grafentheorie?
Een verzameling punten, hoekpunten of knopen genoemd, en lijnen tussen sommige paren daarvan, kanten genoemd. Het is geen grafiek van een functie: hij beschrijft alleen wat met wat verbonden is. Wegenkaarten, sociale netwerken, moleculen en computernetwerken zijn allemaal grafen.
Hoe wordt het chromatisch getal bepaald?
Het lab probeert de graaf te kleuren met één kleur, dan met twee, dan met drie, enzovoort, en doorzoekt voor elk aantal alle mogelijkheden die ertoe doen, waarbij het steeds als volgende het hoekpunt kleurt waarvan de buren al de meeste kleuren gebruiken. Het eerste aantal dat lukt, is het chromatisch getal. Voor de grafen die je hier kunt tekenen duurt dat hooguit een ogenblik; bij een heel lastige graaf stopt het zoeken vroegtijdig en wordt de waarde als bovengrens getoond.
Wanneer heeft een graaf een Eulerpad?
Als al zijn kanten in één deel liggen en niet meer dan twee hoekpunten een oneven graad hebben. Zonder oneven hoekpunten is er een Eulercircuit dat eindigt waar het begint; met twee begint elk Eulerpad bij het ene en eindigt het bij het andere. Het aantal oneven hoekpunten is altijd even, dus het is nooit precies één.
Wat is het complement van een graaf?
De graaf op dezelfde hoekpunten waarvan de kanten precies de paren zijn die eerst niet verbonden waren. Het complement van het complement is weer de graaf waarmee je begon. Het complement van de Petersengraaf is bijvoorbeeld 6-regulier, omdat elk hoekpunt met 3 van de andere 9 verbonden was.
Waarom is de Petersengraaf zo bekend?
Het is een kleine graaf met 10 hoekpunten en 15 kanten die een tegenvoorbeeld is voor veel hoopvolle vermoedens. Elk hoekpunt heeft graad 3, de kortste cykel heeft lengte 5, elke twee hoekpunten liggen hoogstens 2 kanten uit elkaar, en hij kan niet getekend worden zonder dat kanten elkaar kruisen. Het lab begint ermee.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor