COURS // MAT3163 Graphes et optimisation
Mes cours favoris
Ce système permet de sélectionner vos cours favoris en prévision de votre inscription qui se fait sur le portail étudiant.
| Trimestre | Cours | Groupe |
|---|
Description du cours
- 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]
