Enseignement Graphe (L3 ESR)
- Contenu du cours
Le but du cours est de faire découvrir des thechniques d'analyse combinatoire à travers l'étude des graphes. On abordera les points suivants:
- Première notion de graphe: modélisation, représentation, isomorphisme, degré
- Problèmes de chemins dans un graphe: Notion de chemin, connexité, chemin Eulérien et Hamiltoniens
- Graphes acycliques: Arbres, arbre orientés, rang topologique dans un graphe orienté sans circuit, introduction à la théorie des jeux, parcours en largeur et en longueur dans un graphe
- Problèmes de coloriages: coloriages de sommets, coloriages de sommets
- Graphes planaires: formules d’Euler, théorème de Kuratowski, Coloration, Croisement, épaisseur et genre
- Théorie de Ramsey
- Théorie algébrique des graphes
- Problème d’optimisation pour les graphes valués: recherche d’arbre couvrant de pois maximal, recherche de plus court chemin
- Notes de cours: [PDF]
- Feuille de TD:
- TD1: Premières notions sur les graphes [PDF]
- TD2: Chemins et Cycles [PDF]
- TD3: Arbres [PDF]
- TD4: Jeux [PDF]
- TD5: Coloriages [PDF]
- TD6: Graphes planaires [PDF]
- TD7: Théorie algébrique [PDF]
- Ouvrages de référence
- Graph Theory and applications, Jean-Claude Fournier
- Graphes et Combinatoire, Francette Bories-Longuet et Jorge Ramirez-Alfonsin
- Eléments de théorie des graphes, Alain Bretto, Alain Faisant et François Hennecart.