Graphe (type abstrait)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un graphe orienté, dont les arcs et certains sommets sont « valués » par des couleurs.

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[modifier | modifier le code]

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[modifier | modifier le code]

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_sommer(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 suivante :

  • 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[modifier | modifier le code]

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 , 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 un matrices , où les lignes représentent les sommets et les colonnes les arêtes. Une entrée indique si l'arête est incidente au sommet . Plus précisément : 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 est le nombre de sommets et le nombre d'arêtes.

Liste d'ajacence Matrice d'adjacence Matrice d'incidence
Créer le graphe
Ajouter un sommet
Ajouter une arête
Supprimer un sommet
Supprimer une arête
Test d'adjacence entre deux sommets
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 |2, mais aussi lorsque l'on veut savoir rapidement tester l'existence d'une arête entre deux sommets[10],[11],[3].

Articles liés[modifier | modifier le code]

Notes et références[modifier | modifier le code]

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

Liens externes[modifier | modifier le code]