Modes de représentation d’un graphe

Cours modes de représentation d’un graphe, tutoriel & guide de travaux pratiques en pdf.

Quelques notions de base

Definitions et representations

Principales définitions
Un graphe orient  G = (X; U) est la donnee de deux ensembles :
– Un ensemble X = fx₁; x₂;  ; x_ng dont les elements sont appeles sommets ;
– Un sous-ensemble U X X note U = fu₁; u₂; ; u_mg dont les elements sont appeles arcs.
Pour un arc u = (x_i; x_j ), le sommet x_i s’appelle extremit initiale (ou origine) et x_j son extremit nale (ou destination).
Dans l’arc (x_i; x_j ), on dit que le sommet x_j est un successeur de x_i. On dit aussi que le sommet x_i est un predecesseur de x_j .
Lorsque x_i = x_j , l’arc (x_i; x_i) s’appelle une boucle. Un arc prive de son orientation s’appelle une ar^ete.
Deux sommets sont dits adjacents s’ils sont joints par un arc (ou une ar^ete), et deux arcs sont dits adjacents s’ils ont au moins une extremit commune.
Un sous-graphe est obtenu par suppression d’un certain nombre de sommets (et par consequent de tous les arcs qui leur sont lies).
Un graphe partiel est obtenu par suppression d’un certain nombre d’arcs.

Modes de representation d’un graphe

a) Representation par dictionnaire (liste) : Il s’agit d’un tableau a entree simple ou chaque ligne correspond a un sommet et comporte la liste de ses predecesseurs (dictionnaire des predecesseurs) ou de ses successeurs (dictionnaire des successeurs).

Chemins dans un graphe orient

Un chemin est une succession d’arcs adjacents de m^eme sens.
Un circuit est un chemin ferm dans le sens ou les deux extremites initiale et nale sont confondues. Un chemin est dit de longueur p 2 N s’il est constitue de p arcs distincts.

Recherche de chemin optimal

Soit G = (X; U) un graphe value ou a chaque arc a 2 U on associe une longueur l(a). Cette longueur peut representer une duree de parcours, un bene ce de transport, … etc.

Recherche du plus court chemin a origine unique dans un graphe sans boucle et sans circuit

Lorsqu’on cherche un plus court chemin d’un sommet xe x₁ a tous les autres sommets du graphe, plusieurs algorithmes peuvent etre appliques ( algorithme de Bellman-Ford, algorithme de Dijkstra, ) selon les proprietes et la nature du graphe. Le principe de ces algorithmes etant d’affecter a chaque sommet x_i une marque m_i. En n d’algorithme, cette marque represente la longueur d’un plus court chemin de l’origine x₁ au sommet consider x_i.