Introduction à la théorie des graphes : butinage graphique

Auteur(s) :

Mény, Jean-Manuel Découvrir l'auteur

Résumé

Ouvrage construit comme une suite de situations dans lesquelles la théorie des graphes est un bon outil de modélisation et de résolution. L'objectif est de permettre la découverte progressive des divers aspects de la théorie par le biais de problèmes et de leurs résolutions.

Autre(s) auteur(s)
- Aldon, Gilles (1953-....)
- Xavier, Lionel
Éditeur(s)
- SCÉRÉN
- CRDP, Académie de Lyon
Date
- DL 2005
Notes
- Bibliogr. p. 217-218. Glossaire
Langues
- Français
Description matérielle
- 1 vol. (V-218 p.) : ill., couv. ill. ; 24 cm
Sujet(s)
Lieu
- France
ISBN
- 2-86625-313-2
Indice
- 511.5 Théorie des graphes
Quatrième de couverture
- La théorie des graphes voit actuellement son champs d'application s'élargir du fait de son utilisation dans la résolution de problèmes économiques, informatiques, etc. Ce n'est donc pas un hasard si elle fait son apparition dans l'enseignement des mathématiques.
  Cependant, peu nombreux sont les professeurs de mathématiques aujourd'hui en fonction qui ont pu suivre des cours la concernant.
  C'est pourquoi les ouvrages de référence sont utiles et pour les enseignants des filières concernées et pour les professeurs désireux d'actualiser leurs connaissances.
  Le présent ouvrage est construit comme une suite de situations dans lesquelles la théorie des graphes est un bon outil de modélisation et de résolution. L'objectif est de permettre la découverte progressive des divers aspects de la théorie par le biais de problèmes et de leurs résolutions. Pour les enseignants, il constituera en outre une banque de problèmes et de situations nombreuses et variées.
Tables des matières
- - Introduction à la théorie des graphes
  - Butinage graphique
  - Jean-Manuel Mény
  - Gilles Aldon
  - Lionel Xavier
  - scerén
  - 1 Des graphes sans le vocabulaire des graphes 1
  - 1.1 Un exemple orienté1
  - 1.2 Un exemple non orienté
    6
  - 2 Quelques définitions 9
  - 2.1 Graphe (non orienté)9
  - 2.2 Graphe orienté
    12
  - 3 Degrés et nombre d'arêtes 14
  - 3.1 Lemme des poignées de mains14
  - 3.2 Dans un graphe complet16
  - 3.3 Les sommets impairs18
  - 3.4 Suite graphique22
  - 3.5 Lemme des coups de pied au c...25
  - 3.6 Graphe biparti
    26
  - 4 Chaînes, connexité... 28
  - 4.1 Vocabulaire28
  - 4.2 Chaînes, connexité et sommets impairs
    31
  - 5 Graphes eulériens 37
  - 5.1 Eulérien37
  - 5.2 Pair37
  - 5.3 Parité dans une chaîne37
  - 5.4 CN pour un graphe eulérien39
  - 5.5 CS pour un graphe eulérien40
  - 5.6 Construire un cycle eulérien42
  - 5.7 Promenade à la façon Königsberg45
  - 5.8 Ajout ou suppression d'arêtes49
  - 5.9 Décomposition en cycles élémentaires55
  - 5.10 Le musée56
  - 5.11 Graphes orientés eulériens
    59
  - 6 Matrices d'adjacence 64
  - 6.1 Définition d'une matrice d'adjacence64
  - 6.2 Quelques exercices65
  - 6.3 Carré de la matrice d'adjacence69
  - 6.4 Puissances de la matrice d'adjacence75
  - 6.5 Version matricielle de quelques propriétés
    81
  - 7 Introduction aux chaînes de Markov 85
  - 7.1 Graphe probabiliste85
  - 7.2 Chaîne de Markov86
  - 7.3 Puissances de la matrice de transition87
  - 7.4 Cas particulier d'une matrice de transition 2 x 289
  - 7.5 Retour en Oz91
  - 7.6 Cheminement aléatoire sur une droite93
  - 7.7 Pile ou face94
  - 7.8 Programmes de lycée
    96
  - 8 Coloration 99
  - 8.1 Définitions, encadrements99
  - 8.2 Incompatibilités104
  - 8.3 Coloration d'une carte110
  - 8.4 Algorithme de coloration
    112
  - 9 Les arbres 115
  - 9.1 Définitions115
  - 9.2 Feuille118
  - 9.3 Nombre d'arêtes120
  - 9.4 Connexe minimal120
  - 9.5 Arbre couvrant126
  - 9.6 Centre130
  - 9.7 Hooligans132
  - 9.8 Permutations
    132
  - 10 Graphes planaires 135
  - 10.1 Définition135
  - 10.2 Le théorème de Jordan135
  - 10.3 Dual d'un graphe planaire136
  - 10.4 La formule d'Euler pour les graphes planaires137
  - 10.5 Nombre minimum de croisements144
  - 10.6 Théorème des quatre couleurs147
  - 10.7 Graphes planaires hamiltoniens
    153
  - 11 Initiation aux jeux de Nim 158
  - 11.1 Jeu sur un graphe orienté158
  - 11.2 Noyau159
  - 11.3 Noyaux et mariages stables165
  - 11.4 Noyau et stratégie de jeu166
  - 11.5 La course à vingt167
  - 11.6 Jeu des rectangles entiers171
  - 11.7 Jeu des premiers171
  - 11.8 Coincez la reine174
  - 11.9 Fonction de Grundy176
  - 11.10 Course à vingt avec pas interdit177
  - 11.11 Fan Tan à deux tas178
  - 11.12 Somme digitale180
  - 11.13 Multijeux184
  - 11.14 Fonction de Grundy sur un graphe somme185
  - 11.15 Fan Tan185
  - 11.16 Jeu des étrangers187
  - 11.17 Jeu de Prim190
  - 11.18 Jeux des diviseurs194
  - 11.19 Théorème de Grundy (1939)200
  - 11.20 La multiplication des pains
    201
  - 12 Permutations et dérangements 205
  - 12.1 Définitions205
  - 12.2 Passage de P_n à P_n+1206
  - 12.3 Phi^-1 (D_n+1)207
  - 12.4 Récurrence sur le nombre de dérangements208
  - 12.5 Quelques calculs sur d_n208
  - 12.6 Une application classique209
  - 12.7 k boucles
    209
  - A Petit lexique
    211
  - B Quelques notations 216
Origine de la notice:
- BNF