Graphes et combinatoire

Couverture
Page de titre
GRAPHES
1 GÉNÉRALITÉS
	1.1 Définitions
	1.2 Degrés
	1.3 Graphes réguliers
	1.4 Colorations
	Exercices
2 CYCLES, CONNEXITÉ ET ARBRES
	2.1 Chaînes et cycles
	2. 2 Connexité
	2.3 k-connexité et k-arête-connexité
	2.4 Arbres
	2.5 Espaces des cycles et des co cycles
	Exercices
3 GRAPHES HAMILTONIENS ET EULÉRIENS
	3.1 Graphes hamiltoniens
	3.2 Le cercle des irascibles
	3.3 Graphes eulériens
	3.4 Graphes orientés
	3.5 Racines et puits
	3.6 Graphes conservatifs
	3.7 Tournois
	Exercices
4 COUPLAGES ET FACTORISATIONS
	4.1 Couplages
	4.2 Transversalité
	4.3 Couplages stables
	4.4 Un résultat de Dilworth
	4.5 Factorisations
	4.6 Étiquetages gracieux
	Exercices
5 GRAPHES PLANAIRES
	5.1 Généralités
	5.2 Formule d'Euler
	5.3 Graphe dual
	5.4 Polyèdres réguliers
	5.5 Le problème des quatre couleurs
	5.6 Nombre de croisements
	Exercices
6 THÉORIE DE RAMSEY
	6.1 Principe des tiroirs : base
	6.2 Théorème de Ramsey
	6.3 Théorie de Ramsey pour les graphes
	6.4 Résultat de Schur
	Exercices
COMBINATOIRE
7 ENSEMBLES
	7.1 Notions générales
	7.2 Relations binaires
	7.3 Principe de récurrence (ou d'induction)
	7.4 Nombres de Stirling
	Exercices
8 APPLICATIONS ET ÉNUMÉRATION
	8.1 Applications, injections, surjections, bijections
	8.2 Cardinal d'un ensemble
	8.3 Principe des tiroirs
	8.4 Ensembles dénombrables
	8.5 Dénombrement des ensembles finis
	8.6 Principe de Fubini
	Exercices
9 NOMBRES BINOMIAUX ET MULTINOMIAUX
	9.1 Les nombres binomiaux
	9.2 Multi-ensembles
	9.3 Nombres de Bell
	9.4 Coefficient du binôme généralisé
	9.5 Les nombres multinomiaux
	Exercices
10 FORMULES D'INVERSION
	10.1 Le principe d'inclusion-exclusion
	10.2 Applications
	10.3 Fonction de Möbius
	10.4 Formule de Rota
	Exercices
11 FONCTIONS GÉNÉRATRICES
	11.1 Introduction
	11.2 Opérations
	11.3 Suite de Fibonacci
	11.4 Dénombrement (sans répétition)
	11.5 Règle de convolution
	11.6 Dénombrement (avec répétitions)
	11.7 Nombres de Catalan
	Exercices
12 FORMULES DE BURNSIDE-POLYA
	12.1 Permutations
	12.2 Groupes de permutations
	12.3 Formule de Burnside
	12.4 Formule de P6lya
	Exercices
SOLUTIONS
	Solutions des exercices du Chapitre 1
	Solutions des exercices du Chapitre 2
	Solutions des exercices du Chapitre 3
	Solutions des exercices du Chapitre 4
	Solutions des exercices du Chapitre 5
	Solutions des exercices du Chapitre 6
	Solutions des exercices du Chapitre 7
	Solutions des exercices du Chapitre 8
	Solutions des exercices du Chapitre 9
	Solutions des exercices du Chapitre 10
	Solutions des exercices du Chapitre 11
	Solutions des exercices du Chapitre 12
Bibliographie
Index