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
• AA3 : 1,3
• AA4 : 1
• AA5 : 1,2,3, 5,6

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

• consulter une littérature généraliste ou spécialisée sur un thème précis à la pointe des mathématiques discrètes, en forger une synthèse qui contienne les messages et résultats importants
• expliquer à leurs pairs ces messages et résultats de façon claire et précise
• résoudre des problèmes mathématiques en application à ces résultats
• mener une réflexion critique sur les limites des résultats ou la façon dont ils sont présentés
• relier les concepts vus dans la littérature aux concepts vus dans d'autres cours, malgré des notations ou interprétations variées

Acquis d'apprentissage transversaux :

• Recherche critique d'information dans des ouvrages plus ou moins spécialisés, Internet, etc.

Les étudiants sont évalués individuellement et par écrit sur base des objectifs particuliers énoncés plus haut. En outre les étudiants réalisent un projet original. Les projets donnent lieu à la présentation d'un rapport et à sa défense. La note obtenue pour le projet est comptabilisée dans la note finale.

Le cours est organisé autour de séances de cours, de séances d'exercices supervisées et d'un travail original à réaliser par petits groupes. Une consultance est offerte pour un soutien dans la réalisation du travail.

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.

• 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.