Matrices d'adjacence

  Une structure de données simple pour représenter un graphe est la matrice d'adjacence . Pour obtenir , on numérote les sommets du graphe de façon quelconque:

est une matrice carrée dont les c fficients sont et telle que:

Ceci donne alors les déclarations de type et de variables suivantes en Pascal:

const
    Nmax = 50;   (* Nombre de sommets maximal pour un graphe *)
type
    IntSom = 1..Nmax;
    GrapheMat = array[IntSom, IntSom] of integer;
var  
    m: GrapheMat;
    n: IntSom;  (* $n$ est le nombre  effectif de sommets *)
                (* du graphe dont la matrice est $M$ *)

  
Figure: Un exemple de graphe et sa matrice d'adjacence

Un intérêt de cette représentation est que la détermination de chemins dans revient au calcul des puissances successives de la matrice , comme le montre le théorème suivant.

Preuve On effectue une récurrence sur . Pour le résultat est immédiat car un chemin de longueur est un arc du graphe. Le calcul de , pour donne:

Or tout chemin de longueur entre et se décompose en un chemin de longueur entre et un certain suivi d'un arc reliant et . Le résultat découle alors de l' hypothèse de récurrence suivant laquelle est le nombre de chemins de longueur joignant à .
De ce théorème on déduit l'algorithme suivant permettant de tester l'existence d'un chemin entre deux sommets:

function ExisteChemin (i, j: IntSom; n: integer; m: GrapheMat): boolean;
    var
        k: integer;
        u, v, w: GrapheMat;
    begin
    u := m;
    for k := 1 to n do
        begin
        Multiplier(n, u, m, v);
        Ajouter(n, u, v, w);
        u := w;
        end;
    ExisteChemin := (u[i, j] <> 0);
    end;

Remarques

1. L'algorithme utilise le fait, facile à démontrer, que l'existence d'un chemin d'origine et d'extrémité implique celle d'un tel chemin ayant une longueur inférieure au nombre total de sommets du graphe.

    

2. Le nombre d'opérations effectuées par l'algorithme est de l'ordre de car le produit de deux matrices carrées demande opérations et l'on peut être amené à effectuer produits de matrices. La recherche du meilleur algorithme possible pour le calcul du produit de deux matrices a été très intense ces dernières années et plusieurs améliorations de l'algorithme élémentaire demandant multiplications ont été successivement trouvées, et il est rare qu'une année se passe sans que quelqu'un n'améliore la borne. Coppersmith et Winograd ont ainsi proposé un algorithme en ; mais ceci est un résultat de nature théorique car la programmation de l'algorithme de Coppersmith et Winograd est loin d'être aisée et l'efficacité espérée n'est atteinte que pour des valeurs très grandes de . Il est donc nécessaire de construire d'autres algorithmes, faisant intervenir des notions différentes.
3. Cet algorithme construit une matrice (notée ici u) qui peut être utilisée chaque fois que l'on veut tester s'il existe un chemin entre deux sommets ( et ). Dans le cas où on se limite à la recherche de l'existence d'un chemin entre deux sommets donnés (et si ceci ne sera fait qu'une seule fois) on peut ne calculer qu'une ligne de la matrice, ce qui diminue notablement la complexité.