Théorie des graphes

Graphe G = (S, A) : S ensemble de sommets, A ensemble d'arêtes (paires de sommets). • Degré d(s) : nombre d'arêtes issues de s • Graphe orienté (digraphe) : les arêtes ont un sens (flèches) • Graphe complet Kₙ : chaque paire de sommets est reliée • Graphe biparti : sommets en deux groupes, arêtes seulement entre groupes • Chaîne : suite de sommets reliés par des arêtes • Cycle : chaîne fermée

Un graphe connexe admet une chaîne eulérienne (passant une fois et une seule par chaque arête) si et seulement si il a exactement 0 ou 2 sommets de degré impair. • 0 sommet impair → circuit eulérien (retour au départ) • 2 sommets impairs → chaîne eulérienne (de l'un à l'autre) Application : problème des 7 ponts de Königsberg.

Pour un graphe à n sommets, la matrice d'adjacence M est une matrice n×n où : M[i][j] = 1 si arête de i vers j, 0 sinon (graphe non orienté : matrice symétrique). Propriété : M^k[i][j] = nombre de chemins de longueur k de i vers j. Utilisation : calculer M², M³ pour compteur les chemins de longueur 2, 3, etc.