Cours : 8 séances de 2h

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é
    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. Représentations
      1. Matrice d'adjacence
      2. Matrice d'incidence
      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. Notions asymptotiques
          1. Grand O, Oméga, Thêta

          Cours#2
        2. Existence d'une arête ou d'un arc entre deux sommets
        3. Degré d'un sommet
        4. Degré de tous les sommets
  3. 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
    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
      3. Complexité
      4. Version "longue"
    8. Graphe PERT
      1. Date au plus tôt, date au plus tard
    9. Ford (détection d'un circuit absorbant)
      1. Principe
      2. Algorithme
      3. Complexité
      4. Exemple

      Cours #3
    10. Plus court chemin entre toutes paires de sommets
      1. Complexité avec Dijkstra
      2. Calcul matriciel
        1. Principe
        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é
  4. Parcours

    1. Parcours en largeur
      1. Principe : utilisation d'une file et exemple de parcours sur un graphe non orienté
        Cours #5
      2. Algorithme
      3. Exemples
      4. Complexité
      5. Validité (jusqu'à : pour tout sommet v de V(G), d(v) ≥ dG(s,v))
      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éCouleur des sommets lors du parcours d'un arc en fonction de sa classe
      7. Théorème des parenthèses
      8. Théorème du chemin blanc
        Cours #6
    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
        3. Algorithme
        4. Validité de l'algorithme (voir sujet Examen 2011/2012 - session 1 exercice 4)
  5. Arbres couvrants de poids minimum

    1. Définition : graphe partiel
    2. Théorème : tout arbre ayant au moins deux sommets possède au moins deux sommets de degré 1

      Cours #7

    3. Caractérisation des arbres
    4. Cycle fondamental
    5. Algorithme de Kruskal
      1. Principe
      2. Exemple
      3. Énoncé
      4. Complexité
      5. Validité (non traitée)
    6. Algorithme de Prim
      1. Principe
      2. Exemple
      3. Énoncé
      4. Complexité
      5. Validité (non traitée)

        Cours #8

  6. Flots

      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
    1. Programme linéaire associé
    2. Recherche d'une chaîne améliorante
      1. Marquage direct
      2. Marquage indirect
      3. Algorithme de Ford et Fulkerson
      4. Exemple
      5. Problématique
        1. Notion de coupe
        2. Théorème "Flot max / Coupe min"
      6. Application : Recherche d'un couplage maximum dans un graphe biparti
      7. Applications (suite)
        1. Problème du flot canalisé (voir sujet Examen 2011/2012 - session 2 exercice 3)
        2. Arête-connectivité
    3. Coupe minimum