1 - graphe

graphe
Un graphe est « un ensemble non vide mais fini de sommets (ou neuds) combinés à un ensemble d’arêtes qui joignent des paires de sommets distincts » [1].

Note

Les sommets et arêtes sont des objets abstraits.

Note

Un graphe est donc constitué d’au moins un sommet et zéro arête.

Exemple en langage dot

Note

le langage dot est un langage de description de graphes. En savoir plus Il ne vous est pas demandé d’apprendre ce langage.

Le code suivant donne la représentation qui le suit, ou a, b, c, d, e sont des sommets reliés par des arêtes.

code

graph mon_graphe {
   a -- b -- c;
   b -- d;
}

(voir en ligne)

représentation graphique

Note

Les sommets sont ici représentés par des ellipses. Ils pourraient être représentés par des points, des carrés, etc.

../../../_images/DotLanguageUndirected.svg

Autre exemple

graph mon_graphe {
      a -- b;
      c -- d;
      c -- e;
   }

(Voir en ligne)

../../../_images/1-graphe-exemple-2.svg

Notes

[1]« A nonempty but finite set of vertices (or nodes) together with a set of edges that join pairs of distinct vertices. » Martin, L. (Trans.). (2016). Graph. In A. Butterfield, G. Ekembe Ngondi, & A. Kerr (Eds.), A Dictionary of Computer Science (7th ed.). Oxford University Press. https://doi.org/10.1093/acref/9780199688975.001.0001