Théorie des Graphes, Sezione: Tree

Trees and Forests
Rooted trees
Minimum spanning trees

Seleziona attività 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
Seleziona attività Transparents Arbres

Transparents Arbres File

Gli studenti devono

Visualizzare
Seleziona attività One idea, one story: Les Hydrocarbones saturés acycliques

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

Gli studenti devono

Visualizzare

Raggiungere la fine dell'attività
Seleziona attività Transparents Arbre couvrant de poids min

Transparents Arbre couvrant de poids min File

Gli studenti devono

Visualizzare
Seleziona attività 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 Pagina

Gli studenti devono

Visualizzare
Seleziona attività Feuille d'exercice Arbres

Feuille d'exercice Arbres File

Gli studenti devono

Visualizzare
Seleziona attività Étiquette
Seleziona attività Test sur les arbres

Test sur les arbres Quiz

Gli studenti devono

Visualizzare

Ricevere una valutazione

Ottenere la sufficienza
Seleziona attività Tests on trees and on Kruskal algorithm

Tests on trees and on Kruskal algorithm Quiz

Gli studenti devono

Visualizzare

Ricevere una valutazione

Ottenere la sufficienza
Seleziona attività Algorithmes de Kruskal et Union Find - Java

Algorithmes de Kruskal et Union Find - Java Virtual programming lab

Gli studenti devono

Ricevere una valutazione
Seleziona attività Javadoc de GraphePondere.java

Javadoc de GraphePondere.java File

Gli studenti devono

Visualizzare
Seleziona attività Javadoc de Arete.java

Javadoc de Arete.java File

Gli studenti devono

Visualizzare
Seleziona attività 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

Gli studenti devono

Spunta come completato
Seleziona attività Arbre Couvrant de poids min - Python

Arbre Couvrant de poids min - Python Virtual programming lab

Gli studenti devono

Ricevere una valutazione
Seleziona attività Vidéo (10min): Optimalité de l'algorithme de Prim

Vidéo (10min): Optimalité de l'algorithme de Prim Pagina
Seleziona attività Vidéo (8min): Algorithme de Prim

Vidéo (8min): Algorithme de Prim Pagina
Seleziona attività Kruskal in English 09 22

Kruskal in English 09 22 Virtual programming lab

Gli studenti devono

Spunta come completato

Schema della sezione

Skills