Mercredi 15/09 : Cours 1
Introduction, définition de graphe, graphe complémentaire, isomorphismes et automorphismes de graphes, graphes complets, bipartis, bipartis complets. Les matrices d'adjacence A(G) et d'incidence M(G).
Mercredi 22/09 : Cours 2 - TD 1
Comment compter les graphes simples sur n sommets; classes d'isomorphisme de graphes, le groupe d'automorphismes et son cardinal. Le degré d'un sommet; somme des degrés, sommets impairs.
Mercredi 29/09 : Cours 3 - TD 2
Cheminement dans les graphes, chaînes simples, élémentaires; comment compter les nombres de chaînes de longueur fixée. Cycles; un graphes qui a tous les sommets de degré au moins égal à 2 contient un cycle.
Mercredi 06/10 : Cours 4 - (TD 3 - Quai 43 s.109)
Caractérisation de graphes bipartis. Suites de degrés et séquences réalisables.
Application : le problème de la plus courte chaîne, l'algorithme de Dijkstra (
un exemple de l'algorithme).
Mercredi 13/10 : Cours 5 - (TD 4 - Quai 43 s.109)
Arbres et forêts, caractérisation des arbres. Arêtes séparatrices
Mercredi 20/10 : Cours 6 - (TD 5 - Quai 43 s.112)
Sommets séparateurs. Arbres recouvrants. Comment calculer le nombre d'arbres recouvrants d'un graphe connexe : formule de récurrence. Formule de Cayley pour les graphes complets.
Mercredi 27/10 : Cours 7 - (TD 6 - Préfa 16 (Préfa TP))
Application : le problème de l'arbre de poids optimal ; algorithme de Jarnik-Prim. Tours eulériens et chaînes eulériennes : caractérisation de graphes eulériens.
Mercredi 03/11 : Le CC2 aura lieu de 14h00 à 15h15 en Salle Thémis 69.
Mercredi 10/11 : Cours 8 - (TD 7 - Préfa 16 (Préfa TP))
Cycles Hamiltoniens : condition nécessaire, une condition suffisante (Théorème de Dirac). Exemples : le graphe de Petersen, le graphe de Herschel, les graphes des solides de Platon. Application : le problème du postier chinois.
Mercredi 17/11 : Cours 9 - (TD 8 - Préfa 16 (Préfa TP))
Langages et expressions rationnelles. Monoïdes, morphismes de monoïdes. Exemples.
Mercredi 24/11 : Pas de cours - (TD 9 le matin 8h15 - 11h30 Préfa 16 (Préfa TP))
Mercredi 01/12 : Cours 10 - (TD 10 - Préfa 16 (Préfa TP))
Cours annulé à cause de la neige.
Mercredi 08/12 : Cours 11 - (TD 11 - Préfa 16 (Préfa TP))
Automates et langages des mots acceptés. Procès de normalisation. Automate avec ε-transitions, passage à un automate sans ε-transitions. Théorème de Kleene.
Mercredi 15/12 : Cours 12 - (TD 12 - Préfa 16 (Préfa TP))
Preuve du Théorème de Kleene. Lemme de Arden et application pour trouver le langage accepté par un automate. Automates déterministes. Processus de détermination.
Mercredi 12/01 : Lemme de l'étoile et langages non rationnels. Restitution CC3.