samedi 5 janvier 2013

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. 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 v0 vers vk, ont dit que vk est accessible à partir de v0, 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 vk=v0et $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$.


 Implémentation des graphes
on
Libellés :

Aucun commentaire:

Enregistrer un commentaire

Inscription à : Publier les commentaires (Atom)