Rappels de théorie des graphes

La plupart des problèmes exposés ci-après sont des problèmes de théorie des graphes. Un graphe $G$ est un couple $(S, A)$ où $S$ est l'ensemble des sommets (ou noeuds) et $A$ l'ensemble des arêtes (ou arcs). Nous ne verrons que des exemples dans lesquels l'ensemble $S$ est fini, sachant qu'il peut contenir n'importe quoi (des entiers, des réels, des couples de matrices, ds sous-ensembles de $\mbox{I\hspace{-.15em}R}$, des graphes, etc.). L'ensemble $A$ par contre ne peut contenir que des couples (si le graphe est orienté, des paires si le graphe n'es pas orienté) d'éléments de $S$. Par exemple, $G = (S, A)$ avec

$$S = \{(1, 2), (2, 3), (1, 3), (4, 5), (5, 4)\}$$

et

$$A = \{((1, 2),(2, 3)), ((1, 2),(1, 3)),((4, 5),(5, 4)),((5, 4), (4, 5)), ((1, 3),(1, 3)),((2, 3),(1, 2))\}$$

est un graphe (orienté en l'ocurrence). Si un graphe est orienté, on ne dit plus sommets mais noeuds, et on ne dit plus arêtes mais arcs.

Les graphes sont quelquefois valués, c'est-à-dire qu'il existe une application de $A$ dans un sous-ensemble de $\mbox{I\hspace{-.15em}R}$. Ils sont quelquefois pondérés, c'est-à-dire qu'il existe une application de $S$ dans un sous-ensemble de $\mbox{I\hspace{-.15em}R}$.