Aller au contenu principal

3.1 – Les caractéristiques des Graphes

Si on souhaite résumer les graphes en une définition, on pourrait dire qu'ils sont une représentation graphique d'éléments en relation. Je sais, c'est très vague comme définition, mais cela montre bien ce que peuvent représenter les graphes, à peu près n'importe quoi.

3.1.1 – L'anatomie d'un graphe​

Comme montré dans la section 3.0, les graphes sont une série de points reliés entre eux par des lignes droites ou courbes. Mais ces points et ces lignes peuvent être interprétés, et pour le faire, il nous faut les bons termes.

Les deux composantes principales d'un graphe sont les sommets et les arêtes.

Graphe annoté identifiant les sommets et les arêtes

Habituellement, on attribue des lettres aux sommets mais on peut aussi leur attribuer des mots lorsque la situation s'y prête. Les arêtes sont habituellement nommées en fonction des sommets qu'elles relient.

Graphe avec les sommets A, B, C reliés par les arêtes a-b et b-c

3.1.2 – Caractéristiques des graphes​

Pour caractériser un graphe, on utilisera les critères suivants :

  • Ordre d'un graphe – correspond au nombre de sommets qui forment le graphe
  • Degré d'un sommet - correspond au nombre d'arêtes qui sont liées à un sommet
  • Sommets adjacents – correspond à deux sommets liés par une arête
  • Arêtes parallèles – correspond à deux arêtes qui relient les mêmes sommets
  • Boucles – correspond à une arête qui quitte et qui revient à un même sommet

Analysons le graphe suivant selon les critères identifiés :

Graphe à 4 sommets A, B, C, D avec deux arêtes parallèles entre A et B et une boucle au sommet D
  • Ordre d'un graphe : Le graphe est d'ordre 4 puisqu'il possède 4 sommets
  • Degré d'un sommet : Les sommets sont de degrés suivants - A(3), B(2), C(2) et D(3)
  • Sommets adjacents : Les sommets AB, AC et CD sont adjacents
  • Arêtes parallèles : Les arêtes a-b (1) et a-b (2) sont parallèles
  • Boucles : Le sommet D dispose d'une boucle, c'est d'ailleurs pourquoi il est de degré 3 (puisqu'il y a trois «chemins» pour y parvenir)

On peut ensuite utiliser deux distinctions pour caractériser davantage un graphe

  • Connexe ou non : Si tous les sommets d'un graphe sont liés ensemble, il s'agit d'un graphe connexe
  • Complet ou non : Si tous les sommets sont reliés directement à tous les autres sommets, il s'agit d'un graphe complet
Comparaison d'un graphe connexe et d'un graphe non connexe avec les sommets Arthur, Bianca, César et Dominique
Comparaison d'un graphe non complet et d'un graphe complet avec les sommets Arthur, Bianca, César et Dominique

Les exercices liés à cette section se trouvent dans le manuel Vision Vol. 2 : p. 16 # 1, 2, 3c, 4, 5, 6, 7, 8a, 9, 12, 13, 14, 16, 19, 20