Секция: 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 Лекция

Студенты должны

Просмотреть

Пройти лекцию до конца
Выбрать элемент 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 Виртуальная лаборатория программирования

Студенты должны

Получить оценку
Выбрать элемент 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) Виртуальная лаборатория программирования

Студенты должны

Отметить как выполненный
Выбрать элемент Arbre Couvrant de poids min - Python

Arbre Couvrant de poids min - Python Виртуальная лаборатория программирования

Студенты должны

Получить оценку
Выбрать элемент 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 Виртуальная лаборатория программирования

Студенты должны

Отметить как выполненный

Section outline

Skills