année académique
2023-2024

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

Programmes