Même sans le savoir, l'apprenant a déjà vu certains classements dans le passé. Les nombres sont ordonnés par <=. Les entiers peuvent être partiellement ordonnés par la relation "divisible par". En généalogie, les personnes sont ordonnées par la relation "A est un ancêtre de B". Ce module introduit formellement les ordres partiels et prouve quelques faits fondamentaux et non triviaux à leur sujet.

Une grande partie des mathématiques discrètes consiste à compter les choses. Un exemple classique consiste à se demander combien de mots différents peuvent être obtenus en réorganisant les lettres du mot Mississippi. Les problèmes de comptage de ce type abondent dans les mathématiques discrètes, les probabilités discrètes et l'analyse des algorithmes.

Le coefficient binomial (n choisir k) compte le nombre de façons de sélectionner k éléments dans un ensemble de taille n. Il apparaît constamment en combinatoire énumérative. Une bonne compréhension de (n choisir k) est également extrêmement utile pour l'analyse des algorithmes.

Les graphes sont sans doute l'objet le plus important des mathématiques discrètes. Un grand nombre de problèmes d'informatique et de combinatoire peuvent être modélisés dans le langage des graphes. Ce module introduit les notions de base de la théorie des graphes - graphes, cycles, chemins, degré, isomorphisme.

Nous poursuivons avec les bases de la théorie des graphes. Dans ce module, nous présentons les arbres, une classe importante de graphes, et plusieurs caractérisations équivalentes des arbres. Enfin, nous présentons un algorithme efficace pour détecter si deux arbres sont isomorphes.

En partant de l'énigme bien connue des "Ponts de Königsberg", nous prouvons la caractérisation bien connue des graphes eulériens. Nous discutons des chemins hamiltoniens et donnons des critères suffisants pour leur existence avec les théorèmes de Dirac et d'Ore.

Nous discutons des arbres couvrants des graphes. En particulier, nous présentons l'algorithme de Kruskal pour trouver l'arbre couvrant minimal d'un graphe avec des coûts d'arêtes. Nous prouvons la formule de Cayley, qui stipule que le graphe complet sur n sommets a n^(n-2) arbres couvrants.

Ce module traite des réseaux de flux et a une saveur algorithmique distincte. Nous prouvons le théorème de dualité du flux maximum et de la coupe minimum.

Nous prouvons le théorème de Hall et le théorème de Kőnig, deux résultats importants sur les appariements dans les graphes bipartis. Avec la machinerie des réseaux de flux, ces deux résultats ont des preuves directes. Enfin, les ordonnancements partiels font leur retour avec le théorème de Dilworth, qui a une preuve surprenante utilisant le théorème de Kőnig.