Programme d'études 2002-2003 > FSA > INMA2691

• Objectifs
• Cahier des charges
• Programmes proposant cette activité
• Valeurs ECTS de l'activité

Objectifs

Montrer l'utilité des graphes comme outil de modélisation. Développer la théorie élémentaire des graphes, et introduire les algorithmes de base pour l'exploration des graphes, des problèmes de réseaux, etc...

Cahier des charges

Partie 1. Structure et caractérisation des graphes Concepts de base (connexité, nombre cyclomatique, cycles et co-cycles, mineurs); Classes de graphes et leur reconnaissance : graphes planaires, série-parallèle, etc...

Partie 2. Problèmes polynomiaux; Exploration des graphes et test de leur propriétés (connexion, planarité; Flots (Théorèmes de Menger et Hall. Algorithmes récents de flot maximum et de fot à coût minimum, analyse de complexité par amortissement etc...) ; Algorithmes spécialisés pour graphes planaires;

Partie 3. Problèmes difficiles Ensembles stables, cliques et coloration (dualité, graphes parfaits, polynome chromatique, algorithme heuristique pour coloration, horaires, etc ); Autres problèmes tels que le voyageur de commerce, le partitionnement de graphes (algorithmes d'échange et application).

Le cours INMA2691 est mentionné dans les programmes suivants :

Valeurs ECTS de l'activité

Programme d'études 2002-2003 > FSA > INMA2691

Recherche - Aide - Renseignements généraux

[UCL] [Site Web Facultaire] [Pointeurs utiles]

Responsable : Jean-Louis Marchand
Contact : secretaire@fsa.ucl.ac.be