En raison de la crise du COVID-19, les informations ci-dessous sont susceptibles d’être modifiées,
notamment celles qui concernent le mode d’enseignement (en présentiel, en distanciel ou sous un format comodal ou hybride).
5 crédits
30.0 h + 22.5 h
Q1
Enseignants
Blondel Vincent; Delvenne Jean-Charles;
Langue
d'enseignement
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
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 :
|
Contenu
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.
Méthodes d'enseignement
En raison de la crise du COVID-19, les informations de cette rubrique sont particulièrement susceptibles d’être modifiées.
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
des acquis des étudiants
En raison de la crise du COVID-19, les informations de cette rubrique sont particulièrement susceptibles d’être modifiées.
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.
Ressources
en ligne
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 :
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
en charge
MAP
Force majeure
Modes d'évaluation
des acquis des étudiants
des acquis des étudiants
L'examen est écrit, en présentiel. Un examen de modalité adaptée sera proposé aux étudiant/es pouvant faire valoir préalablement à l’examen une impossibilité de participer à l’examen organisé sur site, impossibilité attestée par un certificat de quarantaine ou un ‘formulaire retour’ du SPF Affaires Etrangères, pour peu que le titulaire principal (Jean-Charles Delvenne) soit averti dès que possible et en tout cas avant la date de l'examen principal. Cet examen parallèle portera sur la même matière que l’examen principal, et se déroulera sous une forme compatible avec la situation de quarantaine de l’étudiant/e.
Programmes / formations proposant cette unité d'enseignement (UE)
Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
d'apprentissage
Mineure en Mathématiques appliquées
Master [120] : ingénieur civil en informatique
Master [120] en sciences informatiques
Master [120] : ingénieur civil électricien
Approfondissement en sciences mathématiques
Mineure en sciences de l'ingénieur : mathématiques appliquées (accessible uniquement pour réinscription)
Filière en Mathématiques Appliquées