- Graphes et optimisation

Premier cycle

Cycle : 1 Type de cours : Magistral Nombre de crédits : 3 Discipline : Mathématiques Objectifs Poursuivre l'étude rigoureuse des concepts de la théorie des graphes, des algorithmes fondamentaux sur les graphes et leurs applications. Sommaire du contenu Rappels sur les graphes (simples, orientés, valués), leurs représentations et les concepts de base (chaînes, cycles, chemins). Arbres et leurs propriétés, codage de Pru¿fer et la formule de Cayley. Problèmes d'optimisation sur les graphes : algorithmes de construction d'un arbre couvrant de coût minimal, chemins maximaux ou minimaux. Sujets complémentaires au choix de l'enseignant, par exemple : modèles graphiques probabilistes, applications aux chaînes de Markov, caractérisation et propriétés de certaines familles de graphes, matroïdes, problèmes de l'isomorphisme de graphes, applications aux polytopes et le théorème de Steinitz, réseaux de résistances, graphes plabiques, théorie de Ramsay, graphes aléatoires, polynôme de Tutte. Préalables académiques [MAT1060 Mathématiques algorithmiques] ou [INF1132 Mathématiques pour l'informatique] Programmes associés à ce cours Baccalauréat en mathématiques, concentration en mathématiques Baccalauréat en mathématiques, concentration en statistique Baccalauréat en mathématiques, concentration informatique Majeure en statistique