Le plan du métro
Regarde un plan de métro. Des points, ce sont les stations. Des traits, ce sont les lignes qui les relient.
On peut aller d’une station à une autre en suivant les traits. Il y a souvent plusieurs routes.
Ce dessin est un graphe. Les réseaux d’amis et les routes en sont aussi.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Graphe | Des points reliés par des traits. | Un plan de métro |
| Sommet | Un point du graphe. | La station Gare |
| Arête | Un trait qui relie deux sommets. | Gare et Mairie |
| Voisin | Un sommet relié directement à un autre. | Mairie est voisine de Gare |
| Degré | Le nombre de voisins d’un sommet. | Mairie a un degré de 3 |
| Chemin | Une suite de sommets où chacun est voisin du suivant. | Gare, Mairie, Lycee |
| Liste d’adjacence | Un dictionnaire qui donne, pour chaque sommet, la liste de ses voisins. | "Gare": ["Mairie", "Stade"] |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : lis le plan
À toi de jouer
À toi : lis le plan
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Un graphe n’est pas un arbre
Un arbre a une racine et des niveaux. Un graphe n’a ni racine ni niveau.
Dans un graphe, on peut revenir au point de départ en suivant les traits. On peut aussi arriver par plusieurs routes.
Les arbres sont des graphes très rangés. Les graphes sont plus libres.
Exemple travaillé : les voisines de chaque station
| Station | Voisines | Degré |
|---|---|---|
| Gare | Mairie, Stade | 2 |
| Mairie | Gare, Lycee, Stade | 3 |
| Lycee | Mairie, Marche | 2 |
| Stade | Mairie, Marche, Gare | 3 |
| Marche | Lycee, Stade, Parc | 3 |
| Parc | Marche | 1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : le métro en Python
# Chaque station donne la liste de ses stations voisines.
metro = {
"Gare": ["Mairie", "Stade"],
"Mairie": ["Gare", "Lycee", "Stade"],
"Lycee": ["Mairie", "Marche"],
"Stade": ["Mairie", "Marche", "Gare"],
"Marche": ["Lycee", "Stade", "Parc"],
"Parc": ["Marche"],
}
print("Voisines de Mairie :", metro["Mairie"])
print("Mairie a", len(metro["Mairie"]), "voisines")
for station in metro:
print(station, ": degré", len(metro[station]))
# Quelle station a le plus petit degré ? Laquelle a le plus grand ?
À toi : voisins et degrés
À toi de jouer
À toi : voisins et degrés
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.