Exercices (pc 7)

Exercice 1 Soit G = (S, F) un graphe ayant n sommets et m flèches. Soit I la matrice d’incidence de G. Quelle matrice obtient on en multipliant I par sa transposée ?

Exercice 2 Montrer que dans un graphe planaire connexe, on a la formule

n − m + f = 2

entre le nombre n de sommets, le nombre m d’aretes et le nombre f de faces (formule d’Euler).

En déduire que, dans un graphe planaire, m = O(n).

Exercice 3 (algorithme de Dijkstra) On se donne un graphe G = (S, F) et à chaque flèche e de F est asociée une longueur l(f) qui est un entier positif. La longueur d’un chemin est égale à la somme des longueurs des flèches dont il est formé. La distance, notée d(x_{0}, x), de x_{0} à x est la longueur du plus court chemin de x_{0} à x.

Le but de cet exercice est de donner un algorithme de recherche des plus courts chemins à partir d’un sommet donné x_{0} du graphe. On suppose que le graphe est tel que tout sommet x est atteignable à partir de x_{0} par un chemin. Pour trouver cette distance, on considère des fonctions v de X dans l’ ensemble des entiers naturels appelées valuations . On note L la somme des longueurs de tous les arcs de G et on part de la fonction v_{0} telle que v_{0}(x_{0}) = 0 et v_{0}(x) = L pour x ≠ x_{0}. On applique plusieurs fois la procédure de diminution suivante

void Diminution (int a,  int v[]) {
    if (v[ext[a]] > v[or[a]] + l[a])
        v[ext[a]] = v[or[a]] + l[a];
}

1. Montrez que quelque soit le nombre d’appels à la procèdure Diminution en partant de v_{0} on obtient une valuation v telle que :

v[x] ≥ d(x_{0}, x)

2. Montrez que si aucune des procèdures ne diminue la valeur d’un v[x]

alors

v[x] = d(x_{0}, x)

3. Programmez l’algorithme consistant à gérer une file de priorité initialisée à l’ensemble de tous les sommets et à en retirer itérativement le sommet de plus faible valuation. Une fois ce sommet retiré on effectue la procédure Diminution(a,v) pour tous les arcs a ayant ce sommet pour origine.