Section: Tree | Théorie des Graphes

Trees and Forests
Rooted trees
Minimum spanning trees

Select activity Skills 1. Proof technics Under...
Skills
1. Proof technics

Understand double counting proofs in the course or in the exercises

Apply double counting proof technics to simple proofs on trees

2. Tree properties

Know the trees characterizations

Prove the equivalence between the tree characterizations

Prove properties on trees (at least one leaf, at least two leaves, single path between each pair of vertices...)

Describe certificates for tree recognition

3. Minimum spanning tree

Formulate the minimum spanning tree (MST) problem

Describe on of the classical greedy algorithms (Kruskal or Prim) to solve the MST problem

Explain the main components of the proof

Vocabulary : acyclic, tree, forest, root, parent, children, leaf, hight, depth of a vertex, greedy algorithm, arborescence, weighed graph
Select activity Transparents Arbres

Transparents Arbres File

Students must

View
Select activity One idea, one story: Les Hydrocarbones saturés acycliques

One idea, one story: Les Hydrocarbones saturés acycliques Lesson

Students must

View

Go through the activity to the end
Select activity Transparents Arbre couvrant de poids min

Transparents Arbre couvrant de poids min File

Students must

View
Select activity 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

Students must

View
Select activity Feuille d'exercice Arbres

Feuille d'exercice Arbres File

Students must

View
Select activity Étiquette
Select activity Test sur les arbres

Test sur les arbres Quiz

Students must

View

Receive a grade

Receive a passing grade
Select activity Tests on trees and on Kruskal algorithm

Tests on trees and on Kruskal algorithm Quiz

Students must

View

Receive a grade

Receive a passing grade
Select activity Algorithmes de Kruskal et Union Find - Java

Algorithmes de Kruskal et Union Find - Java Virtual programming lab

Students must

Receive a grade
Select activity Javadoc de GraphePondere.java

Javadoc de GraphePondere.java File

Students must

View
Select activity Javadoc de Arete.java

Javadoc de Arete.java File

Students must

View
Select activity 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

Students must

Mark as done
Select activity Arbre Couvrant de poids min - Python

Arbre Couvrant de poids min - Python Virtual programming lab

Students must

Receive a grade
Select activity Vidéo (10min): Optimalité de l'algorithme de Prim

Vidéo (10min): Optimalité de l'algorithme de Prim Page
Select activity Vidéo (8min): Algorithme de Prim

Vidéo (8min): Algorithme de Prim Page
Select activity Kruskal in English 09 22

Kruskal in English 09 22 Virtual programming lab

Students must

Mark as done

Section outline

Skills