Graphes

Prologue......Page 3 1.1. Sommets, arêtes......Page 4 1.2. Valence, diamètre......Page 8 1.3. Connectivités......Page 9 1.4. Arbres......Page 10 1.5. Chaînes et cycles......Page 11 1.6. Exercices......Page 13 2.1. Graphe eulérien......Page 16 2.2. Graphe hamiltonien......Page 18 2.3. Problèmes P et NP......Page 19 2.4. Exercices......Page 20 3.1. Le théorème de Ramsey (1930)......Page 22 3.2. Le théorème de Schur (1916)......Page 25 3.3. Les théorèmes de Van der Waerden (1927) et Szemerédi (1975)......Page 27 3.4. Exercices......Page 28 4.1. Matrice d'adjacence......Page 31 4.2. Matrices positives......Page 36 4.3. Laplacien......Page 39 4.4. Exercices......Page 44 Chapitre 5. Graphes planaires......Page 48 5.1. La relation d'Euler......Page 50 5.2. Le théorème de Kuratowski......Page 51 5.3. Exercices......Page 54 Chapitre 6. Trois conjectures et deux théorèmes......Page 55 Liste des figures......Page 1 Index......Page 58