Programme de révision pour le partiel de THEG
=============================================

Définitions de base : graphe orienté ou non, graphe connexe, arbre,
degré d'un sommet, graphe complet, graphe biparti, cycle, cycle
eulérien, stable, clique, noyau, graphe complémentaire, graphe
planaire, nombre chromatique, rayon, diamètre, excentricité, centre,
maille, sous-graphe induit par un ensemble.

Représentation sous forme de liste d'adjacence ou de matrice
d'adjacence.  Comprendre le sens mathématique de cette matrice
d'adjacence (indice: toute matrice représente une application
linéaire).

Formule de la somme des degrés.

Formule de Cayley (nombre d'arbre de n noeuds).

Savoir faire un parcours en profondeur et un parcours en largeur.

Calcul de distance dans un graphe: savoir quel algo utiliser pour
calculer une distance entre deux points donnés, ou quel algo pour
calculer toutes les distances entre toutes les paires de points.
Revoir la façon de calculer la complexité de ces algos.  (Vous aurez à
calculer la complexité d'algorithmes de graphes dans l'exam.)

[Pas fait en 2017] Réseaux de flot.  Savoir trouver un flot maximal
dans un réseau de flot (avec les algos d'Edmonds-Karp ou de Dinitz).
Savoir appliquer ces méthodes à des flots multi-sources ou
multi-puits, ou avec des contraintes sur les sommets.  Application aux
mariages.

[Pas fait en 2017] Savoir calculer une stratégie gagnante dans un jeu
de Nim (ex. allumettes) dont on a le graphe.

Savoir donner ("à l'oeil") le nombre chromatique de graphes simples.

Théorème des 4 couleurs.

Formule d'Euler (pour les graphes planaires).

Savoir utiliser les critères dérivés de la formule d'Euler pour
montrer qu'un graphe n'est pas planaire.

Théorème de Kuratowski (essayez de trouver K5 ou K3,3 dans quelques
graphes non planaires).

Savoir dire si un graphe est cordal ou non.  Savoir indiquer les
sommets simpliciaux dans un graphe.  Savoir faire un parcours en
largeur lexicographique (LexBFS).  Savoir colorier un graphe cordal.
Savoir justifier qu'un graphe d'intervalles est cordal.

Savoir trouver les arêtes d'un poisson.

===

Une fois que vous maîtrisez tout ce qui précède, vous pouvez vous
"amuser" à refaire quelques démonstrations. Je vous suggère de
commencer par des faciles :

1) Démontrez la formule des alcanes: C(n)H(2n+2).
2) Démontrez la formule d'Euler.

Puis des compliquées :

3) Démontrez que tout graphe cordal possède un sommet simplicial.
4) Démontrez la formule de Cayley (Note: pour une démonstration
   différente de celle présentée en cours, vous pouvez aussi utiliser
   le théorème de Kirchhoff pour calculer le nombre d'arbres couvrant
   d'un graphe complet de n sommets).