Cette UE abordera les points suivants :
Théorie des graphes
- Notion de graphe. Degré. Chemins, chaînes, cycles. Connexité.
- Graphes eulériens et hamiltoniens. Graphes bipartites.
- Isomorphismes, groupes d’automorphismes.
- Matrice d’adjacence, spectre et propriétés.
- Arbres, formule de Cayley. Arbres couvrants, algorithme de Kruskal.
- Coloriage, nombre chromatique.
- Planarité, formule d’Euler. Théorème des six couleurs.