Théorie des graphes

Graphe G=(V,E) : V : ensemble de sommets (ordre n=|V|) E : ensemble d'arêtes (m=|E|) DEGRÉ d(v) : nombre d'arêtes incidentes à v Graphe connexe : tout sommet accessible depuis tout autre GRAPHE ORIENTÉ (digraphe) : Arcs (u,v) : de u vers v (u→v) Demi-degré entrant d⁺(v) et sortant d⁻(v)

Σᵥ d(v) = 2|E| (Somme des degrés = 2 × nombre d'arêtes) COROLLAIRE : Le nombre de sommets de degré impair est pair. DÉMONSTRATION : Chaque arête contribue 1 à d(u) et 1 à d(v) → contribue exactement 2 à Σd(v) → Σd(v) = 2|E| ✓

CHAÎNE EULÉRIENNE (traverse chaque arête une fois) : ↔ G connexe ET exactement 0 ou 2 sommets de degré impair CIRCUIT EULÉRIEN (chaîne eulérienne fermée) : ↔ G connexe ET tous sommets de degré pair Si 2 sommets impairs : ce sont les extrémités obligatoires Si 0 sommet impair : tout sommet peut être le départ

⚡ Problème des 7 ponts de Königsberg (Euler, 1736) : premier problème de théorie des graphes.