Graphe (type abstrait)

En informatique, et plus particulièrement en génie logiciel, le type abstrait graphe est la spécification formelle^[1] des données qui définissent l'objet mathématique graphe^[2] et de l'ensemble des opérations qu'on peut effectuer sur elles. On qualifie d'« abstrait » ce type de données car il correspond à un cahier des charges qu'une structure de données concrète doit ensuite implémenter.

Description

La structure de données abstraite de graphes consiste en un ensemble fini, éventuellement mutable de sommets ou nœuds ou points, avec un ensemble de paires ordonnées ou non de tels éléments Ces paires sont des arêtes, arcs non orientés, ou lignes pour un graphe non orienté, et flèches, arêtes orientées , arcs, ou lignes orientées dans le cas orienté. Les sommets peuvent faire partie de la structure, ou être des entités extérieures, représentées par des entiers ou des références.

Une structure de graphe peut aussi associer, à chaque arête, une « valeur », telle qu'une étiquette ou une valeur numérique (un coût, une capacité, une longueur, etc.). Plus généralement, un graphe peut aussi être donnée par deux ensembles d'objets, un de sommets et un ensemble d'arêtes, muni de deux applications qui, à chaque arête, associent son sommet de départ et son sommet d'arrivée. Cette vision^[3] permet d'associer des valeurs à chaque objet (sommet ou arête).

Opérations

Les opérations de base fournies par une structure de données de graphe G incluent usuellement^[4]^,^[3] :

sont_adjacents(G, x, y): teste s'il y a une arête de x à y;
voisins(G, x): liste les sommets qui sont adjacents à x;
ajouter_sommet(G, x): ajoute le sommet x s'il n'y figure pas déjà;
supprimer_sommet(G, x): supprime le sommet x s'il existe;
ajouter_arête(G, x, y): ajoute l'arête de x à y s'il n'y figure pas déjà;
supprimer_arête(G, x, y): supprime l’arête de x à y si elle existe;
retourner_valeur_sommet(G, x): retourne la valeur associée à x;
fixer_valeur_sommet(G, x, v): fixe la valeur de x à v.

Les structures qui associent des valeurs aux arêtes disposent en général^[4] des opérations suivantes :

retourner_valeur_arête(G, x, y): retourne la valeur de l'arête (x, y);
fixer_valeur_arête(G, x, y, v): fixe à v la valeur de l’arête (x, y).

Représentations

Diverses structures de données sont utilisées en pratique pour la représentation de graphes :

Liste d'adjacence^[5]^,^[6]: Les sommets sont représentés comme des objets ou enregistrements, et à chaque sommet est associée une liste de sommets adjacents. Cette structure permet de conserver des données additionnelles pour les sommets. Les informations additionnelles concernant les arêtes peuvent être stockés dans les objets si les arêtes sont représentées par des objets. Dans ce cas, chaque sommet peut contenir les arêtes adjacentes et chaque arête ses sommets incidents.
Matrice d'adjacence^[7]^,^[8]: C'est une matrice carrée de taille $|V|\times |V|$ , où les lignes représentent les sommets de départ et les colonnes les sommets d'arrivée. Une entrée peut désigner la présence d'un arc, ou peut porter une valeur d'arc. Dans le cas des graphes non orientés, la matrice est symétrique.
Matrice d'incidence^[9]: C'est une matrice de taille $|V|\times |E|$ , où les lignes représentent les sommets et les colonnes les arêtes. Une entrée $b_{x,a}$ indique si l'arête $a$ est incidente au sommet $x$ . Plus précisément : $b_{x,a}={\begin{cases}-1,&{\text{si }}a{\text{ sort de }}x\\1,&{\text{si }}a{\text{ entre dans }}x\\0&{\text{sinon}}.\end{cases}}$ Il n'y a que deux valeurs non nulles par colonne (et une seule dans le cas d'une boucle).

La table suivante donne la complexité en temps des diverses opérations sur les graphes selon les représentations. Ici $|V|$ est le nombre de sommets et $|E|$ le nombre d'arêtes.

	Liste d'ajacence	Matrice d'adjacence	Matrice d'incidence
Créer le graphe	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
Ajouter un sommet	$O(1)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
Ajouter une arête	$O(1)$	$O(1)$	$O(\|V\|\cdot \|E\|)$
Supprimer un sommet	$O(\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
Supprimer une arête	$O(\|V\|)$	$O(1)$	$O(\|V\|\cdot \|E\|)$
Test d'adjacence entre deux sommets	$O(\|V\|)$	$O(1)$	$O(\|E\|)$
Remarques	Lent dans la suppression parce qu'il faut trouver les sommets ou arêtes	Lent dans l'adjonction ou suppression de sommets parce que la matrice doit être reformatée	Lent dans l'adjonction ou suppression de sommets ou d'arêtes parce que la matrice doit être reformatée

Les listes d'adjacence sont en général préférables pour des graphes peu denses. Une matrice d'adjacence est au contraire préférable quand le graphe est dense, c'est-à-dire quand le nombre d'arêtes |E | est proche du carré du nombre de sommets |V |², mais aussi lorsque l'on veut savoir rapidement tester l'existence d'une arête entre deux sommets^[10]^,^[11]^,^[3].

Articles liés

Notes et références

↑ Manfred Broy, Martin Wirsing et Claude Pair, « A Systematic Study of Models of Abstract Data Types », Theoretical Computer Science, vol. 33,‎ 1984, p. 139-174
↑ Sébastien Veigneau, Approches impérative et fonctionnelle de l'algorithmique : applications en C et en CAML Light, Springer Science & Business Media, 1999 (lire en ligne)
↑ ^{a b et c} Kurt Mehlhorn et Stefan Näher, LEDA : A platform for combinatorial and geometric computing, Cambridge University Press, 1999, « Chapter 6: Graphs and their data structures », p. 240–282.
↑ ^{a et b} Goodrich et Tamassia 2015, Section 13.1.2: Operations on graphs, p. 360
↑ Cormen et al. 2002, p. 514-515.
↑ Goodrich et Tamassia 2015, p. 361-362.
↑ Cormen et al. 2002, p. 515-516.
↑ Goodrich et Tamassia 2015, p. 363.
↑ Cormen et al. 2002, Exercise 22.1-7, p. 517.
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Algorithmique, Paris, Dunod, 2002, xxix+1188 (ISBN 978-2-10-003922-7, SUDOC 068254024), « Section 22.1: Représentation de graphes », p. 514–517.
↑ Michael T. Goodrich et Roberto Tamassia, Algorithm Design and Applications, Wiley, 2015, « Section 13.1: Graph terminology and representations », p. 355–364.