Cours MAT3163 – Graphes et optimisation

Poursuivre l’étude rigoureuse des concepts de la théorie des graphes, des algorithmes fondamentaux sur les graphes et leurs applications.

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 Prü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. 

• INF1132 – Mathématiques pour l'informatique
• MAT1060 – Mathématiques algorithmiques