PC 7
Graphes

1.

représentations

2.

matrice d'adjacence

3.

fermeture transitive

4.

exploration

5.

plus court chemin

Introduction

Un graphe (S,F) est donné par

• Un ensemble S de sommets
• Un ensemble $F\subset S\times S$ de flèches (ou arcs).

Un chemin dans G est une suite

$$(s_0,s_1),(s_1,s_2),\ldots ,(s_{n-1},s_n)$$

Variantes:

• On a aussi en général des étiquettes sur les flèches ou sur les sommets.
• Graphes non orientés.
• Graphes représentés ( dans le plan par ex.)
• Multigraphes.

Exemples de graphes

Les graphes se rencontrent comme:

1.

Modèle de liaisons spatiales: réseaux de transport, électriques, ...

2.

Représentations de liens logiques: graphes de dépendance.

3.

Modèles de l'évolution temporelle: les sommets sont des états d'un système.

4.

Schémas de programmes: les sommets sont les instructions.

Exemples

 

Figure 1: dodecaèdre

 

Figure 2: canal contraint

Représentation des graphes

1.

Matrice d'adjacence:

$$A_{ij}=\left\{\begin{array}{ll}1 & \mbox{si $(i,j)\in F$ }\\ 0 & \mbox{sinon} \end{array}\right.$$

Les éléments peuvent être des booléens ou des entiers.

2.

Liste de successeurs: On donne pour chaque sommet la liste de ses successeurs:

$$L(s)=\{t\in S \mid (s,t)\in S\}$$

3.

Matrice d'incidence: On donne pour chaque flèche son origine et son extremité:

$$I_{if}=\left\{\begin{array}{ll} 1& \mbox{si $f=(i,.)$ }\\ ... ...mbox{si $f= (.,i)$ } \\ 0 & \mbox{sinon} \end{array}\right.$$

Exemple

 

Figure 3:

$$A=\left[\begin{array}{ccccc} 0&1&0&0&0\\ 0&0&0&1&1\\ 1&0&0&0&0\\ 1&0&1&0&1\\ 0&0&0&0&0\\ \end{array}\right]$$

Fermeture transitive

On se donne un graphe G=(S,F) par sa matrice d'adjacence A.

On veut calculer la fermeture transitive de G, i.e. le graphe G^*=(S,F^*) défini par $(s,t)\in F^*$ ssi

$$\mbox{il existe un chemin de $s$\space \\lq a $t$\space dans $G$ }$$

Propriété fondamentale de la matrice d'adjacence:

$$\begin{tabular}{\vert c\vert} \hline $A^k_{ij}$ =\mbox{nb de ... ... de longueur $k$ de $i$\space \\lq a $j$ }\\ \hline \end{tabular}$$

ou en booléens

$$\begin{tabular}{\vert cc\vert} \hline $A^k_{ij}=true \Leftrig... ...ace }\\ &\mbox{de $i$\space \\lq a $j$ }\\ \hline \end{tabular}$$

Formule donnant la matrice d'adjacence A^* de G^*( en booléens):

$$A^*=I+A+A^2+\ldots +A^{n-1}$$

puisqu'un chemin de i à j peut être choisi de longueur au plus n-1.

$\Rightarrow$ Algorithme naïf en O(n⁴).

Exemple

Si

$$A=\left[\begin{array}{ccccc} 0&1&0&0&0\\ 0&0&0&1&1\\ 1&0&0&0&0\\ 1&0&1&0&1\\ 0&0&0&0&0\\ \end{array}\right]$$

Alors

$$A^*=\left[ \begin{array}{ccccc} 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 0&0&0&0&1 \end{array}\right]$$

class Matrice {
  int[][] m; //matrice carree
  int n; //la dimension de m

  Matrice(int x) {
    n=x;
    m=new int[n][n];
  }
}

L'algorithme de Warshall

Idée: au lieu de faire porter la récurrence sur la longueur du chemin, on peut la faire porter sur le nombre de sommets utilisés. Posons:

$$A^{(k)}_{ij}=\left\{\begin{array}{cc} 1 & \mbox{ s'il existe... ...pace entre temps}\\ 0 & \mbox{sinon}\\ \end{array} \right.$$

L'algorithme est basé sur la formule de récurrence (en booléens):

A^(k)_ij=A^(k-1)_ij+A^(k-1)_ikA^(k-1)_kj

avec A⁽¹⁾_ij=I_ij+A_ij.

Calcul sur place dans une matrice T:

static void Warshall(Matrice T) {
  int k,i,j;
  for (k= 0; k< T.n; ++k)
    for (i= 0; i< T.n; ++i)
      if (T.m[i][k]== 1)
        for (j= 0; j< T.n; ++j)
          if(T.m[k][j]== 1) 
            T.m[i][j]= 1;
}

La complexité devient O(n³). C'est un exemple où on peut améliorer la complexité sans rien perdre.

Plus court chemin

On se donne sur chaque flèche(i,j) une longueur l(i,j) positive. On cherche à déterminer le plus court chemin d'un sommet à un autre.

On représente le graphe par une matrice C définie par

$$C_{ij}=\left\{\begin{array}{ll} l(i,j) & \mbox{si $(i,j)\in ... ...mbox{si $i=j$ }\\ \infty & \mbox{sinon}\\ \end{array}\right.$$

On pose ensuite C^(k)_ij = la longueur du plus court chemin de i à jutilisant au plus k flèches.Du fait que les longueurs sont positives, on a la relation de récurrence:

$$\begin{array}{\vert l\vert} \hline C^{(k+1)}_{ij}= \min\left\... ...q n\}\\ \end{array}\\ \end{array}\right.\\ \hline \end{array}$$

Ceci conduit à un algorithme en O(n⁴).

Exemple

Si

$$C=\left[ \begin{array}{ccccc} 0&1&\infty&\infty&\infty\\ \in... ...nfty&8&0&1\\ \infty&\infty&\infty&\infty&0 \end{array}\right]$$

La matrice des plus courts chemins est

$$D=\left[ \begin{array}{ccccc} 0&1&10&2&3\\ 6&0&9&1&2\\ 4&5&... ... 5&6&8&0&1\\ \infty&\infty&\infty&\infty&0 \end{array}\right]$$

et

$$P=\left[\begin{array}{ccccc} &&3&1&3\\ 3&&3&&3\\ &0&&1&3\\ &0&&&\\ &&&& \end{array}\right]$$

L'algorithme de Floyd

On considère cette fois C_k[i,j]= la longueur du plus court chemin de i à j ne passant par aucun sommet >k. On a la relation de récurrence:

$$\begin{array}{\vert l\vert} \hline C_{k+1}[i,j]= \min\left\{\... ...C_k[i,k+1]+C_k[k+1,j]\\ \end{array}\right.\\ \hline \end{array}$$

On écrit l'algorithme comme une fonction qui transforme le tableau A sur place et renvoie un tableau P servant à retrouver un plus court chemin.

static Matrice Floyd(Matrice A) {
  Matrice P=new Matrice(A.n);
  for (int i=0; i< P.n; i++)
    for (int j=0; j<P.n; j++)
      P.m[i][j]= -1;
  for (int k= 0; k< A.n; ++k)
    for (int i= 0; i< A.n; ++i)
      for (int j= 0; j< A.n; ++j)
        if (A.m[i][k]+A.m[k][j] < A.m[i][j]) {
          A.m[i][j]= A.m[i][k]+A.m[k][j];
          P.m[i][j]= k;
        }
  return P;
}

Pour retrouver un plus court chemin, on ecrit la fonction suivante qui affiche les sommets utilisés.

static void chemin (int i, int j, Matrice P) {
  int k;
  k= P.m[i][j];
  if (k != -1) {
     chemin(i,k,P);
     System.out.println(k);
     chemin(k,j,P);
   }
}

Il suffit de vérifier que P[i,j]=-1 ssi le plus court chemin de i à j est une flèche et que si P[i,j]=k, le plus court chemin de ià j passe par k.