| Crédit : 3 ECTS |
| Langue du cours : anglais
|
|
|
|
Volume horaire
- CM :
15 h
- Volume horaire global (hors stage) :
15 h
Compétences à acquérir
The goal is to understand the deep links between efficient algorithms, structures in graphs, and geometry of polyhedra.
Description du contenu de l'enseignement
In this course, we introduce the notion of perfect graph. We start by proving that bipartite graphs, their line-graphs and the complement of both classes are all perfect. We prove the weak perfect graph theorem, namely, that complement of perfect graphs are perfect. Further problems, around the notion of complete bipartite subraph are studied to illustrate more the interactions between graphs and linear algebra.
Mode de contrôle des connaissances
One exam.
Bibliographie, lectures recommandées
Bibliographie Combinatorial Optimization : Polyhedra and Efficiency. A. Schrijver , Springer (2003)
Enseignant responsable
DENIS CORNAZ