Tree
|
 |
Compétences
1. Techniques de preuve- Avoir compris les preuves par double comptage du cours et des exercices
- Appliquer le schéma de preuve par double comptage à des preuves simples sur les arbres
2. Propriétés des arbres- Connaitre les caractérisations d'un arbre
- Démontrer l'équivalence entre les caractérisations d'un arbre
- Démontrer des propriétés sur les arbres (au moins une feuille, au moins deux feuilles, chemin unique entre chaque paire de sommets...)
- Décrire des certificats pour la reconnaissance d'un arbre
3. Arbre couvrant de poids minimum- Enoncer le problème de l'arbre couvrant de poids minimum (MST)
- Décrire un des algorithmes gloutons classiques (Kruskal ou Prim) pour résoudre le problème MST
- Expliquer les principaux ingrédients de la preuve
Vocabulaire : acyclique, arbre, foret, racine, père, fils, feuille, hauteur, profondeur d'un sommet, algorithme glouton, arborescence, graphe pondéré