Тема: Tree | Théorie des Graphes

Trees and Forests
Rooted trees
Minimum spanning trees

Изберете дейност 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
Изберете дейност Transparents Arbres

Transparents Arbres Файл

Обучаваните трябва

Преглеждане
Изберете дейност One idea, one story: Les Hydrocarbones saturés acycliques

One idea, one story: Les Hydrocarbones saturés acycliques Урок

Обучаваните трябва

Преглеждане

Go through the activity to the end
Изберете дейност Transparents Arbre couvrant de poids min

Transparents Arbre couvrant de poids min Файл

Обучаваните трябва

Преглеждане
Изберете дейност 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 Страница

Обучаваните трябва

Преглеждане
Изберете дейност Feuille d'exercice Arbres

Feuille d'exercice Arbres Файл

Обучаваните трябва

Преглеждане
Изберете дейност Étiquette
Изберете дейност Test sur les arbres

Test sur les arbres Тест

Обучаваните трябва

Преглеждане

Получаване на оценка

Получаване на оценка за преминаване
Изберете дейност Tests on trees and on Kruskal algorithm

Tests on trees and on Kruskal algorithm Тест

Обучаваните трябва

Преглеждане

Получаване на оценка

Получаване на оценка за преминаване
Изберете дейност Algorithmes de Kruskal et Union Find - Java

Algorithmes de Kruskal et Union Find - Java Virtual programming lab

Обучаваните трябва

Получаване на оценка
Изберете дейност Javadoc de GraphePondere.java

Javadoc de GraphePondere.java Файл

Обучаваните трябва

Преглеждане
Изберете дейност Javadoc de Arete.java

Javadoc de Arete.java Файл

Обучаваните трябва

Преглеждане
Изберете дейност 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

Обучаваните трябва

Отбелязване като завършено
Изберете дейност Arbre Couvrant de poids min - Python

Arbre Couvrant de poids min - Python Virtual programming lab

Обучаваните трябва

Получаване на оценка
Изберете дейност Vidéo (10min): Optimalité de l'algorithme de Prim

Vidéo (10min): Optimalité de l'algorithme de Prim Страница
Изберете дейност Vidéo (8min): Algorithme de Prim

Vidéo (8min): Algorithme de Prim Страница
Изберете дейност Kruskal in English 09 22

Kruskal in English 09 22 Virtual programming lab

Обучаваните трябва

Отбелязване като завършено

Схема на раздела

Skills