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 Файл
      Изменено 26/01/26, 17:52
    • CM 5 : arbres couvrants de poids minimum Файл
      Изменено 26/01/26, 13:55
    • Redaction-type algo. de Kruskal Файл
    • Test sur les arbres Тест
      Студенты должны
      Получить оценку
      Получить проходной балл
    • Test Minimum Spanning Tree Тест
      Студенты должны
      Получить оценку
      Получить проходной балл
    • One idea, one story: Les Hydrocarbones saturés acycliques Лекция
      Студенты должны
      Пройти лекцию до конца
    • One idea, one story: Prim's Network for the capitals of the American states Страница
    • Vidéo (8min): Algorithme de Prim Страница
    • Vidéo (10min): Optimalité de l'algorithme de Prim Страница