-
Partager cette page
Graph theory
Titulaire(s) du cours
Gwenaël JORET (Coordonnateur)Crédits ECTS
5
Langue(s) d'enseignement
anglais
Contenu du cours
Le cours est un cours d'introduction à la théorie des graphes, donné en anglais. Aperçu des sujets abordés :
- Matchings in bipartite and non-bipartite graphs;
- Connectivity (Menger's theorem, the structure of 2- and 3-connected graphs);
- Planar graphs (plane graphs, Euler's formula, Kuratowski's theorem);
- Coloring (coloring planar graphs, vertex- and edge-colorings, perfect graphs);
- Structural graph theory (treewidth, minors);
- Extremal graph theory;
- Random graphs;
- The probabilistic method.
Objectifs (et/ou acquis d'apprentissages spécifiques)
Le cours a pour but d'acquérir les bases de la théorie des graphes.
Méthodes d'enseignement et activités d'apprentissages
24h de cours magistral, 12h heures d'exercices, deux devoirs
Références, bibliographie et lectures recommandées
1) Reinhard Diestel, Graph Theory (3ème édition), Graduate Texts in Mathematics 173. Publié par Springer en Juillet 2006.
Autres renseignements
Contacts
Gwenaël JORET - Campus Plaine - Département d'Informatique - CP212 Bâtiment N/O, bureau 2.O8.111 (gwenael.joret@ulb.be)
Campus
Plaine
Evaluation
Méthode(s) d'évaluation
- Autre
Autre
Devoirs + examen écrit sur la théorie et les exercices.
Construction de la note (en ce compris, la pondération des notes partielles)
Devoirs : 4 points
Examen écrit : 16 points (moitié théorie - moitié exercices)
Langue(s) d'évaluation
- anglais