 | |
| MATH0249-1 | Théorie des graphes
 |
|
| Durée : | 30h Th, 30h Pr |
|
| Crédits/ECTS : |
|
|
| Titulaire(s) : | Michel Rigo |
|
| Langue : | Langue française |
|
| Aperçu général : | La théorie des graphes est une branche des mathématiques discrètes. Elle permet la formalisation de divers problèmes et structures et trouve en particulier de nombreuses applications en recherche opérationnelle (problèmes de transport, de tournées,...), en informatique (réseau, routage, télécommunications,...), en combinatoire, en théorie des groupes, en théorie des langages formels, ...
Dans ce cours, on s'attachera à présenter quelques notions fondamentales de la théorie des graphes d'un point de vue théorique. Néanmoins, on mettra aussi en lumière certaines considérations algorithmiques. |
|
| Objectif du cours : | Après avoir présenter les différentes classes de graphes (orientés ou non, multi-graphes, graphes pondérés), le cours aborde plusieurs thèmes classiques dont :
- parcours et chemins de graphes (chemins et circuits Eulériens et Hamiltoniens)
- connexité
- planarité
- arbres
- arbres couvrants
- flots dans un graphe
- décomposition de graphes
- théorie algébrique des graphes
- problèmes de coloriage
- combinatoire des graphes
|
|
| Pré-requis : | Notions de base en algèbre linéaire. La connaissance d'un langage de programmation impératif est souhaitable (en interaction avec le cours d'introduction à la programmation). |
|
| Travaux pratiques : | L'implémentation d'algorithmes sur les graphes est à envisager. |
|
| Organisation : | Le cours est consacré principalement aux aspects théoriques des graphes. Les séances de répétition permettent de présenter la résolution d'exercices mais aussi l'illustration et la concrétisation des concepts et des algorithmes vus au cours. L'horaire des cours et des séances d'exercices sera communiqué en début d'année. |
|
| Notes de cours : | Des notes de cours seront distribuées aux étudiants lors du premier cours. Ces notes sont téléchargeables sur http://www.discmath.ulg.ac.be/ (http:///) |
|
| Evaluation : | L'examen en session comporte une partie orale et une partie écrite. La partie écrite concerne uniquement la résolution d'exercices. La partie orale porte sur la théorie et ses applications directes. La matière de l'examen et les modalités d'interrogation seront précisées par un affichage aux valves. |
|
| Contacts : | M. Rigo
Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
| Remarques : | Des compléments d'information sont disponibles sur
http://www.discmath.ulg.ac.be/ |
|
