Les graphes

La théorie des graphes est aujourd'hui un outil majeur de modélisation et de résolution de problèmes dans un très grand nombre de domaines, des sciences fondamentales aux applications technologiques les plus concrètes. Un graphe est défini par ses sommets et ses arcs. Les sommets forment un ensemble S quelconque (quoique fini en pratique), et les arcs un sous-ensemble A de $S\times S$ ; autrement dit, un graphe est le graphe d'une relation binaire. Si $a=(u,v)\in A$, on dit que a est un arc d'extrémité initiale u et d'extrémité finale v, on le note $a: u\to v$ ; on dit aussi que v est un sommet adjacent à u, ou est un successeur de u.

La théorie des graphes est pourvue d'un vocabulaire riche mais assez intuitif (figure 2.7). Par exemple, une chaîne de longueur $k\ge 0$ d'un graphe est une suite de k+1 sommets $v_0, v_1, \dots, v_k$, avec $v_i\to v_{i+1}$ ou $v_{i+1}\to v_{i}$ pour $0\le i\le k$. Une chaîne est un chemin si ses arcs sont consécutifs : $v_0\to v_1\to\dots v_k$. Un graphe est connexe (resp. fortement connexe) si deux sommets quelconques sont reliés par une chaîne (resp. un chemin). Les composantes connexes sont les classes d'équivalence de la relation << être relié par une chaîne >>. S'il existe un chemin de v₀ vers v_k, ont dit que v_k est accessible à partir de v₀, ce qu'on note $v_0\to^{\star}v_k$ ; la relation d'accessibilité est un préordre (relation réflexive et transitive). Un chemin est un circuit si v_k=v₀ et $k\ge 1$. Les composantes fortement connexes sont les classes de la relation d'équivalence induite par l'accessibilité, définie entre les sommets u et v quand $u\to^{\star}v$ et $v\to^{\star}u$.