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 File
      Modificato il 26/01/2026 17:52
    • CM 5 : arbres couvrants de poids minimum File
      Modificato il 26/01/2026 13:55
    • Redaction-type algo. de Kruskal File
    • Test sur les arbres Quiz
      Gli studenti devono
      Ricevere una valutazione
      Ottenere la sufficienza
    • Test Minimum Spanning Tree Quiz
      Gli studenti devono
      Ricevere una valutazione
      Ottenere la sufficienza
    • One idea, one story: Les Hydrocarbones saturés acycliques Lezione
      Gli studenti devono
      Raggiungere la fine dell'attività
    • One idea, one story: Prim's Network for the capitals of the American states Pagina
    • Vidéo (8min): Algorithme de Prim Pagina
    • Vidéo (10min): Optimalité de l'algorithme de Prim Pagina