Théorie des Graphes

Théorie des Graphes

Objectifs (compétences visées) : Appréhender les algorithmes des graphes utilisés dans les réseaux informatiques, dans les problèmes de calcul de coût minimal, dans la recherche du meilleur chemin et dans les méthodes d’ordonnancement (Gestion des projets,…)

En théorie des graphes, on désigne par graphe deux types d'objets :

* les graphes orientés (digraph en anglais)
* les graphes non orientés (graph ou undirected graph en anglais) que l'on appelle parfois simplement graphe

Formellement, un graphe orienté est un couple (S,A) où S est l'ensemble des sommets du graphe et A est l'ensemble des arcs du graphe. Chaque arc est un couple de sommet dont le premier élément est le sommet de départ de l'arc et le second élément est le sommet d'arrivée de l'arc.

Par exemple, une représentation graphique du graphe orienté G = (S,A) avec S = {A,B,C,D,F} et A = {(A,C), (A,B), (C,D), (D,A)} peut être la suivante :

graph1
Formellement, un graphe non orienté est un couple (S, A) où S est l'ensemble des sommets du graphe et A est l'ensemble des arêtes du graphe. Chaque arête est un couple de sommet non ordonné (ou un iensemble de deux éléments ou seul élément) dont les deux éléments relient deux sommets du graphe indépendamment de son orientation.

Par exemple, une représentation graphique du graphe non orienté G = (S,A), avec S = {A,B,C,D,E,F,H} et A={{A,B}, {A,C}, {C,F}, {B,D}, {D,E}, {D,H}} est la suivante :