Théorie et pratique des graphes et réseaux

Ce cours a pour objectif de guider les étudiants dans la réalisation d’un projet complet mobilisant des concepts fondamentaux et avancés de la théorie des graphes. À partir de jeux de données issus de plateformes open data (comme data.gouv.fr), les étudiants apprendront à :

• Collecter, nettoyer et structurer les données pour en extraire une représentation pertinente sous forme de graphe ;
• Modéliser un problème concret à partir de ces données, en définissant les nœuds, les arêtes et les propriétés associées ;
• Appliquer des algorithmes classiques de la théorie des graphes (recherche de composantes connexes, plus courts chemins, détection de communautés, couverture de sommets, etc.) pour résoudre une problématique réelle non triviale ;
• Visualiser et interpréter les résultats à l’aide d’outils spécialisés tels que Graphviz ou Gephi, dans une perspective d’analyse et de restitution.

Ce projet permettra aux étudiants de mettre en pratique des compétences transversales en algorithmique, en manipulation de données et en modélisation, tout en découvrant les nombreuses applications de la théorie des graphes dans des contextes concrets.

À l’issue de ce cours, les étudiants seront capables de :

1. Identifier un problème réel pouvant être modélisé sous forme de graphe, à partir de données ouvertes hétérogènes.
2. Collecter, nettoyer et préparer des données issues de plateformes open data (ex. : data.gouv.fr) pour les rendre exploitables dans un cadre algorithmique.
   
   
3. Construire un graphe pertinent (choix des sommets, des arêtes, pondérations éventuelles) en fonction de la problématique étudiée.
   
   
4. Mobiliser des algorithmes classiques de la théorie des graphes pour analyser et résoudre un problème non trivial (exemples : composantes connexes, centralité, plus courts chemins, flots, détection de communautés, couverture de sommets, etc.).
   
   
5. Interpréter les résultats obtenus à partir des traitements algorithmiques et en évaluer la pertinence au regard du problème initial.
   
   
6. Utiliser des outils de visualisation de graphes (tels que Graphviz ou Gephi) pour produire une restitution graphique claire et exploitable.
   
   
7. Développer une démarche de projet en autonomie ou en petit groupe, incluant la formulation d’hypothèses, la définition d’un plan d’analyse, le choix d’outils et la production d’un livrable final.

• Session 1

Formule standard :
Modalité : Contrôle continu
Type : Dossier

Formule dérogatoire :
Type : Dossier

• Session 2 :

Type : Dossier

Langage python

1. Compétences techniques

• Maîtriser les étapes de préparation de données issues de sources ouvertes : collecte, nettoyage, transformation.
• Modéliser une situation réelle sous forme de graphe.
• Implémenter et utiliser des algorithmes classiques de la théorie des graphes :
  • parcours (DFS, BFS),
  • plus courts chemins (Dijkstra, Bellman-Ford),
  • détection de cycles,
  • composantes connexes,
  • centralité,
  • couverture de sommets, etc.
• Utiliser des bibliothèques de manipulation et d’analyse de graphes (networkx, igraph, etc.).
• Produire des visualisations de graphes pertinentes avec Graphviz, Gephi ou autres outils spécialisés.
  
  

2. Compétences théoriques

• Comprendre les structures fondamentales de la théorie des graphes : types de graphes, propriétés, invariants.
• Choisir des algorithmes adaptés à une problématique donnée et en comprendre la complexité.
• Analyser les résultats obtenus et leur signification dans le contexte du problème modélisé.
  
  

3. Compétences transversales

• Mener un projet de bout en bout, de la formulation du problème à la restitution des résultats.
• Travailler en autonomie ou en collaboration dans une démarche de recherche de solution.
• Présenter et vulgariser une démarche algorithmique appliquée à des données réelles.
• Mobiliser des outils numériques variés dans une optique de résolution de problème.
• Documenter le code, les choix techniques et les résultats obtenus dans un format clair et structuré (rapport).