Voici les points abordés en cours, qui peuvent vous servir de
programme de révision pour l'examen de THEG 2020.  L'examen sera un
QCM sans document autorisé, et ne couvrira évidemment pas TOUS ces
points.

- 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)

- Notations
- Liste d'adjacence
- Matrice d'adjacence
- Calculs des complexité en fonction de |E| et |V|
- Formule de la somme des degrés
- connexité, forte connexité

- Parcours en profondeur
- Parcours en largeur
- Tri topologique

- Calcul de circuit Eulérien

- 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|

- Plus courts chemins n source sur graphe pondérés sans cycles négatifs
- Bases de théorie des groupes pour l'interprétation des matrices d'adjacence et de leurs puissances

- Couplage, couplage maximal, couplage maximum, couplage parfait, chemin améliorant
- Algo d'Edmonds pour le calcul d'un couplage maximum


Playlist des vidéos produites pendant le confinement, n'incluant pas
les premier cours (qui avaient lieux en amphi):

https://www.youtube.com/playlist?list=PLONCQ4-S78TkaQSW3srqyrX5QN_omA0x3


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
- flots
- jeux