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

linma1691  2023-2024  Louvain-la-Neuve

Mathématiques discrètes I : Théorie et algorithmique des graphes
5.00 crédits
30.0 h + 22.5 h
Q1
Enseignants
Blondel Vincent; Delvenne Jean-Charles;
Langue
d'enseignement
Français
Préalables
Ce cours suppose acquises les notions élémentaires de mathématiques discrètes telles qu'enseignées dans le cours LEPL1108.
Thèmes abordés
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é.
Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

1 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
 
Contenu
Structure et caractérisation des graphes - Concepts de base - degré, composante connexe, chemin, cycle, coupe, mineur.  Exploration des graphes et test de leurs propriétés - k-connexité, graphes planaires, eulériens. Flots - théorèmes de Menger et Hall, algorithmes de flot maximum, de flot de coût minimum et leur complexité. Algèbre linéaire en théorie des graphes. Problèmes: couplage optimal, ensemble indépendant optimal, problème du voyageur de commerce et de partitionnement, calcul du nombre chromatique. Distinction entre problèmes "faciles" et "difficiles", NP-complétude.
Méthodes d'enseignement
Le cours est organisé autour de séances de cours et de séances d'exercices supervisées.
Modes d'évaluation
des acquis des étudiants
Les étudiants sont évalués par des projets durant le quadrimestre et par un examen écrit (ou oral selon les circonstances), sur la base des objectifs particuliers énoncés plus haut. Les projets du quadrimestre comptent pour 25% de la note finale (de janvier comme d'août).
Ces projets donneront lieu à une note globale unique, communiquée après la fin du semestre. Le non-respect des consignes méthodologiques définies sur Moodle, notamment en matière d’utilisation de ressources en ligne ou de collaboration entre étudiant.e.s, pour tout projet entraînera une note globale de 0 pour l'entièreté des projets.
Ressources
en ligne
Page Moodle du cours
Bibliographie
Ouvrage de base (non obligatoire) / primary (non mandatory) reference :
Graph Theory with Applications, A. Bondy- U.S.R. Murty, Springer, téléchargement libre/free download
Aussi /also :
  • 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.
Support de cours
  • Notes de cours/lectures notes
  • Transparents/slides
Faculté ou entité
en charge
MAP


Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Approfondissement en sciences mathématiques

Mineure en Mathématiques appliquées

Filière en Mathématiques Appliquées

Master [120] : ingénieur civil électricien

Master [120] : ingénieur civil en informatique

Master [120] en sciences informatiques

Mineure Polytechnique