1. Arbres et forets 
    2. Arbres enracinés
    3. Arbres couvrants de poids minimum
    		 How a graph theorist draws a "star"

    • 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é
    • CM 4 : arbres Fichier
      Modifié 26 janv. 26, 17:52
    • CM 5 : arbres couvrants de poids minimum Fichier
      Modifié 26 janv. 26, 13:55
    • Redaction-type algo. de Kruskal Fichier
    • Test sur les arbres
      Les étudiants doivent
      Recevoir une note
      Obtenir une note minimale de réussite
    • Test Minimum Spanning Tree
      Les étudiants doivent
      Recevoir une note
      Obtenir une note minimale de réussite
    • One idea, one story: Les Hydrocarbones saturés acycliques Leçon
      Les étudiants doivent
      Effectuer l’activité jusqu’à la fin
    • One idea, one story: Prim's Network for the capitals of the American states Page
    • Vidéo (8min): Algorithme de Prim Page
    • Vidéo (10min): Optimalité de l'algorithme de Prim Page