11. Graphe

graph LR;
1-->2 & 3 & 5 & 8;
2-->9;
3-->5;
4-->3;
5-->6 & 7 & 8;
6-->4 & 7;
7-->6 & 7;
8-->1 & 7 & 9;
9-->7 & 9;

En mémoire, on peut représenter un graphe par une matrice d’adjacence :

En C :

#define MAX 100
typedef struct gra {
    int graphe[MAX][MAX];
    int nbSommets;
} Graphe;

On peut représenter en mémoire un graphe par des listes d’adjacences :
1: 2, 3, 5, 8
2: 9
3: 5
Utile lorsque le nombre d’arcs du graphe est \ll n^2 (n le nombre de sommets).

Remarques

Le schéma précédent illustre un graphe orienté (arc avec un sens). On rencontre aussi des graphes non-orientés (arrêtes).

Vocabulaire

Chemin dans un graphe : Longueur d’un chemin.
Circuit : Dans le graphe ci-dessous, 2 et 3 forment un circuit (je crois?).

graph LR
1-->2
2-->3
3-->2 & 5

Parcours en profondeur dans un Graphe

graph LR;
1-->2 & 7;
2-->9;
3-->1 & 5;
4-->3;
5-->6 & 7;
6-->4 & 7;
7-->8;
8-->1 & 7 & 9;
9-->7 & 9;

// On suppose la structure en C précédente

void estAccessible(Graphe * g, int s, int * tab);

/*
`sd` Sommet de Départ et `sa` Sommet d'Arrivé
On prend *g et pas g pour éviter de recopié le graphe (car il est grand)
donc on prend son adresse.
*/
int chemin(Graphe * g, int sd, int sa) {
    int T[g->nbSommets]; // indique les sommets visités
    for(int i = 0; i < g->nbSommets; i++)
        T[i] = 0;
    estAccessible(g, sd, T);

    return T[sa];
}

/*
`tab` est un tableau contenant au départ que des cases vides à 0
et la fonction met à 1 les cases dont les indices sont les sommets
accessibles par un chemin partant du sommet `s`.
*/
void estAccessible(Graphe * g, int s, int * tab) {
    if(tab[s] == 1) // Si `tab[s]` à déjà été visité
        return;
    tab[s] = 1;
    // Ensuite on parcours tout les successeurs possibles
    for(int i = 0; i < g->nbSommets; i++)
        if(g->graphe[s][i] == 1)
            return estAccessible(g, i, tab); // on continue le parcours à partir de `i`
}

Remarque

On pourrait améliorer la fonction en la quittant lorsque le sommet d’arrivé sa est atteint.

Trouver les circuits

graph TD
A[ ]-->B & C;
B[ ]-->D & E;
C[ ]-->E;
D[ ]-->F;
E[ ]-->D & F;
F[ ]

graph TD
A[ ]-->B & C;
B[ ]-->C & D;
C[ ]-->E;
D[ ]-->C & F;
E[ ]-->D & F;
F[ ]

Définition de pré-visite, post-visité et revisité

Lors d’un parcours en profondeur, chaque sommet peut-être soit :

• jamais visité
• pré-visité puis post-visité (visité une première fois) et éventuellement être revisité (soit visité une nouvelle fois soit au court d’un autre parcours soit pendant le même)
  

Graphe (étiqueté)

Un graphe étiqueté est un graphe où chaque arc possède une étiquette (un nombre, une lettre…)

Vocabulaire (longueur d’un chemin d’un graphe étiqueté)

Par convention, la longueur d’un chemin dans un graphe étiqueté par des nombres est la somme des étiquettes des arcs empruntés par le chemin. La longueur du chemin vide est nulle.

Exemple

graph LR
1==2==>2
1--1-->3
2==3==>4
3--6-->2
4==2==>5

La longueur de 1, 2\rightarrow 2, 2, 2\rightarrow4, 4, 4\rightarrow5, 4, 4\rightarrow5, 5 est 2+3+2=7

Définition (plus court chemin et distance)

Soit un graphe étiqueté par des nombres et deux sommets d et a du graphe.
S’il existe un chemin allant de d à a qui possède la plus petite longueur parmis les chemins allant de d à a alors ce chemin est appelé le plus “court” chemin allant de d à a et sa longueur est appelée la distance de d à a.

Exemple

graph LR
1==1==>2
1--9-->3
2==1==>3

Ici la distance de 1 à 3 vaut 2 et le plus court chemin est 1, 2, 3

Contre-Exemple

graph LR
1--1-->2
1-- -1 -->1

graph TD
3
4

Dans ces 2 cas il n’y a pas de plus court chemin.
On pourrait dire que :

• pour le cas 1, la distance de 1 à 2 est -\infty
• pour le cas 2, la distance de 3 à 4 est +\infty

Problème algorithmique

Entrée: graphe `g`, `d`, `a` deux sommets de `g`
Sortie: plus court chemin (s'il existe) allant de `d` vers `a`

Illustration

Propriété

Soit un graphe G étiqueté par des nombres positifs ou nuls et d’un sommet
Si pour un sommet a on appelle C_a le plus court chemin allant de d vers a, alors :
C_{a} = C_{p} \circ p\rightarrow a
avec p une puissance de a et C_p le plus court chemin allant de d vers p
b(C_{p)} + l(p\rightarrow a) = \min(l(C_{s)} + l(s\rightarrow a),\ t_{q})\ \text{$s$ prédésseur de $a$}
avec l(C_{p}) longueur du chemin C_{p} et l(p\rightarrow a) étiquette de l’arc allant de p\rightarrow a. Si de plus d = a il faut prendre en compte le chemin vide.

Dorénavant les étiquettes seront positives ou nulles.

Algorithme de Dijkstra

Entrée: graphe `g` étiquetté, `d` sommet
Sortie: Pour chaque sommet accessible à partir de `d` : le plus court chemin allant de `d` à `i` et la distance de `d` à `i`

Illustration

Comment traité un sommet pas encore traité ?

Exemple