Mathématiques discrètes I : Théorie et algorithmique des graphes [ LINMA1691 ]

> https://icampus.uclouvain.be/claroline/course/index.php?cid=INMA1691

Ce cours suppose acquises les notions élémentaires de mathématiques discrètes et nécessite une maturité suffisante en mathématique, de niveau équivalent à celle d'un étudiant ingénieur arrivé au terme de sa première année d'étude.

Introduction au langage et à la théorie des graphes : questions de caractérisation, isomorphie, existence, énumération. Propriétés de graphes orientés et non-orientés comme la connexité, la planarité, la k-colorabilité, le caractère eulérien, parfait, etc. Modélisation de problèmes pratiques : structure de données et algorithmes pour l'exploration des graphes. Développement d'algorithmes de base avec analyse de leur complexité.

Eu égard au référentiel AA, ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

• AA1 : 1,2,3

Plus précisément, au terme du cours, l'étudiant sera capable de :

• modéliser des problèmes divers dans le langage de la théorie des graphes
• reconnaître si un problème de théorie des graphes a une solution algorithmique efficace ou non
• proposer et appliquer un algorithme pour résoudre ce problème, au moins pour certaines classes de graphes
• démontrer de façon claire et rigoureuse des propriétés élémentaires relatives aux concepts couverts

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».

Les étudiants sont évalués individuellement et par écrit sur la base des objectifs particuliers énoncés plus haut.

Le cours est organisé autour de séances de cours et de séances d'exercices supervisées.

Structure et caractérisation des graphes - Concepts de base - degré, composante connexe, chemin, cycle, coupe, mineur. Classes de graphes et leur reconnaissance -graphe parfait, série-parallèle, planaire, digraphe acyclique. Exploration des graphes et test de leurs propriétés - k-connexion, planaire, eulérien. Flots - théorèmes de Menger et Hall, algorithmes de flot maximum, de flot de coût minimum et leur complexité. Problèmes: couplage optimal, ensemble stable optimal, problème du voyageur de commerce et de partitionnement, calcul du nombre chromatique.

Ouvrage de base :

Graph Theory with Applications, A. Bondy- U.S.R. Murty, Springer, téléchargement libre

Aussi :

• Algorithmic Graph Theory, Alan Gibbons, Cambridge University Press 1985
• Introduction to Graph Theory, Douglas West, Prentice Hall 1996.
• Combinatorial Optimization, W.R. Cook et al., Wiley 1998.
• Network Flows, Ahuja et al., Prentice Hall 1993.