Programme des séances de THEG en 2019 = programme de révision.

Séance 1:
- Survol rapide de plein de problèmes de graphe.
- Définition d'arbre couvrant.
- Théorème de Kirchhoff pour dénombrer les arbres couvrants.
- Formule de Cayley (il y a n^{n-2} arbres avec sommets numérotés de 1 à n)

Séance 2:
- Notations
- Liste d'adjacence
- Matrice d'adjacence
- Parcours en profondeur
- Parcours en largeur
- Calculs des complexité en fonction de |E| et |V|
- Tri topologique
- Formule de la somme des degrés

Séance 3:
- excentricité, rayon, diamètre,
- Plus courts chemins 1 source sur graphe non pondéré (DistMap)
- Plus courts chemins 1 source sur graphe pondéré >=0 (Dijsktra)
- Plus courts chemins 1 source sur graphe pondéré sans cycles négatif (Bellman-Ford)
- Calculs des complexité en fonction de |E| et |V|

Séance 4:
- Plus courts chemins n source sur graphe pondérés sans cycles négatif
  (3 algos dont Floyd-Warshal)

Séance 5:
- Couplage, couplage maximal, couplage maximum, couplage parfait, chemin améliorant.
- Algo d'Edmonds pour le calcul d'un couplage maximum

Séance 6:
- Couplage pondéré maximum, chemin améliorant pondéré
- Application au problème du postier chinois

Séance 7:
- Calcul de circuit Eulérien
- Résumé du cours


Les sujets qui suivent, présents dans les annales, n'ont pas été
abordés cette année en cours.  Si j'ai besoin d'en parler dans l'exam
cette année, je les définirai.
- graphes planaires, faces, graphe dual, théorème de Kuratowski
- graphes cordaux, graphes d'intervales
- connexité, forte connexité
- flots
- jeux