Graphes

Ce cours propose un approfondissement de la théorie des graphes, en dépassant l’usage des graphes comme simple outil de modélisation pour aborder leur étude comme objet mathématique et algorithmique. Il s’inscrit dans la continuité des cours d’algorithmique, d’optimisation combinatoire et de recherche opérationnelle.

Le cours met l’accent sur le raisonnement, la preuve et l’analyse fine des structures de graphes. Les notions étudiées pourront inclure les classes de graphes, les invariants, les problèmes de domination, de couverture, d’indépendance, de partitionnement, de connectivité, ainsi que certaines questions de complexité algorithmique. Des résultats seront démontrés en cours afin d’habituer les étudiants à manipuler des arguments combinatoires, des preuves par contradiction, des constructions d’exemples et de contre-exemples.

Une attention particulière sera portée au lien entre propriétés structurelles et difficulté algorithmique. Le cours montrera comment certaines restrictions sur les graphes peuvent rendre un problème plus accessible, tandis que d’autres problèmes restent difficiles même sur des classes particulières. Des outils informatiques, des solveurs et des agents fondés sur les LLM pourront être utilisés pour explorer des exemples, générer des conjectures, chercher des contre-exemples ou assister la rédaction de preuves, tout en conservant une validation mathématique rigoureuse.

À l’issue du cours, les étudiants devront être capables de :

• Manipuler des notions avancées de théorie des graphes.
• Comprendre et rédiger des démonstrations portant sur des propriétés de graphes.
• Utiliser des invariants pour caractériser ou comparer des graphes.
• Analyser des problèmes classiques comme la domination, la couverture, l’indépendance ou le partitionnement.
• Identifier le rôle des classes de graphes dans l’étude d’un problème.
• Construire des exemples, des contre-exemples et des familles infinies de graphes.
• Distinguer les résultats structurels, algorithmiques et de complexité.
• Relier une propriété locale d’un graphe à un comportement global.
• Utiliser des outils numériques pour expérimenter sur des graphes et tester des conjectures.
• Evaluer de manière critique les résultats produits par des outils d’IA ou des programmes d’exploration.

Modalités : Mixte : CC + CT
SESSION 1 :
Contrôle Continu
• Type : Écrit, QCM, Oral
• Durée : 2h00
• Précisions : Le contrôle continu représente les 50 % restants et comprend un devoir écrit ou sur machine comptant pour 25 % et un projet comptant pour 25 %.

Contrôle Terminal
• Type : Écrit
• Durée : 1h30
• Précisions : Une durée indicative de 2h00, susceptible d’être ajustée en fonction des contraintes pédagogiques, matérielles ou logistiques, dans le respect des M3C applicables.

Régime Dérogatoire
• Type : Écrit
• Durée : 1h30
• Précisions : Une durée indicative de 2h00, susceptible d’être ajustée en fonction des contraintes pédagogiques, matérielles ou logistiques, dans le respect des M3C applicables.

SESSION 2 :
• Type : Écrit
• Durée : 1h30
• Précisions : Une durée indicative de 2h00, susceptible d’être ajustée en fonction des contraintes pédagogiques, matérielles ou logistiques, dans le respect des M3C applicables.

Utilisation de l'intelligence artificielle :
L’utilisation de l’Intelligence Artificielle est interdite lors des évaluations.

Optimisation combinatoire et algorithmique

● Maîtriser le vocabulaire et les objets avancés de la théorie des graphes.
● Raisonner sur des propriétés combinatoires et produire des preuves rigoureuses.
● Étudier des invariants de graphes et comprendre leurs relations.
● Analyser des problèmes de domination, de couverture, d’indépendance et de partitionnement.
● Exploiter les classes de graphes pour affiner l’analyse d’un problème.
● Construire et utiliser des contre-exemples pour tester une conjecture.
● Comprendre les liens entre structure d’un graphe, algorithmes et complexité.
● Mobiliser des outils informatiques pour générer, visualiser et analyser des graphes.
● Utiliser des LLM et des agents comme supports d’exploration, sans déléguer la preuve ni la validation mathématique.