Section : Arbres | Théorie des Graphes

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

Sélectionner l’activité Skills 1. Proof technics Under...
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

Les étudiants doivent

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

One idea, one story: Les Hydrocarbones saturés acycliques Leçon

Les étudiants doivent

Consulter

Effectuer l’activité jusqu’à la fin
Sélectionner l’activité Transparents Arbre couvrant de poids min

Transparents Arbre couvrant de poids min Fichier

Les étudiants doivent

Consulter
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

Les étudiants doivent

Consulter
Sélectionner l’activité Feuille d'exercice Arbres

Feuille d'exercice Arbres Fichier

Les étudiants doivent

Consulter
Sélectionner l’activité Étiquette
Sélectionner l’activité Test sur les arbres

Test sur les arbres

Les étudiants doivent

Consulter

Recevoir une note

Obtenir une note minimale de réussite
Sélectionner l’activité Tests on trees and on Kruskal algorithm

Tests on trees and on Kruskal algorithm

Les étudiants doivent

Consulter

Recevoir une note

Obtenir une note minimale de réussite
Sélectionner l’activité Algorithmes de Kruskal et Union Find - Java

Algorithmes de Kruskal et Union Find - Java Virtual programming lab

Les étudiants doivent

Recevoir une note
Sélectionner l’activité Javadoc de GraphePondere.java

Javadoc de GraphePondere.java Fichier

Les étudiants doivent

Consulter
Sélectionner l’activité Javadoc de Arete.java

Javadoc de Arete.java Fichier

Les étudiants doivent

Consulter
Sélectionner l’activité Implementation of the Union-Find Class and of Kruskal Algorithm - Java (the same in English)

Implementation of the Union-Find Class and of Kruskal Algorithm - Java (the same in English) Virtual programming lab

Les étudiants doivent

Marquer comme terminé
Sélectionner l’activité Arbre Couvrant de poids min - Python

Arbre Couvrant de poids min - Python Virtual programming lab

Les étudiants doivent

Recevoir une note
Sélectionner l’activité Vidéo (10min): Optimalité de l'algorithme de Prim

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

Vidéo (8min): Algorithme de Prim Page
Sélectionner l’activité Kruskal in English 09 22

Kruskal in English 09 22 Virtual programming lab

Les étudiants doivent

Marquer comme terminé

Résumé de section

Compétences