Aller au contenu principal

3.3 – Arbres, Graphes orientés et Graphes valués

Notre exploration des graphes tire à sa fin! Nous verrons dans cette dernière section de «vocabulaire» nos derniers types de graphes et les dernières particularités de ces modèles.

3.3.1 – Arbres​

C'est bien simple : Un arbre est un graphe qui ne peut pas supporter un cycle simple. C'est donc un graphe où il est impossible d'avoir une chaîne qui revient à son point de départ sans revenir sur ses pas, emprunter les mêmes arêtes ou repasser par les mêmes sommets.

Comparaison entre un arbre (sans cycle possible) et un graphe ordinaire (avec plusieurs cycles possibles)

Dans le graphe de gauche, il est impossible de faire un cycle, si simple soit-il, sans revenir sur ses pas. Dans le graphe de droite, il existe une multitude de cycles possibles. Ex : 1-2-12-1, 2-3-12-2, 4-5-6-4, etc.

3.3.2 – Graphes orientés​

Un graphe orienté est un graphe où toutes les arêtes se voient attribuer un sens de déplacement. Une arête qui dispose d'une orientation est appelée arc. Les graphes orientés ont les particularités suivantes :

  • Une série d'arcs est appelé un chemin (un peu comme une série d'arêtes est appelé une chaîne)
  • Un chemin qui revient à son point de départ est appelé un circuit (un peu comme une chaîne qui revient à son point de départ est appelé un cycle)
  • Comme pour les cycles et les chaînes, un chemin ou un circuit dans lequel aucun arc n'est répété est dit simple (chemin simple ou circuit simple)

Dans ce graphe :

Graphe orienté à 5 sommets A, B, C, D, E avec des arcs (arêtes orientées) et une boucle au sommet D

A-B, C-E, D-A, etc. sont des arcs A-B-C-E est un chemin A-B-E-A est un circuit

3.3.3 – Les graphes valués​

Un graphe valué est un graphe sur lequel les arêtes portent des valeurs numériques. À la manière d'une carte dans un parc ou d'un réseau routier, ces valeurs peuvent représenter des distances. Elle pourrait aussi représenter des prix, du temps, ou bien d'autres facteurs.

Carte routière du sud du Québec à côté de sa représentation en graphe valué reliant Ottawa, Montréal, Drummondville, Sherbrooke et Québec

L'élément important à retenir pour les graphes valués est que la valeur d'une chaîne, d'un chemin, d'un cycle ou d'un circuit correspond à la somme des valeurs des arêtes empruntées pour compléter ce parcours. Par exemple, pour compléter le chemin O-H-M-S, on calcule 105 km + 90 km + 150 km pour un total de 345 km

Graphe valué reliant les sommets O, H, M, D, S et Q avec les distances en kilomètres inscrites sur chaque arête

Les exercices liés à cette section se trouvent dans le manuel Vision Vol. 2 : p. 37 #1, 2, 3, 5, 6, 8, 10, 12, 13, 15, 17, 19 et 20