Terminale · Mathématiques

Découvrir la modélisation d'un réseau par un graphe et sa matrice d'adjacence

Traduire une situation de réseau en graphe, écrire sa matrice d'adjacence et lire sur cette matrice les liens directs, ainsi que des chaînes ou chemins simples, sans calculer de puissances de matrice.

Aperçu gratuit
Illustration de la fiche « Découvrir la modélisation d'un réseau par un graphe et sa matrice d'adjacence »

Les points essentiels

  • Modéliser un réseau (routes, relations, circuits, messages) consiste à choisir les sommets (objets ou lieux) et les arêtes ou arcs (liens entre eux), puis à ignorer tout ce qui n'est pas pertinent pour la question posée.
  • Un graphe non orienté relie ses sommets par des arêtes sans sens de lecture ; un graphe orienté utilise des arcs, qui ont un sens. Le choix dépend de la situation : une route à double sens est une arête, une rue à sens unique est un arc.

Les mots à connaître

Graphe
Un graphe est un ensemble de sommets et un ensemble de liens (arêtes s'ils n'ont pas de sens, arcs s'ils sont orientés) reliant certains couples de sommets. Il sert de modèle mathématique d'un réseau.
Matrice d'adjacence
Pour un graphe dont les sommets sont numérotés de 1 à n, c'est la matrice carrée A d'ordre n telle que a_ij = 1 s'il existe un lien du sommet i vers le sommet j, et a_ij = 0 sinon. Elle dépend de l'ordre choisi pour les sommets.

Un exemple pour comprendre

Quatre villes A, B, C, D sont reliées par des routes à double sens : A–B, A–C, B–C, C–D. Dessiner mentalement le graphe, écrire sa matrice d'adjacence (ordre A, B, C, D), puis donner le degré de chaque sommet.

Le graphe est non orienté car les routes sont à double sens. Ligne A : A est relié à B et C, donc (0 1 1 0). Ligne B : relié à A et C, donc (1 0 1 0). Ligne C : relié à A, B et D, donc (1 1 0 1). Ligne D : relié seulement à C, donc (0 0 1 0). La matrice est symétrique et sa diagonale est nulle, ce qui est cohérent. Les degrés sont les sommes des lignes : A a le degré 2, B le degré 2, C le degré 3, D le degré 1. Vérification : 2 + 2 + 3 + 1 = 8, soit le double du nombre d'arêtes (4).

Première page de l’Essentiel : Découvrir la modélisation d'un réseau par un graphe et sa matrice d'adjacence
Ketty