Fiche de cours Logimaths
Graphes : le cours expliqué pas à pas
Sommets, arêtes, matrice d'adjacence
💡 Avant de commencer Version expliquée pas à pas. L'idée clé : un graphe modélise des relations : des points reliés par des liens (réseaux, trajets, connexions).
Étape 1 : Points et liens
Un graphe est fait de sommets (des points) reliés par des arêtes (des liens). Exemples : un réseau social, un plan de métro, des routes entre villes.
Étape 2 : Le vocabulaire de base
Définitions Le degré d'un sommet = son nombre d'arêtes. Un chemin est une suite d'arêtes reliant deux sommets. Un graphe est connexe si on peut aller de tout sommet à tout autre.
Étape 3 : La matrice d'adjacence
Traduire en nombres On range les liens dans une matrice : la case (i, j) vaut 1 s'il y a une arête entre les sommets i et j, 0 sinon. On peut alors calculer sur le graphe.
💡 Compter les chemins Les puissances de la matrice d'adjacence donnent le nombre de chemins d'une longueur donnée entre deux sommets.
Étape 4 : À quoi ça sert
Optimiser des trajets, analyser des réseaux, modéliser des connexions : les graphes sont partout en informatique et en logistique.
👆 À toi de jouer Dans un graphe, que représente le degré d'un sommet ?
Voir la réponse
Le nombre d'arêtes qui lui sont reliées.🎯 Mémo
L'essentiel Graphe = sommets + arêtes (relations). Degré, chemin, connexe. Matrice d'adjacence pour calculer (chemins via ses puissances).