Mathématiques discrètes I : Théorie et algorithmique des graphes [ LINMA1691 ]
5.0 crédits ECTS
30.0 h + 22.5 h
1q
| Enseignant(s) |
Blondel Vincent ;
Delvenne Jean-Charles (supplée Blondel Vincent) ;
|
Langue
d'enseignement: |
Français
|
| Lieu de l'activité |
Louvain-la-Neuve
|
| 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 |
Montrer l'utilité des graphes comme outil de modélisation. Développer la théorie élémentaire
des graphes, la caractérisation et l'énumération de différentes classes de graphe, l'existence et la recherche de sous-graphes optimaux, la complexité du calcul de certains paramètres
|
| 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.
|
| Autres infos |
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.
|
Cycle et année
d'étude |
> Bachelier en sciences mathématiques
> Bachelier en sciences de l'ingénieur, orientation ingénieur civil
> Bachelier en sciences informatiques
> Master [120] : ingénieur civil en informatique
> Master [120] en sciences informatiques
> Master [120] : ingénieur civil en mathématiques appliquées
> Master [120] : ingénieur civil électricien
> Master [120] : ingénieur civil électromécanicien
|
Faculté ou entité
en charge |
> MAP
|
<<< Page précédente
|
