Grafentheorie: oefenopgaven met stapsgewijze oplossingen

1Hoekpunten, kanten en graden

Een graaf bestaat uit hoekpunten (punten) en kanten (lijnen tussen twee hoekpunten). In een enkelvoudige graaf zijn er geen lussen en geen dubbele kanten.

De graad van een hoekpunt is het aantal kanten dat erin samenkomt. Elke kant heeft twee uiteinden, dus hij telt voor 1 mee in de graad van elk uiteinde. Dat geeft het handenschudlemma:

Twee gevolgen: de som van de graden is altijd even, en het aantal hoekpunten met oneven graad is ook even.

• De volledige graaf K_n verbindt elk paar: n(n − 1)/2 kanten.
• De volledige bipartiete graaf K_m,n verbindt elk hoekpunt aan de ene kant met elk hoekpunt aan de andere kant: m·n kanten.
• Een k-reguliere graaf op n hoekpunten heeft n·k/2 kanten.

De adjacentiematrix heeft een 1 op (i, j) als i en j verbonden zijn. Voor een ongerichte graaf is hij symmetrisch, een rijsom is een graad, en het element (i, j) van Mᴸ telt de wandelingen van lengte L van i naar j.

2Euler en Hamilton

Een Eulercircuit gebruikt elke kant precies één keer en keert terug naar het begin. Een Eulerpad gebruikt elke kant één keer maar mag elders eindigen. Voor een samenhangende graaf geldt:

• alle graden even: er bestaat een Eulercircuit;
• precies twee oneven graden: er bestaat een Eulerpad, van het ene oneven hoekpunt naar het andere;
• meer dan twee oneven graden: geen van beide.

Een Hamiltoncircuit bezoekt elk hoekpunt precies één keer. Er is geen eenvoudige graadtest voor. In K_n zijn er (n − 1)!/2 verschillende Hamiltoncircuits: kies het beginpunt vast, orden de andere n − 1 hoekpunten en deel door 2 voor de twee richtingen.

3Bomen

Een boom is een samenhangende graaf zonder cykels. Elke boom met n hoekpunten heeft precies n − 1 kanten. Voeg je een willekeurige kant toe, dan ontstaat een cykel; haal je een willekeurige kant weg, dan valt hij uiteen.

Een bos van c bomen op n hoekpunten heeft n − c kanten. Een samenhangende graaf met m kanten houdt een opspannende boom over na het verwijderen van m − n + 1 kanten.

Het handenschudlemma telt bladeren: Σ deg = 2(n − 1). Een korte vorm is L = 2 + Σ (d − 2) over de hoekpunten met graad d ≥ 3. Een boom met twee hoekpunten van graad 3 en verder alleen bladeren heeft 2 + 1 + 1 = 4 bladeren.

4Dijkstra en minimaal opspannende bomen

Het algoritme van Dijkstra vindt kortste afstanden vanaf een beginpunt in een graaf met niet-negatieve gewichten.

1. Geef het beginpunt afstand 0 en elk ander hoekpunt ∞.
2. Leg het onafgehandelde hoekpunt met de kleinste afstand vast; zijn afstand is nu definitief.
3. Werk voor elke buur v bij: d(v) = min(d(v), d(u) + w(u, v)).
4. Herhaal tot het doel is vastgelegd.

Een minimaal opspannende boom verbindt alle hoekpunten met het kleinste totale gewicht. Kruskal sorteert de kanten van licht naar zwaar en neemt elke kant tenzij hij een cykel sluit. Prim laat één boom groeien vanuit een beginpunt en voegt steeds de lichtste kant toe die eruit vertrekt. Beide stoppen na n − 1 kanten.

5Veelgemaakte fouten

• Vergeten de som van de graden door 2 te delen om het aantal kanten te krijgen.
• Op een Eulercircuit testen zonder te controleren of de graaf samenhangend is.
• Een hoekpunt in Dijkstra vastleggen voordat het de kleinste voorlopige afstand heeft.
• De n − 1 lichtste kanten nemen zonder op cykels te controleren.
• De Hamiltoncircuits van K_n tellen als n! in plaats van (n − 1)!/2.

6Hoe tentamenvragen eruitzien

• Makkelijk: graden en kanten. Je gebruikt het handenschudlemma, telt de kanten van K_n, K_m,n, reguliere grafen en bomen, leest een adjacentiematrix af, of klikt het hoekpunt met een gegeven graad aan.
• Gemiddeld: Eulerpaden en bomen. Je beslist of een graaf een Eulercircuit of -pad heeft, telt de bladeren van een boom, telt de kanten die je weghaalt voor een opspannende boom, of telt Hamiltoncircuits in K_n.
• Moeilijk: kortste paden en opspannende bomen. Je laat het algoritme van Dijkstra lopen, vindt het hoekpunt dat in een gegeven ronde wordt vastgelegd, bepaalt het gewicht van een minimaal opspannende boom, klikt de kant aan die Kruskal of Prim als volgende toevoegt, of telt wandelingen met de adjacentiematrix.