Graphes & Algorithmique

Graphe non orienté G=(V,E) : V = ensemble de sommets, E = ensemble d'arêtes Ordre = |V| (nombre de sommets) Degré d(v) = nombre d'arêtes incidentes à v Graphe connexe : il existe un chemin entre toute paire de sommets Théorème des poignées de main : Σᵢ d(vᵢ) = 2|E| Corollaire : le nombre de sommets de degré impair est pair Graphe complet Kₙ : Chaque sommet relié à tous les autres : |E|=n(n−1)/2

⚡ Chaîne : suite de sommets liés par des arêtes (arête visitée une seule fois). Cycle : chaîne fermée.

CHAÎNE EULÉRIENNE (traverse chaque arête exactement 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 les sommets de degré pair Si 2 sommets impairs → ce sont les extrémités de la chaîne eulérienne Si 0 sommet impair → on peut commencer par n'importe quel sommet Algorithme de construction : algorithme de Hierholzer

⚡ Chemin hamiltonien (chaque SOMMET une fois) ≠ eulérien. Le problème hamiltonien est NP-complet.