Réseau Graphes P. Fonctionnelle P. Logique Complexité

L3

Ressources utiles (Hum, ça va ?)

• À la découverte des algorithmes de graphes
• Théorie des graphes : Fondements
• Sujet d'examen 2014-2015
• Sujet deuxième session 2013-2014
• TPs de structure de données de l'année dernière (si ça peut être utile):
  • TP n°1
  • TP n°2
  • TP n°3

Explications de bases

Vocabulaire

Un graphe est non orienté quand les sommets sont reliés entre eux par de simples traits (des arcs).

• Tous les noeuds reliés à un sommet sont appelés ses voisins.
• Le degrés (noté d(a) pour le sommet a) d'un sommet correspond à son nombre de voisins. *

Un graphe est orienté lorsque les sommets sont reliés entre eux par des flèches (des arêtes).

• Tous les noeuds incident (arrivant dessus) à un même noeud consituent ses prédécesseurs.
• Tous les noeuds reliés à un autre noeud par le biais d'une arête constituent ses successeurs.
• Le nombre de prédécesseurs d'un noeud correspond à son degrès entrant (noté d-(a) pour le sommet a) et le nombre de successeurs correspond à son degrés sortant (noté d+(a) pour le sommet a).

Matrice et liste d'adjacence

Par exemple, pour le graphe:

                +-----+                    +-----+
                |  1  |------------------->|  2  |
                +-----+                    +-----+
                   |
                   |
                   |
                   v
                +-----+
                |  3  |
                +-----+

La matrice d'adjacence correspondante est (la première ligne est le point de départ):

          +---+-----------+
          |   | 1 | 2 | 3 |
          |---|-----------|
          | 1 | 0 | 0 | 0 |
          | 2 | 1 | 0 | 0 |
          | 3 | 1 | 0 | 0 |
          +---+-----------+

          +---+-----------+
          |   | 1 | 2 | 3 |
          |---|-----------|
          | 1 | 0 | 1 | 1 |
          | 2 | 1 | 0 | 0 |
          | 3 | 1 | 0 | 0 |
          +---+-----------+

Et la liste d'adjacence correspondante est:

    +-----+   _____    _____
    |  1  |->|  2  |->|  3  |->Nil
    +-----+   -----    -----
    |  2  |-> Nil
    +-----+
    |  3  |-> Nil
    +-----+

    +-----+   _____    _____
    |  1  |->|  2  |->|  3  |->Nil
    +-----+   -----    -----
    |  2  |->|  1  |->Nil
    +-----+   -----
    |  3  |->|  1  |->Nil
    +-----+   -----

Algorithmes utiles

Coloration: Pour représenter le parcours, l'algorithme utilise la coloration avec la convention:

• Blanc: Le sommet x n'est pas visité.
• Gris: Le sommet x est visité pour la première fois ou bien un de ses voisins n'est pas visité.
• Noir: Sommet et voisins visités.

Parcours en Largeur (PeL)

procédure PeL(Entrée: G = <S, A> : Graphe)
  var p, d
début
  // p et d sont des tableaux et stockent la liste
  // des prédécesseurs de x et la date à laquelle x
  // a été traité.
  pour x dans S faire
    c(x) = Blanc
    p(x) = Nil
    d(x) = +∞
  fin

  // c(x) représente la couleur de x
  d(S) = 0
  c(S) = Gris
  F    = {S}

  tant que F != Ø faire
    x = tete(F)

    pour y dans Adj(x) faire
      si c(y) = Blanc alors
        p(y) = x
        d(y) = d(x) + 1
        c(y) = Gris
        Enfiler(F, y)
      fin
    fin

    c(x) = Noir
    Defiler(F)
  fin tant que
fin

Parcours en Profondeur (PeP)

procédure PeP(Entrée: G = <S, A> : Graphe)
  var p, d, f
début
  pour x dans S faire
    p(x) = Nil
    c(x) = Blanc
  fin

  temps = 0; // Variable globale

  pour x dans S faire
    si c(x) = Blanc alors
      visiter(x);
    fin
  fin
fin

procédure visiter(Entrée: S : Sommet)
début
  c(x) = Gris
  temps = temps + 1;
  d(x) = temps

  pour y dans Adj(x) faire
    si c(y) = Blanc alots
      p(y) = x
      visiter(y)
    fin
  fin

  c(x) = Noir
  temps = temps + 1;
  f(x) = temps
fin