Informatique · Terminale · 2 min de lecture
Sommets, arêtes et parcours dans un graphe
Structure relationnelle : sommets, arêtes (graphe non orienté) ou arcs (graphe orienté), voisins, degré, chemin ; modéliser une situation (réseau routier, réseau électrique, Internet, réseau social) par un graphe ; représenter un graphe par une matrice d'adjacence ou par des listes de successeurs (ou de prédécesseurs), passer d'une représentation à l'autre et choisir selon le traitement.
Chapitre du programme : Numérique et sciences informatiques (spécialité)
Bloc 1 sur 7 · Comprendre
Comprendre
Un graphe représente des objets par des sommets et des relations par des arêtes. Un graphe non orienté décrit une relation symétrique ; un graphe orienté distingue le départ et l'arrivée d'un arc. Les poids peuvent représenter des coûts ou des distances, mais leur sens doit être annoncé.
Bloc 2 sur 7 · Approfondir
Approfondir
Dans un graphe simple non orienté, le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. Un chemin relie des sommets par des arêtes successives. Dans un graphe non pondéré, un plus court chemin minimise le nombre d'arêtes, pas une distance géographique supposée.
Bloc 3 sur 7 · Exemple
Exemple travaillé
Considérez les arêtes AB,AC,BC et CD entre quatre sommets. Les degrés sont2 pour A,2 pour B,3 pour C et1 pour D. Leur somme vaut8, soit deux fois les quatre arêtes. De A à D, le chemin A,C,D utilise deux arêtes et il n'existe pas d'arête AD : la distance est donc2.
Bloc 4 sur 7 · Visualiser
Visualiser le raisonnement
Écrivez pour chaque sommet la liste de ses voisins : A:{B,C}, B:{A,C}, C:{A,B,D}, D:{C}. Chaque arête apparaît dans deux listes. On peut retrouver le degré en comptant chaque liste et suivre un chemin directement sur cette représentation.
Continuez sur votre lancée
Vous avez découvert l’essentiel et un exemple. Retrouvez la suite du cours et les points à retenir, puis passez à l’entraînement guidé dans votre compte.
- Les formules et les repères à retenir
- Les erreurs fréquentes expliquées
- Un exercice avec des aides et sa correction
L’accès gratuit comprend les cours et exercices de votre niveau choisi.
Sources
- https://docs.python.org/3/tutorial/
- MIT, Mathematics for Computer Science : https://courses.csail.mit.edu/6.042/spring18/mcs.pdf
- Princeton, undirected graphs : https://algs4.cs.princeton.edu/41graph/
Vous pensez avoir trouvé une erreur dans cette leçon ? Signalez-la par e-mail.