Section : Arbres | Graphes (UGA)

Arbres et forets
Arbres enracinés
Arbres couvrants de poids minimum

Sélectionner l’activité Compétences1. Techniques de preuveAvoir compris le...
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é
Sélectionner l’activité Transparents Arbres

Transparents Arbres Fichier
Sélectionner l’activité One idea, one story: Les Hydrocarbones saturés acycliques

One idea, one story: Les Hydrocarbones saturés acycliques Leçon
Sélectionner l’activité Transparents Arbre couvrant de poids min

Transparents Arbre couvrant de poids min Fichier
Sélectionner l’activité One idea, one story: Prim's Network for the capitals of the American states

One idea, one story: Prim's Network for the capitals of the American states Page
Sélectionner l’activité Feuille d'exercice Arbres

Feuille d'exercice Arbres Fichier
Sélectionner l’activité Étiquette
Sélectionner l’activité Test sur les arbres

Test sur les arbres
Sélectionner l’activité Tests on trees and on Kruskal algorithm

Tests on trees and on Kruskal algorithm
Sélectionner l’activité Vidéo (8min): Algorithme de Prim

Vidéo (8min): Algorithme de Prim Page
Sélectionner l’activité Vidéo (10min): Optimalité de l'algorithme de Prim

Vidéo (10min): Optimalité de l'algorithme de Prim Page

Résumé de section

Compétences