Théorie des graphes

Durée

25h Th, 20h Pr

Nombre de 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

Horaire

Horaire en ligne

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

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 profondeur. 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 calcul matriciel suffisent (rudiments de calcul matriciel, calcul de déterminant, notion de vecteur propre et valeur propre d'une matrice). Pour les étudiants informaticiens, des liens sont établis avec le cours "Mathématiques pour l'Informatique II".  Etre sensibilisé à la notion de complexité est un atout.

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, à distance, hybride)

Combinaison d'activités d'apprentissage en présentiel et en distanciel


Explications complémentaires:

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. Une partie des heures d'enseignement (théorie et/ou exercices) pourra être dispensée sous forme de vidéo à visionner à distance et complété par des séances de question/réponse.

Supports de cours, lectures obligatoires ou recommandées

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)
• M. Rigo, Advanced graph theory and combinatorics, ISTE-Wiley (2016).

Modalités d'évaluation et critères

Examen(s) en session

Toutes sessions confondues

- En présentiel

évaluation écrite ( questions ouvertes )

Travail à rendre - rapport


Explications complémentaires:

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 ou Python, 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. Une insuffisance grave observée à l'une des parties pénalise la note finale. 

2. Seconde formule (pas de projet d'implémentation, exercices et partie théorique étendue) :

Un examen écrit à livre fermé est organisé. Cet examen comporte deux volets. L'un porte sur la résolution d'exercices se rapportant à la matière vue aux cours et aux séances de répétition.
L'autre porte sur la présentation et la compréhension des algorithmes, énoncés et preuves détaillées vus au cours (discussion, applications directes). Il est attendu que l'étudiant puisse développer toutes les preuves abordées au cours.

La note finale est obtenue sur base des deux volets de l'examen. Une insuffisance grave observée à l'une des parties pénalise la note finale. 

Stage(s)

Remarques organisationnelles et modifications principales apportées au cours

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

Association d'un ou plusieurs MOOCs

Notes en ligne