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 Archivo
      Actualizado 26/01/2026 17:52
    • CM 5 : arbres couvrants de poids minimum Archivo
      Actualizado 26/01/2026 13:55
    • Redaction-type algo. de Kruskal Archivo
    • Test sur les arbres Cuestionario
      Los estudiantes deben
      Recibir una calificación
      Recibir una calificación de aprobado
    • Test Minimum Spanning Tree Cuestionario
      Los estudiantes deben
      Recibir una calificación
      Recibir una calificación de aprobado
    • One idea, one story: Les Hydrocarbones saturés acycliques Lección
      Los estudiantes deben
      Completa la actividad hasta el final
    • One idea, one story: Prim's Network for the capitals of the American states Página
    • Vidéo (8min): Algorithme de Prim Página
    • Vidéo (10min): Optimalité de l'algorithme de Prim Página