Курс: Graphes (UGA), Тема: Tree

Представяне по теми

Главна

Tree
Arbres et forets
Arbres enracinés
Arbres couvrants de poids minimum
- 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é
- Transparents Arbres Файл
  
  Преглеждане
- One idea, one story: Les Hydrocarbones saturés acycliques Урок
  
  Преглеждане Go through the activity to the end
- Transparents Arbre couvrant de poids min Файл
  
  Преглеждане
- One idea, one story: Prim's Network for the capitals of the American states Страница
  
  Преглеждане
- Feuille d'exercice Arbres Файл
  
  Преглеждане
- Test sur les arbres Тест
  
  Преглеждане Получаване на оценка Получаване на оценка за преминаване
- Tests on trees and on Kruskal algorithm Тест
  
  Преглеждане Получаване на оценка Получаване на оценка за преминаване
- Vidéo (8min): Algorithme de Prim Страница
- Vidéo (10min): Optimalité de l'algorithme de Prim Страница

Представяне по теми

Главна

Tree

Compétences