Cours : 12 séances d'1h20
Cours #1

  1. Généralités

    1. Rappels historiques : ponts de Königsberg, graphe eulérien, problème des 4 couleurs
    2. Définitions sur les graphes non orientés
      1. Sommets, arêtes
      2. Arête multiple, boucle, graphe simple
      3. Degré
      4. Relations adjacence (sommets, arêtes) et incidence
      5. Voisin
      6. Ordre, taille
      7. Notation V(G), E(G), n, m, deg(v)
    3. Définitions sur les graphes orientés
      1. Ensembles de sommets et d'arcs
      2. Arcs entrant et sortant
      3. Prédécesseur, successeur
      4. Degrés entrant et sortant
    4. Définitions sur les graphes étiquetés et non étiquetés
      1. Notion d'égalité sur les graphes étiquetés
      2. Isomorphisme de graphes
    5. Cheminement
      1. Chaîne, chaîne simple, chaîne élémentaire, cycle
      2. Chemin, circuit, circuit élémentaire
    6. Théorèmes
      1. Le nombre maximum d'arêtes dans un graphe simple est égal à n*(n-1)/2
      2. La somme des degrés d'un graphe non orienté est paire et égale à deux fois le nombre d'arêtes
      3. Le nombre de sommets de degré impair dans un graphe non orienté est pair
      4. Dans un graphe orienté, la somme des degrés entrants est égale à la somme des degrés sortants et au nombre d'arcs
      5. Dans tout graphe simple ayant au moins deux sommets, il existe deux sommets de même degré
        Cours #2
    7. Sous-graphes
      1. Sous-graphes induits
      2. Graphes partiels
    8. Connexité
      1. Graphes connexes
      2. Graphes fortement connexes
      3. Composantes connexes et fortement connexe
      4. Connectivité

  2. Structures de données et complexité

    1. Notions asymptotiques
      1. Grand O, Oméga, Thêta
    2. Représentations
      1. Matrice d'adjacence
      2. Matrice d'incidence
        Cours #3
      3. Listes d'adjacence
      4. Ensembles de voisinage (tables de hachage)
      5. Taille mémoire selon la représentation
      6. Complexité selon la représentation
        1. Existence d'une arête ou d'un arc entre deux sommets
        2. Degré d'un sommet
        3. Degré de tous les sommets

  3. Parcours

    1. Parcours en largeur
      1. Principe : utilisation d'une file et exemple de parcours sur un graphe non orienté
      2. Algorithme
      3. Exemples
      4. Complexité
      5. Validité (jusqu'à : pour tout sommet v de V(G), d(v) ≥ dG(s,v))
        Cours #4
      6. Validité (suite et fin)
    2. Parcours en profondeur
      1. Principe: utilisation d'une pile et exemple de parcours sur un graphe non orienté
      2. Énoncé de l'algorithme
      3. Exemple sur un graphe orienté
      4. Complexité
      5. Classification des arcs
      6. Classes des arcs dans le parcours en profondeur d'un graphe non orienté
      7. Cours #5
      8. Couleur des sommets lors du parcours d'un arc en fonction de sa classe
      9. Théorème des parenthèses
      10. Théorème du chemin blanc
    3. Applications du parcours en profondeur
      1. Tri topologique
        1. Principe
        2. Exemple
        3. Algorithme
        4. Théorème: tout graphe admet un tri topologique ssi il est sans circuit
        5. Validité de l'algorithme
      2. Composantes fortement connexes
        1. Définition
        2. Exemple
          Cours #6
        3. Algorithme
        4. Validité de l'algorithme (voir sujet Examen 2011/2012 - session 1 exercice 4)
          Cours #7

  4. Arbres couvrants de poids minimum

    1. Définition : graphe partiel
    2. Caractérisation des arbres (rappel du TD1)
    3. Cycle fondamental
    4. Algorithme de Kruskal
      1. Principe
      2. Exemple
      3. Énoncé
      4. Complexité
      5. Validité
    5. Algorithme de Prim
      1. Principe
      2. Exemple
      3. Énoncé
      4. Complexité
      5. Validité

  5. Plus courts chemins

    1. Problématique
      1. Entre deux sommets
      2. Entre un sommet v et tous les autres
      3. Entre tous les sommets
    2. Existence
      Cours #8
    3. Arborescence
    4. Principe du relâchement
    5. Principes des algorithmes de Dijkstra (fonction de poids positive) et Bellman (graphe sans circuit)
    6. Dijkstra
      1. Algorithme
      2. Exemple
      3. Complexité avec file de priorité
      4. Validité
    7. Bellman
      1. Algorithme à partir d'un ordre topologique
      2. Exemple
        Cours #9
      3. Complexité
      4. Version "longue"
    8. Ford (détection d'un circuit absorbant)
      1. Principe
      2. Algorithme
      3. Complexité
      4. Exemple
    9. Plus court chemin entre toutes paires de sommets
      1. Complexité avec Dijkstra
      2. Calcul matriciel
        1. Principe
          Cours #10 et 11
        2. Algorithme
        3. Exemple
        4. Complexité
        5. Version accélérée
      3. Floyd
        1. Principe
        2. Algorithme
        3. Complexité
        4. Exemple
        5. Fin de l'exemple
        6. Application à la fermeture transitive
          1. Définition
          2. Algorithme de Warshall
      4. Algorithme de Johnson (non traité)
        1. Principe
        2. Graphe (G', w', s)
        3. Algorithme
        4. Complexité

  6. Flots

    1. Problématique
      1. Notion de réseau : graphe orienté, source, puits, capacité
      2. Notion de flot : loi de Kirchhoff, arc retour
      3. Problème du flot maximum
    2. Programme linéaire associé
    3. Recherche d'une chaîne améliorante
      1. Marquage direct
      2. Marquage indirect
      3. Algorithme de Ford et Fulkerson
      4. Exemple
        Cours #12
    4. Coupe minimum
      1. Notion de coupe
      2. Théorème "Flot max / Coupe min"
    5. Application : Recherche d'un couplage maximum dans un graphe biparti
    6. Applications (suite)
      1. Problème du flot canalisé (voir sujet Examen 2011/2012 - session 2 exercice 3)
      2. Arête-connectivité