Algorithmes et structures des données 2 ~ FSTInfo

Graphes

Définition

Un graphe est un ensemble d’objets modélisés par des sommets, et mis en relation (binaire). Ces relations sont modélisés par des arcs ou des arêtes. Un graphe orienté [non orienté] est un couple

où S est un ensemble fini de sommets, et A un ensemble de paire ordonnées [couple] de sommets appelés arcs [arêtes].

Terminologie

Un graphe simple est sans boucle*, et sans liens multiples. Dans un graphe orienté, on dit que y est le successeur de x s’il existe un arc qui mène de x vers y ; on dit en outre que y est adjacent à x. Pour un graphe orienté, on dit simplement que x et y sont adjacents. Un graphe est dit complet si pour tout couple de sommet il existe un arc (ou une arête) les joignant. Dans un graphe orienté, le demi-degré extérieur [intérieur] d’un sommet x, que l’on note

[

], est le nombre d’arcs ayant x comme extrémité initiale (finale). Le degré de x est

. Pour un graphe non orienté, on définit uniquement le degré d’un sommet x

. Dans un graphe orienté, on appelle chemin de longueur L une suite de L+1 sommets

telles que

forme un arc. Pour un graphe non orienté, on parle de chaîne. Dans un graphe orienté [non orienté], un chemin [une chaîne] dont tous les arcs [arêtes] sont distincts et tels que les sommets aux extrémités coïncident est un circuit [un cycle]. Un graphe orienté est fortement connexe si pour toute paire de sommets distincts s et s’, il existe un chemin de s vers s’ et un chemin de s’ vers s. Un graphe non orienté est connexe, si pour toute paire de sommets distincts, il existe une chaîne les joignant. Une composante fortement connexe [connexe] est un sous-graphe fortement connexe [connexe] maximal.

Graphe et Arbre

En théorie des graphes, un arbre est un graphe non orienté, connexe et sans cycle. Soit G un graphe orienté, on appelle racine de G un sommet r tel que, pour tous sommets x distincts de r, il existe un chemin de r vers x. Une arborescence est un graphe orienté G admettant une racine et tel que le graphe obtenu à partir de G en enlevant l’orientation soit un arbre.

Signature graphe orienté

sorte sommet
utilise booléen, entier
opérations
                s : entier à sommet
                n° : sommet à entier
                – arc – : sommet x sommet à booléen
                d⁺: sommet à entier
                ième_succ : sommet x entier à sommet
                prem_succ : sommet à sommet
                succ_suivant : sommet x sommet à sommet

Pour les graphes non orientés, on dispose de la même signature en remplaçant – arc – par – arête – et d⁺ par d.

Représentation des graphes

On aura deux possibilités classiques de gestion de la mémoire : contiguë et chaînée.

Représentation contiguë : Soit n le nombre de sommet d’un graphe ; on définit la matrice d’incidence de dimension n x n noté G et tel que

ssi il existe un arc de i vers j. Si le graphe est non orienté la matrice d’incidence est symétrique.

type graphe = tableau[1 à n, 1 à n] de booléen.

La complexité en espace est en O(n²), parcourir les successeurs d’un sommet se fait en O(n), savoir si y est le successeur de x se fait en O(1).

Représentation chaînée : Pour chaque sommet s_i, on forme la liste d’adjacence, qui est la liste chaînée de tous le successeur de s_i.

type graphe = tableau[1 à n] d’adresse de cellule;

cellule = structure

numéro : entier de 1 à n;

suivant : adresse de cellule;

fin;

Soit

. La complexité en espace est en n + 2p. Le parcours des successeurs d’un sommet s’effectue en

. La consultation complète est en

. Savoir si y est le successeur de x se fait en

, dans le pire des cas.

Remarque. Le chaînage peut être simulé dans un tableau. Pour un graphe non orienté, il y a redondance** d’information.

Parcours en profondeur d’un graphe orienté

Le parcours en profondeur un parcours récursif, simulable par une pile.
Principe : On utilise une marque (vecteur de n booléens) pour marquer les sommets au fur et à mesure qu’on les rencontre. à partir d’un x de départ, non marqué, on avance dans le graphe en allant toujours vers un nouveau successeur non marqué ; les sommets retenus à chaque fois sont marqués. Quand on ne peut plus avancer, on revient au choix précédent, et on itère la méthode.

Procédure Profondeur(x : sommet) ;

début

i ß n°(x) ;

marque[i]ß vrai ;

pour j de 1 à d⁺(x) faire

début

y ß ième_succ(x, j) ;

k ß n°(y) ;

si non marque[k] alors Profondeur(y) ;

fin ;

fin_Profondeur ;

Programme principal

début

pour i de 1 à n faire marque[i] ß faux ;

pour i de 1 à n faire

si non marque[i] alors profondeur(s(i)) ;

fin.

Pour les graphes non orientés, on dispose du même algorithme en remplaçant d⁺(x) par d.

Les sommets ne sont marqués qu’une seule fois et l’algorithme parcourt un fois et une seule les listes d’adjacence : complexité en

, ce qui donne

pour les listes d’adjacence et

pour les matrices d’adjacence.

On considère les arcs x à y tels que Profondeur(x) appelle Profondeur(y). Ces arcs couvrants constituent une forêt couvrante constituée d’arborescences disjointes et dont les racines sont les sommets de départ. Les graphes obtenu sans orientation sont des arbres (graphe non orienté, connexe et sans cycle). La forêt couvrante a autant d’arbres recouvrants qu’il y a de composantes connexes dans le graphe. Ainsi le parcours en profondeur résout le test de connexité en temps linéaire.

Parcours en largeur

Le parcours par largeur ou par niveau est un parcours itératif qui fonctionne avec une file.

Principe : On part d’un sommet x et on visite tous les successeurs y de x ; on réitère l’algorithme sur les sommets y dans l’ordre où on les a rencontrés à partir de x. On utilise toujours une marque de sommets. On utilise une file pour gérer ce parcours par niveaux.

Procédure Largeur(x :sommet)

début

file_vide(file) ;

i ß n°(x) ;

marque[i] ß vraie ;

ajouter(file, x) ;

tant que non est_vide(file) faire

début

y ß premier(file) ;

retirer(file) ;

pour i de 1 à d⁺(y) faire

début

z ß ième_succ(y,i) ;

j ß n°(z);

si non marque[j] alors

début

marque[j] ß vraie;

ajouter(file,z);

fin;

fin ;

Programme principal

début

pour i de 1 à n faire marque[i] ß faux ;

pour i de 1 à n faire

si non marque[i] alors Largeur(s(i)) ;

fin.

On a la même complexité que pour le parcours en profondeur. L’algorithme pour un graphe non orienté s’obtient simplement en remplaçant d⁺ par d. On a la même propriété sur la forêt couvrante et les composantes connexes que pour le parcours en profondeur.

* lien d’un sommet sur lui-même

** y est le successeur de x et réciproquement

FSTInfo

lundi 9 novembre 2015