Module Math3-Alg3-1 : Combinatoires, arithmétiques et graphes
Table of Contents
1 Prérequis
Module Math1-Bases3 et Math3-Alg3
2 Objectif d'apprentissage
Le but du cours est de faire un tour d’horizon de différentes méthodes combinatoires autour de deux grands thèmes, la théorie des graphes et la théorie des nombres.
3 Descriptions des enseignements
3.1 Combinatoire
- Principe de combinatoire: preuves par bijections, principes des bergers, double comptage (application aux égalités entre coeffcients binomiaux), principe des tiroirs, principe d’inclusion-exclusion (application au comptage de surjections)
- Utilisation des séries génératrices pour déterminer un cardinal
3.2 Graphe:
- Notions de base sur des graphes: graphe orienté, non orienté, isomorphisme, degré, lemme de la poignée de main, différents types de représentation.
- Problèmes de chemins dans un graphe: longueur d’un chemin à partir de la matrice d’adjacence, connexité, k-connexité, chemin eulerien, chemin hamiltonien.
- Arbres: différentes caractérisation des arbres, arbre orienté, notion de rang dans un graphe orienté sans circuit.
- Coloration: coloration de sommet, nombre chromatique, notion de stable et de clique, polynôme chromatique, coloration d’arêtes, indice chromatique, Théorème de Vizing.
- Planarité: graphe planaire, formule d’Euler et applications, coloration de graphe planaire, Théorème de Kuratowski (peut être admis).
- Initiation à la méthode probabiliste à travers divers exemples.
3.3 Autres thèmes qui peuvent être abordés dans les graphes:
- Initiation à la théorie de Ramsey.
- Couplage : notion de couplage, couplage dans les graphe bipartis (théorème de Hall), couplage stable, Algorithme de Gale-Shapley, théorème de Tutte.
- Problèmes d’optimisation pour les graphes valués: recherche d’arbre couvrant de pois maximal (algorithmes de Prim et Kruskal), recherche de plus court chemin (algorithmes de Bellman-Ford-Kalaba et Dijkstra-Moore), problème de flots dans les transports (algorithme de Ford-Fulkerson).
4 Références
- Éléments de théorie des graphes Alain Bretto, Alain Faisant, François Hennecart
- Graph Theory and application Jean Claude Fournier
- Théorie des Graphes J.A. Bondy et U.S.R. Murty
- Théorie Des Nombres. Daniel Duverney
- Introduction à la théorie des nombres Jean-Marie De Koninck Armel Mercier