UCL - Etudes

English version

Formations
Premier cycle
Deuxième cycle
Troisième cycle
Certificats (programmes non académiques)
Passerelles
Formation continue
Facultés et entités
Cadre académique
Réforme de Bologne
Accès aux études
Organisation des études
Lexique
Calendrier académique
Règlement des études et examens
Charte pédagogique
Renseignements généraux
Recherche
Simple
Détaillée
Par cours

Théorie et algorithmique des graphes [INMA1691]
[30h+22.5h exercices] 5 crédits

English version

Version imprimable

Cette activité se déroule pendant le 2ème semestre

Enseignant(s):

Vincent Blondel, Laurence Wolsey

Langue d'enseignement :

français

Niveau :

Premier cycle

>> Objectifs (en termes de compétences)
>> Objet de l'activité (principaux thèmes à aborder)
>> Résumé : Contenu et Méthodes
>> Autres informations (Pré-requis, Evaluation, Support, ...)
>> Autres crédits de l'activité dans les programmes

Objectifs (en termes de compétences)

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

Objet de l'activité (principaux thèmes à aborder)

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

Résumé : Contenu et Méthodes

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 informations (Pré-requis, Evaluation, Support, ...)

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.

Autres crédits de l'activité dans les programmes

ECGE3DS/SC

Diplôme d'études spécialisées en économie et gestion (Master in business administration) (Supply Chain Management)

(5 crédits)

Obligatoire

FSA12BA

Deuxième année de bachelier en sciences de l'ingénieur, orientation ingénieur civil

(5 crédits)

FSA13BA

Troisième année de bachelier en sciences de l'ingénieur, orientation ingénieur civil

(5 crédits)

FSA3DS/IN

Diplôme d'études spécialisées en sciences appliquées (informatique)

(5 crédits)

INFO22

Deuxième année du programme conduisant au grade d'ingénieur civil informaticien

(5 crédits)

INFO23

Troisième année du programme conduisant au grade d'ingénieur civil informaticien

(5 crédits)

MAP22

Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées

(5 crédits)

SINF12BA

Deuxième année d'études de bachelier en sciences informatiques

(5 crédits)



Ce site a été conçu en collaboration avec ADCP, ADEF, CIO et SGSI
Responsable : Jean-Louis Marchand - Contact : secretaire@fsa.ucl.ac.be
Dernière mise à jour :13/03/2007