Sección: Tree | Théorie des Graphes

Trees and Forests
Rooted trees
Minimum spanning trees

Seleccionar actividad 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
Seleccionar actividad Transparents Arbres

Transparents Arbres Archivo

Los estudiantes deben

Ver
Seleccionar actividad One idea, one story: Les Hydrocarbones saturés acycliques

One idea, one story: Les Hydrocarbones saturés acycliques Lección

Los estudiantes deben

Ver

Completa la actividad hasta el final
Seleccionar actividad Transparents Arbre couvrant de poids min

Transparents Arbre couvrant de poids min Archivo

Los estudiantes deben

Ver
Seleccionar actividad 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 Página

Los estudiantes deben

Ver
Seleccionar actividad Feuille d'exercice Arbres

Feuille d'exercice Arbres Archivo

Los estudiantes deben

Ver
Seleccionar actividad Étiquette
Seleccionar actividad Test sur les arbres

Test sur les arbres Cuestionario

Los estudiantes deben

Ver

Recibir una calificación

Recibir una calificación de aprobado
Seleccionar actividad Tests on trees and on Kruskal algorithm

Tests on trees and on Kruskal algorithm Cuestionario

Los estudiantes deben

Ver

Recibir una calificación

Recibir una calificación de aprobado
Seleccionar actividad Algorithmes de Kruskal et Union Find - Java

Algorithmes de Kruskal et Union Find - Java Laboratorio virtual de programación

Los estudiantes deben

Recibir una calificación
Seleccionar actividad Javadoc de GraphePondere.java

Javadoc de GraphePondere.java Archivo

Los estudiantes deben

Ver
Seleccionar actividad Javadoc de Arete.java

Javadoc de Arete.java Archivo

Los estudiantes deben

Ver
Seleccionar actividad 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) Laboratorio virtual de programación

Los estudiantes deben

Marcar como hecha
Seleccionar actividad Arbre Couvrant de poids min - Python

Arbre Couvrant de poids min - Python Laboratorio virtual de programación

Los estudiantes deben

Recibir una calificación
Seleccionar actividad Vidéo (10min): Optimalité de l'algorithme de Prim

Vidéo (10min): Optimalité de l'algorithme de Prim Página
Seleccionar actividad Vidéo (8min): Algorithme de Prim

Vidéo (8min): Algorithme de Prim Página
Seleccionar actividad Kruskal in English 09 22

Kruskal in English 09 22 Laboratorio virtual de programación

Los estudiantes deben

Marcar como hecha

Perfilado de sección

Skills