Cheminements
|  |
Compétences
1. Techniques de preuve- Connaître les trois étapes d'une preuve algorithmique (exécution, terminaison, validité du résultat)
- Avoir compris les preuves algorithmiques du cours
- Appliquer le schéma de preuve algorithmique sur des problèmes simples
- Avoir compris les preuves par contre exemple minimal/maximal du cours
- Avoir compris les certificats du cours (accessibilité, distance)
2. Propriétés- Montrer que l'existence d'un chemin entre deux sommets est une relation d'équivalence
- Connaitre la propriété sur le nombre minimal d'arêtes d'un graphe connexe
- Connaître et démontrer le théorème de Euler (caractérisation des graphes eulériens)
3. Parcours- Décrire / Reconnaitre un parcours en profondeur ou en largeur d'un graphe
- Ecrire l'algorithme pour faire un parcours en largeur et en profondeur d'un graphe
Vocabulaire : chaîne, extrémités, simple, élémentaire, longueur, graphe connexe, composante connexe, co-cycle, parcours en largeur, BFS, parcours en profondeur, DFS, st-coupe, cycle, cycle eulérien, chaîne eulérienne, graphe eulérien, cycle hamiltonien, graphe hamiltonien