C12.1 : Les graphes
Activité de présentation : Qui parle à qui ?
Voir explications du professeur
Vocabulaire
Sommets (nœuds) et arêtes (arcs)
Un graphe est une structure de donnée relationnelle.
Un graphe est un ensemble de sommets (nœuds) reliés entre eux par des arêtes (arcs).
Les sommets comme les arêtes peuvent être associées à des données.
On appelle taille du graphe le nombre de sommets (nœuds) de ce graphe.
Graphe orienté ou non orienté
Lorsque le sens des liaisons entre les nœuds est pris en compte, on parle de graphe orienté.
Lorsque le sens des liens entre les nœuds n'est pas pris en compte, on parle de graphe non orienté.
Remarque : on utilise plutôt le terme arc pour les graphes orientés, et le terme arête pour les graphes non orientés.
Chemin
Un chemin entre deux nœuds est une séquence finie de nœuds et/ou d'arcs (arêtes) permettant de les relier.
La longueur d'un chemin est le nombre d'arcs (arêtes) de ce chemin.
Voisinage
Deux nœuds sont dits adjacents ou voisins s'ils sont reliés par un arc (arête).
Dans le cas d'un graphe orienté, on distingue les successeurs et les prédécesseurs.
Applications pour bien comprendre (sur papier)
Application 1
1) Lister tous les chemins permettant d'aller de 1 à 5.
2) Donner le nombre de voisins de chaque nœud.
Application 2
Pour chacun des deux graphes, répondre aux questions suivantes :
- 1) Lister les chemins permettant d'aller de "a" à "d".
- 2) Lister les chemins permettant d'aller de "d" à "a".
- 3) Donner le nombre de voisins de chaque nœuds.
Un langage pour représenter les graphes : le DOT
Le site viz-js.com permet de rentrer des données au format DOT et de visualiser ces données sous forme graphique.
La page suivante donne quelques exemples de codes : lien.
A faire : En vous appuyant sur ces exemples, reproduire les graphes n° 1, n° 2 et n° 3.
Exemples d'utilisation
Utilisation des graphes pour la cartographie (sur papier)
On s'intéresse ici aux applications de cartographie.
Question : Quel graphe peut permettre de stocker les informations utilisées par les logiciels de cartographie pour déterminer la meilleure route à suivre pour aller d'un endroit à un autre ?
Labyrinthes (sur papier)
Exemple 1
On considère le labyrinthe suivant :
A faire : Associer ce labyrinthe à un graphe. On expliquera la démarche adoptée.
Exemple 2
A faire : Même question avec le labyrinthe suivant :
