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.

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).

