Module Math3-Alg3 : Combinatoires, arithmétiques et graphes
Table of Contents
1 Prérequis
Module Math1-Bases3 et Math3-Alg1
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).
3.4 Théorie des nombres
- Nombres premiers: arithmétique élémentaire, décomposition en nombres premiers, crible, quelques idées sur la distribution des nombres premiers (théorème d’Euclide, inégalités de Tchebychev, exemple de suite arithmétique contenant une infinité de nombre premier).
- Equations diophantiennes: équation du type ax+by=c, triplets pythagoriciens, méthode de descente infini, entiers comme somme de quatre carrés.
- Fonctions arithmétiques: fonctions arithmétiques élémentaires, convolution de Dirichlet et inversion de Moebius et applications au calcul de la fonction d’Euler.
- Approximation diophantienne: théorème de Dirichlet, mesure d'irrationalité, théorème de Liouville, exemples de nombres transcendants
- Fractions continues
- Résidus quadratiques: Symbole de Legendre. Loi de réciprocité quadratique.
3.5 Autres thèmes qui peuvent être abordés en théorie des nombres:
- Notion sur la théorie des partitions: fonctions génératrices, comportement asymptotique du nombre de partitions
- Série de Dirichlet et applications aux développements asymptotiques élémentaires de fonctions arithmétiques
- Formes quadratiques entières: Représentabilité d'un entier par une forme quadratique. Classes d'équivalence. Réduction.
- Géométrie des nombres: convexes et réseaux, théorèmes de Minkowski.
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