Quelques résultats classiques concernant les graphes orientés
M2 Informatique, M2 Maths-Info.
Partie de FMIN339
Ce cours est partagé avec P.Ochem
Contenu de cette partie:
Le cours porte sur des résultats / conjectures classiques concernant
les graphes orientés. Le programme est approximativement le suivant:
- Cours 1: Chemins :
Théorème de Gallai-Milgram, Théorème de Menger, 'linkage',
Branchings Theorem d'Edmonds.
- Cours 2: Cycles :
Composantes fortement connexes, Décomposition en oreilles,
'Feedback arc/vertex set', couverture par cycles.
La Fiche d'exercices:
Exercices
Bibliographie:
- J Bang-Jensen, G. Gutin: Digraphs, theory, algo, applications
(une version en ligne:
www.tud.ttu.ee/material/enn/GraphTheory/main.pdf )
- J.A Bondy, U.S Murty, Graph theory (pas de version en ligne)
- le jardin de conjectures: http://garden.irmacs.sfu.ca/?q=category/graph_theory
- Si vous avez encore faim: http://lemon.cs.elte.hu/egres/open/Main_Page