Programme des cours 2017-2018
MATH0499-1  
Théorie des graphes
Durée :
25h Th, 20h Pr
Nombre de crédits :
Bachelier en sciences informatiques4
Master en science des données, à finalité4
Master en sciences informatiques, à finalité4
Master en sciences informatiques4
Bachelier en sciences mathématiques4
Nom du professeur :
Michel Rigo
Langue(s) de l'unité d'enseignement :
Langue française
Organisation et évaluation :
Enseignement au premier quadrimestre, examen en janvier
Unités d'enseignement prérequises et corequises :
Les unités prérequises ou corequises sont présentées au sein de chaque programme
Contenus de l'unité d'enseignement :
Dans ce cours, on aborde des thèmes classiques issus de la théorie des graphes :


  • notion de base : graphes, multi-graphes, graphes orientés/non orientés, chemins, circuits
  • connexité
  • graphes acycliques et tri topologique
  • sous-graphes, arbres, arbres couvrants
  • recherche d'un chemin de coût minimum, algorithme de Dijkstra
  • chemins et graphes eulériens 
  • chemins et graphes hamiltoniens
  • rudiments de théorie algébrique des graphes, dénombrement du nombre de chemins de longueur n, application aux suites linéaires récurrentes, illustration de l'algorithme de PageRank
  • graphes bipartis et couplage
  • planarité et formule d'Euler
  • problèmes de coloriage, nombres de Ramsey
  • problèmes de flot (maximum) dans un réseau
L'accent est mis sur les concepts introduits et leur formalisation mathématique. Dans la mesure du possible, ces concepts seront illustrés par des exemples "proches" de problèmes réels (routage, assignation d'adresses, recherche de communautés dans de grands graphes, etc). Le plus souvent, les thèmes présentés débouchent sur la mise en oeuvre d'algorithmes. Ces derniers sont décrits en pseudo-code. Le logiciel de calcul formel Mathematica sera utilisé pour illustrer la majorité des thèmes développés dans le cours.
Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement :
Au terme de ce cours, l'étudiant maîtrisera les notions fondamentales issues de la théorie des graphes. Il/elle sera capable de modéliser un problème en termes de graphes et d'appliquer/donner la marche à suivre des divers algorithmes vus au cours. L'étudiant sera en mesure d'argumenter ses affirmations. Il/elle  disposera d'un arsenal de résultats théoriques compris en profondeu. Il/elle pourra mettre en oeuvre plusieurs résultats et méthodes du cours pour résoudre un exercice de réflexion. 
Savoirs et compétences prérequis :
Ce cours nécessite peu de prérequis. Des bases en algèbre linéaire suffisent (rudiments de calcul matriciel, calcul de déterminant, de polynôme caractéristique, notion de vecteur propre et valeur propre d'une matrice). Etre sensibilisé à la notion de complexité est un atout. Aucun prérequis concernant le logiciel Mathematica n'est nécessaire.
Activités d'apprentissage prévues et méthodes d'enseignement :
Le cours est consacré principalement aux aspects théoriques. Les séances de répétition permettent de présenter la résolution d'exercices et l'illustration ou la concrétisation des concepts vus au cours.
Mode d'enseignement (présentiel ; enseignement à distance) :
Cours théorique avec "tableau et craies" + support vidéo en interaction avec les étudiants. Dans les séances d'exercices, les étudiants sont face à des exercices qu'ils doivent résoudre.
Lectures recommandées ou obligatoires et notes de cours :
Des notes reprenant l'ensemble de la matière enseignée au cours théorique seront distribuées aux étudiants en début d'année. Ces notes de cours sont suffisantes. Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/ (journal de bord, transparents utilisés au cours, ...)
Les étudiants souhaitant disposer d'autres sources d'information peuvent par exemple consulter : 
  • R. Diestel, Graph Theory, Graduate Texts in Mathematics, Volume 173, Springer, 2005. (accessible en ligne)
  • Gibbons, Algorithmic Graph Theory, Cambridge Univ. Press (1985)
  • J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, MacMillan Press (1976).
Modalités d'évaluation et critères :
Deux formules d'évaluation sont possibles. Chaque étudiant doit se prononcer pour l'option retenue avant la fin du mois d'octobre.
1. Première formule (projet d'implémentation, exercices, partie théorique réduite) :
Un examen écrit à livre fermé est organisé. Lors de cet examen, l'étudiant doit pouvoir énoncer et exploiter les définitions et résultats vus au cours. Cet examen comprendra également la résolution de plusieurs exercices se rapportant à l'ensemble de la  matière vue au cours et aux séances de répétition.
Un projet d'implémentation intervient également dans la note finale.  Ce projet nécessite en plus de fournir un code C, la production d'un rapport écrit court devant faciliter la compréhension du code et la défense orale de celui-ci (questions individuelles). Les énoncés et les modalités de présentation seront fournies en cours d'année. Sauf mention explicite, les différents groupes ne peuvent ni collaborer, ni s'inspirer du code d'un autre groupe. La note finale est obtenue sur base des deux scores : examen écrit et projet.
2. Seconde formule (pas de projet d'implémentation, exercices et partie théorique étendue) :
Un examen écrit à livre fermé est organisé. Cet examen porte essentiellement sur la résolution d'exercices se rapportant à la matière vue aux cours et aux séances de répétition.
Un examen oral est également organisé. Il consiste en la présentation d'algorithmes, d'énoncés et de preuves de résultats vus au cours (discussion, applications directes). Il est attendu que l'étudiant puisse développer les preuves vues au cours. La note finale est obtenue sur base des deux notes d'examen.
Stage(s) :
Remarques organisationnelles :
Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/  On peut en particulier y consulter le journal de bord de l'année en cours et aussi celui des années précédentes.
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
Notes en ligne :
Notes de cours
ensemble des notes