Programme des séances de THEG en 2018 = programme de révisions.

Séance 1:
- Chemins Eulériens.  Définition.  Condition nécessaire et suffisante.
  Algorithme pour en produire un.
- 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:
- Liste d'adjacence
- Matrice d'adjacence
- Parcours en profondeur (récursif ou non)
- Parcours en largeur
- 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 de compexité en fonction de |E| et |V|

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

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

Séance 5:
- Théorème de Tutte pour l'existence d'un couplage maximum
- Couplage pondéré maximum, chemin améliorant pondéré
- Application au problème du postier chinois

Séance 6:
- connexité, bi-connexité, point d'articulation
- algorithme de recherche des points d'articulation (Hopcroft-Tarjan)
- connexité forte, connexité faible
- algorithme de décomposition en composantes fortement connexes (Tarjan)


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.
- excentricité, rayon, diamètre,
- graphes planaires, faces, graphe dual, théorème de Kuratowski
- graphes cordaux, graphes d'intervales
- flots
- jeux