De zeven bruggen van Königsberg

4Graden

De graad deg(v) van een hoekpunt v is het aantal kanteinden dat het raakt. Anders gezegd: het is het aantal bruggen dat dat stuk land verlaat.

Als controle gebruiken we het handdruklemma. Elke kant heeft precies twee uiteinden, en elk uiteinde telt 1 bij de graad van één hoekpunt. Dus voor elke graaf geldt:

∑_{v ∈ V} deg(v) = 2 |E|,
en hier 3 + 5 + 3 + 3 = 14 = 2 × 7.

Een gevolg: de som van alle graden is even, dus elke graaf heeft een even aantal hoekpunten met oneven graad.

6Waarom het ertoe doet in de informatica

De stelling van Euler vervangt zoeken door tellen. Je hoeft geen routes uit te proberen, alleen graden te tellen:

from collections import Counter

def euler_kind(edges):
    """Classify a connected multigraph given as a list of edges (u, v)."""
    degree = Counter()
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
    odd = sum(1 for d in degree.values() if d % 2 == 1)
    if odd == 0:
        return "Eulerian circuit"
    if odd == 2:
        return "Eulerian path"
    return "neither"

koenigsberg = [("A", "B"), ("A", "B"), ("B", "D"), ("B", "D"),
               ("A", "C"), ("B", "C"), ("C", "D")]
print(euler_kind(koenigsberg))  # neither: four odd vertices

Dit draait in O(V + E) tijd: één keer over de kanten, dan één keer over de hoekpunten. Een volledige controle gaat ook na of alle kanten tot één samenhangende component behoren, met één keer breedte-eerst of diepte-eerst zoeken, wat eveneens O(V + E) kost. Een naïeve zoektocht die elke volgorde van de kanten uitprobeert, kan tot E! reeksen onderzoeken. Dat is 7! = 5.040 voor Königsberg, maar 20! ≈ 2,4 × 10¹⁸ voor een graaf met slechts 20 kanten.

Hetzelfde idee komt overal in de informatica terug:

• Het algoritme van Hierholzer bouwt een Eulercircuit in O(E) tijd. Volg ongebruikte kanten tot je terug bij het begin bent. Bouw daarna, vanuit een willekeurig hoekpunt van dat circuit dat nog ongebruikte kanten heeft, een nieuw circuit en voeg het erin in.
• Het Chinese-postbodeprobleem vraagt naar de kortste gesloten wandeling die elke kant minstens één keer gebruikt, zoals bij postbedeling, sneeuwploegen of veegwagens. Op ongerichte grafen is het in polynomiale tijd op te lossen. Koppel de oneven hoekpunten via een perfecte matching met minimaal gewicht, gewogen volgens de afstand van het kortste pad. Loop daarna het kortste pad tussen elk gekoppeld paar een tweede keer.
• De-Bruijngrafen bij genoomassemblage: DNA-sequencers lezen miljoenen korte fragmenten, die in overlappende deelstrings van lengte k worden geknipt. Elke deelstring wordt een gerichte kant van zijn eerste k − 1 letters naar zijn laatste k − 1 letters. Het genoom herbouwen wordt dan een zoektocht naar een Eulerpad. In gerichte grafen is de voorwaarde dat de ingraad gelijk is aan de uitgraad in elk hoekpunt, behalve dat het begin één extra uitgaande kant heeft en het einde één extra inkomende kant.
• Het Hamilton-contrast: verander “elke kant precies één keer” in “elk hoekpunt precies één keer” en geen eenvoudige graadtest werkt nog. Beslissen of een graaf een Hamiltonpad heeft, is NP-volledig. Er is geen polynomiaal algoritme bekend, en er een vinden zou P = NP bewijzen.