L'unité d'enseignement ENSIN4U6
« Éléments de combinatoire et de théorie des graphes »

Familiariser les étudiants avec les bases de la théorie des graphes et la combinatoire utilisées en informatique et en mathématiques discrètes ; apprendre à modéliser des problèmes dans le langage des graphes.

• Graphes, représentation des graphes, arbres, cycles, connexité.
• Tours d'Euler et tours de Hamilton.
• Coloriage des sommets et des arêtes.
• Graphes planaires, graphes sur des surfaces et la caractéristique d'Euler.
• Graphes d'intervalles, graphes parfaits.
• Flots, connexité, couplages.
• Introduction à la combinatoire ; algorithmes de combinatoire énumérative.
• Combinatoire des familles d'ensembles ; principe de Dirichlet et théorème de Ramsay ; principe d'inclusion-exclusion et ses applications.
• Comptage et énumération : nombre d'arbres couvrants d'un graphe, nombre de couplages d'un graphe planaire.