Composantes connexes et tri topologique
Deux applications des parcours : étiqueter les composantes connexes d'un graphe non orienté, et ordonner les sommets d'un graphe orienté sans circuit (Kahn par degrés entrants, ou ordre de fin inverse d'un parcours en profondeur) ; un circuit rend le tri impossible.
- 28 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Composante connexe : de quoi s'agit-il ?
Voir la réponse
Ensemble maximal de sommets d'un graphe non orienté, tous reliés deux à deux par des chaînes.
Un parcours depuis un sommet découvre exactement sa composante. Un graphe est connexe quand il n'en a qu'une.
Sept modules : A et B sans prérequis ; C exige A ; D exige A et B ; E exige C et D ; F exige B ; G exige E et F. Quel ordre est un tri topologique ?
- A B D C F E G
- A C D E B F G
- F B A D C E G
- A B C E D F G
Voir la réponse
A B D C F E G
Dans la bonne réponse, chaque module vient après ses prérequis. Dans A C D E B F G, D passe avant B ; dans F B A D C E G, F passe avant B ; dans A B C E D F G, E passe avant D.
Pour étiqueter les composantes connexes, on lance un parcours depuis chaque sommet … : chaque lancement découvre … entière.
Voir la réponse
Pour étiqueter les composantes connexes, on lance un parcours depuis chaque sommet non encore visité : chaque lancement découvre une composante entière.
Le nombre de lancements est le nombre de composantes. Le parcours peut être en largeur ou en profondeur, le résultat est le même.
Graphe orienté sans circuit : de quoi s'agit-il ?
Voir la réponse
Graphe orienté dans lequel aucun chemin ne revient à son point de départ.
C'est la forme naturelle des dépendances (prérequis, tâches, fichiers à compiler). On le note DAG en anglais.