 | | |
| MATH0499-1 | Théorie des graphes
|
|
| Durée : | 25h Th, 20h Pr |
|
| Nombre de crédits : |
|
|
| Nom du professeur : | Michel Rigo |
|
Langue(s) du cours :
|
| Langue française |
|
Organisation et évaluation :
|
| Enseignement au premier quadrimestre, examen en janvier |
|
Contenus du cours :
|
| Dans ce cours, on aborde des thèmes classiques issus de la théorie des graphes :
- notion de base : graphes, multi-graphes, graphes orientés/non orientés, chemins, circuits
- connexité
- graphes acycliques et tri topologique
- sous-graphes, arbres, arbres couvrants
- recherche d'un chemin de coût minimum, algorithme de Dijkstra
- chemins et graphes eulériens
- chemins et graphes hamiltoniens
- rudiments de théorie algébrique des graphes, dénombrement du nombre de chemins de longueur n, application aux suites linéaires récurrentes, illustration de l'algorithme de PageRank
- graphes bipartis et couplage
- planarité et formule d'Euler
- problèmes de coloriage, nombres de Ramsey
- noyau d'un graphe, applications aux jeux combinatoires
- problèmes de flot (maximum) dans un réseau
L'accent est mis sur les concepts introduits et leur formalisation mathématique. Dans la mesure du possible, ces concepts seront illustrés par des exemples "proches" de problèmes réels (routage, assignation d'adresses, recherche de communautés dans de grands graphes, etc). Le plus souvent, les thèmes présentés débouchent sur la mise en oeuvre d'algorithmes. Ces derniers seront décrits en pseudo-code. |
|
Acquis d'apprentissage (objectifs d'apprentissage) du cours :
|
| Au terme de ce cours, l'étudiant maîtrisera les notions fondamentales issues de la théorie des graphes. Il/elle sera capable de modéliser un problème en termes de graphes et d'appliquer/donner la marche à suivre des divers algorithmes vus au cours. L'étudiant sera en mesure d'argumenter ses affirmations. Il/elle disposera d'un arsenal de résultats théoriques compris en profondeur et pour lesquels il/elle sera capable d'en fournir et d'en expliquer les preuves. Il/elle pourra mettre en oeuvre plusieurs résultats et méthodes du cours pour résoudre un exercice de réflexion. |
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| Ce cours nécessite peu de prérequis. Des bases en algèbre linéaire suffisent (rudiments de calcul matriciel, notion de vecteur propre et valeur propre d'une matrice). Etre sensibilisé à la notion de complexité est un atout. |
|
Activités d'apprentissage prévues et méthodes d'enseignement :
|
| Le cours est consacré principalement aux aspects théoriques.
Les séances de répétition permettent de présenter la résolution d'exercices et l'illustration ou la concrétisation des concepts vus au cours.
On pourra aussi envisager d'implémenter certains algorithmes lors de ces séances d'exercices. |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| Cours théorique avec "tableau et craies" en interaction avec les étudiants. Dans les séances d'exercices, les étudiants sont face à des exercices qu'ils doivent résoudre. |
|
Lectures recommandées ou obligatoires et notes de cours :
|
| Des notes reprenant l'ensemble de la matière enseignée au cours théorique seront distribuées aux étudiants en début d'année.
Ces notes de cours sont suffisantes. Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/ (journal de bord, transparents utilisés au cours, ...)
Les étudiants souhaitant disposer d'autres sources d'information peuvent par exemple consulter :
- R. Diestel, Graph Theory, Graduate Texts in Mathematics, Volume 173, Springer, 2005. (accessible en ligne)
- Gibbons, Algorithmic Graph Theory, Cambridge Univ. Press (1985)
- J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, MacMillan Press (1976).
|
|
Modalités d'évaluation et critères :
|
| L'examen en session (dont la date sera fixée au niveau du conseil des études) comporte une partie orale (présentations d'algorithmes, énoncés et preuves de résultats, avec discussion) et une partie écrite. La partie écrite concerne uniquement la résolution d'exercices. La partie orale porte sur la théorie et ses applications directes. |
|
Stage(s) :
|
| |
|
Remarques organisationnelles :
|
| Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/
On peut en particulier y consulter le journal de bord de l'année en cours et aussi celui des années précédentes. |
|
Contacts :
|
| M. Rigo
Institut de Mathématique (B37) -
Grande Traverse 12 -
Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 -
E-mail : M.Rigo@ulg.ac.be |
|
|
|
| Notes en ligne : |
|
| Notes de cours |
| ensemble des notes |
|
|
