Initiation à la théorie des graphes

Couverture
Page de titre
Chapitre 1 : généralités
1.1 Premières définitions
1.2 Exemples concrets
1.3 Ordre ; degré
Première pause
1.4 Chaîne; cycle
1.5 Sous-graphe ; graphe complet, connexe; sous-graphe stable
Deuxième pause
1.6 Distance; diamètre
1.7 Graphe orienté
Troisième pause
1.8 Graphes particuliers
Graphe biparti
Arbre
Graphe planaire
Graphe probabiliste
Dernière pause
Solutions des « pauses »
Exercices :
Graphes non orientés
Graphes orientés
Chapitre 2 : graphes et chemins
2.1 Introduction
2.2 Graphe eulérien
2.2.1 De quoi s'agit-il ?
2.2.2 A quelle condition un graphe admet-il une chaîne eulérienne ? (ou un cycle eulérien)
2.2.3 Comment trouver une chaîne eulérienne ?
Première pause
2.3 Graphe hamiltonien
2.3.1 De quoi s'agit-il ?
2.3.2 A quelle condition un graphe admet-il une chaîne hamiltonienne ? (ou un cycle hamiltonien)
2.3.3 Comment trouver une chaîne hamiltonienne ?
Deuxième pause
2.4 Et si le graphe est orienté ?
Dernière pause
Solutions des « pauses »
Exercices
Et le bac ?
Chapitre 3 : graphes et couleurs
3.1 Introduction
3.2 Coloration d'un graphe
3.2.1 De quoi s'agit-il ?
3.2.2 Comment faire?
Première pause
3.2.3 A quoi cela sert-il ?
3.3 Nombre chromatique
Deuxième pause
3.4 Utilisation
Solutions des « pauses »
Exercices
Et le bac ?
Chapitre 4 : graphes et matrices
4.1 Rappels sur les matrices
Première pause
4.2 Matrice associée à un graphe non orienté
Deuxième pause
4.3 Matrice associée à un graphe orienté
Troisième pause
4.4 Utilisation des matrices
Dernière pause
Solutions des « pauses »
Exercices
Et le bac ?
Chapitre 5 : graphes valués
5.1 Définitions
Première pause
5.2 Recherche du plus court « trajet »
Deuxième pause
5.3 Quelques remarques sur des cas particuliers
Solutions des « pauses »
Exercices
Et le bac ?
Chapitre 6 : graphes et probabilités
6.1 De quoi s'agit-il ?
Première pause
6.2 Utilisation
Deuxième pause
6.3 Etat probabiliste
6.4 Etat probabiliste à la n ième étape
Troisième pause
6.5 Etat stable
6.5.1 Définition
6.5.2 Recherche d'un état stable
Quatrième pause
6.6 Graphe probabiliste et suite géométrique
6.6.1 Rappels
6.6.2 Quel rapport avec les graphes probabilistes ?
Solutions des « pauses »
Exercices
Et le bac ?
Chapitre 7 : graphes étiquetés - Automates
7.1 Graphe étiqueté
7.2 Automate fini
Première - et seule - pause
Solution de la « pause »
Exercices
Et le bac ?
Compléments
Rappel des principales notions
Algorithme
Pour terminer.. .et réviser (exercices de bac corrigés)
Brèves notices historiques
Logiciels pour graphes
Sites Internet et graphes
Programme TES spécialité (graphes)
Algorithme « gourmand »
Index