INFORMATIQUE GRAPHE

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[1], 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[2] 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

                n°(x) ;

                marque[i] v rai ;

                pour j de 1 à d⁺(x) faire

                                début

                              ième_succ(x, j) ;

                          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) ;

                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

ième_succ(y,i) ;

n°(z);

si non marque[j] alors

                 début

                 marque[j]  vraie;

                 ajouter(file,z);

                 fin;

fin ;

                                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.