2017-2018 / MATH0499-1

Théorie des graphes

Durée

25h Th, 20h Pr

Nombre de crédits

 Bachelier en sciences informatiques4 crédits 
 Master en science des données, à finalité4 crédits 
 Master en sciences informatiques, à finalité4 crédits 
 Master en sciences informatiques4 crédits 
 Bachelier en sciences mathématiques4 crédits 

Enseignant

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