Graphe : structure relationnelle de données
Objectifs d’apprentissage
Connaissances à acquérir et compétences à développer et/ou à mobiliser (acquis antérieurs)
Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés.
Modéliser des situations sous forme de graphes.
Langage de programmation Python : compétences requises, à acquérir, à mobiliser, à développer, à maîtriser.
Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs.
Passer d’une représentation à une autre.
Des exemples de structures de données en graphes – Terminologie, définition et caractéristiques d’un graphe.
Tout comme pour les arbres, dans certaines situations une structure linéaire ne permet pas de décrire les données qui les caractérisent.
On cherche à identifier des exemples de situations représentables par un graphe.
Ensuite on définit les caractéristiques d’un graphe.
Situation n°1
Situation n°2
Situation n°3
Ce qu’il faut retenir (1)
Exemples et Définitions
Qu’il s’agisse d’un réseau social, d’un réseau routier ou encore d’un réseau informatique, autant d’exemples qui peuvent être considérés comme des graphes.
Un graphe est une structure relationnelle, c’est à dire un ensemble de relations entre des sommets.
Un graphe est constitué de sommets et d’arêtes. Une arête ou un arc relie deux sommets adjacents.
Le degré d’une sommet est le nombre d’arêtes liés à ce sommet.
L’ordre d’un graphe est le nombre de sommets.
Exercice n°1
Un réseau social, un réseau routier, un réseau informatique peuvent être décrits par des graphes.
Pour chacune de ces situations, indiquez à quoi correspondent les sommets et les arêtes de ces graphes.
<< Cliquez pour plus d’informations <<