Les sept ponts de Königsberg

4Les degrés

Le degré deg(v) d’un sommet v est le nombre d’extrémités d’arêtes qui le touchent. De façon équivalente, c’est le nombre de ponts qui partent de ce morceau de terre.

Pour vérifier, utilisons le lemme des poignées de main. Chaque arête a exactement deux extrémités, et chaque extrémité ajoute 1 au degré d’un sommet. Donc, pour tout graphe,

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

Une conséquence : la somme de tous les degrés est paire, donc tout graphe a un nombre pair de sommets de degré impair.

6Pourquoi c’est important en informatique

Le théorème d’Euler remplace une recherche par un comptage. Inutile d’essayer des parcours : il suffit de compter les degrés :

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

Cela s’exécute en temps O(V + E) : un passage sur les arêtes, puis un sur les sommets. Une vérification complète contrôle aussi que toutes les arêtes appartiennent à une seule composante connexe, avec un parcours en largeur ou en profondeur, lui aussi en O(V + E). Une recherche naïve qui essaie tous les ordres possibles des arêtes peut examiner jusqu’à E ! séquences. Cela fait 7 ! = 5 040 pour Königsberg, mais 20 ! ≈ 2,4 × 10¹⁸ pour un graphe de seulement 20 arêtes.

La même idée apparaît partout en informatique :

• L’algorithme de Hierholzer construit un cycle eulérien en temps O(E). On suit des arêtes inutilisées jusqu’à revenir au départ. Ensuite, depuis n’importe quel sommet de ce cycle qui a encore des arêtes inutilisées, on construit un autre cycle et on l’insère.
• Le problème du postier chinois cherche la plus courte marche fermée qui utilise chaque arête au moins une fois, comme pour la distribution du courrier, les chasse-neige ou les balayeuses de rue. Sur les graphes non orientés, il se résout en temps polynomial. On apparie les sommets de degré impair par un couplage parfait de poids minimum, pondéré par la distance du plus court chemin. Puis on parcourt une seconde fois le plus court chemin entre chaque paire appariée.
• Les graphes de de Bruijn en assemblage de génomes : les séquenceurs d’ADN lisent des millions de courts fragments, découpés en sous-chaînes qui se chevauchent, de longueur k. Chaque sous-chaîne devient une arête orientée allant de ses k − 1 premières lettres à ses k − 1 dernières lettres. Reconstruire le génome revient alors à chercher un chemin eulérien. Dans les graphes orientés, la condition est que le degré entrant soit égal au degré sortant en chaque sommet, sauf que le départ a une arête sortante de plus et l’arrivée une arête entrante de plus.
• Le contraste hamiltonien : remplacez « chaque arête exactement une fois » par « chaque sommet exactement une fois » et aucun simple test de degrés ne fonctionne plus. Décider si un graphe possède un chemin hamiltonien est NP-complet. Aucun algorithme polynomial n’est connu, et en trouver un prouverait que P = NP.