2 – sommet

sommet

Un sommet, aussi appelé nœud, est une abstraction indivisible [1].
Un sommet peut être lié, par une ou plusieurs arêtes, à un ou plusieurs sommets (deux sommets peuvent être liés entre eux par plusieurs arêtes). Un sommet peut aussi n’être relié à aucun sommet (il est dit isolé) ou à lui-même (on parle de boucle)

exemple

code

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

(voir en ligne)

Note

Ici le sommet e n’est lié à aucun autre, il est dit isolé. Le sommet a est lié à lui-même par une arête : on parle de boucle. Les sommets b et d sont liés par deux arêtes.

représentation graphique

---

notion de label

label

Un sommet peut recevoir un label : un terme ou ensemble de terme désignant le concept représenté par le sommet.

exemples

graphe sans label

Dans les exemples précédents, les sommets ont des labels (a, b, c, d, e), voyons un exemple ou nous indiquons explicitement l’absence de label.

code

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

   a [label=""];
   b [label=""];
   c [label=""];
   d [label=""];
}

(voir en ligne)

représentation visuelle

graphe avec labels

code

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

   a [label="élément a"];
   b [label="élément b"];
   c [label="élément c"];
   d [label="élément d"];
}

(voir en ligne)

représentation visuelle

---

Notes

[1]

Ou plus précisemment « une sous-structure d’une structure de données hiérarchique qui ne peux pas être subdivisée, e.g. un sommet dans un graphe ou arbre. », « A substructure of a hierarchical data structure that cannot be further decomposed, e.g. a vertex in a graph or tree. » Martin, L. (Trans.). (2016). Edge. 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