Editorial

Si vous envisagez de suivre ce cours en 2012-2013, inscrivez-vous maintenant sur la plate-forme icampus! 

Le premier cours aura lieu le mardi 18 septembre à 14h00 au local BARB20. Il n'y aura pas de séance d'exercice durant la première semaine S1. L'horaire pour les premières séances est repris plus bas.

Enseignant

Vincent Blondel, http://perso.uclouvain.be/vincent.blondel/                           

Assistants

Vincent Traag, responsable projet
Romain Hollanders, séance mardi 14h00
Arnaud Browet, séance lundi 8h30

Références et documents:

Introduction to graph theory, Douglas West, Prentice Hall, 1996.
Exercices, 2008-2009, par V. Blondel.
Notes de cours, INMA1691, 2005-2006, par L. Wolsey.

Projet

La réalisation d’un projet fait partie intégrale du cours. On demande une compréhension du sujet choisi, une démarche active de recherche et d'analyse d'informations, d'éventuels développements originaux, la rédaction d'un rapport d'une petite dizaine de pages et une présentation orale en fin d'année. Le projet s'effectue par groupe et donne lieu à une présentation orale. Le projet est évalué sur base des éléments suivants : rapport écrit, qualité et originalité du contenu, qualité de la présentation, réponses aux questions et maîtrise de la matière.

Evaluation

Rapport de projet et présentation orale: 30 %
Examen écrit:70 %

Contenu (sous réserve) 

1. Terminologie, propriétés élémentaires, graphe orientés, connexité, représentation des graphes.
2. Connexité, plus court chemin, exploration.
3. Arbres de recouvrement, arbre de recouvrement de poids minimum.
4. Enumération des arbres, circuits et connectivité, circuits fondamentaux.
5. Graphes planaires, mineurs.
6. Réseaux et flots.
7. Graphes Eulériens et Hamiltoniens.
8. Stables et coloration, polynôme chromatique.
9. Couplages.