Ch. 1 — Vocabulaire et arbres

Un graphe, un modèle

Dans sa forme la plus simple, un graphe est un ensemble de ronds reliés par des lignes : les ronds sont les sommets, les lignes les arêtes. Les sommets ont des noms, les arêtes peuvent porter des étiquettes et avoir un sens (des flèches) — mais un graphe a toujours des sommets et des arêtes. Formellement :

Un graphe G est un couple (S, A) où S est l'ensemble des sommets et A l'ensemble des arêtes, chaque arête étant une paire de sommets (x, y) — qu'on écrit aussi xy.

C'est plus que des dessins : c'est un modèle, une représentation partielle de la réalité concentrée sur les propriétés pertinentes. Réseau social (personnes + connexions), alignement de séquences génétiques, plateau de jeu, réseau routier : le même objet. La méthode du cours : partir d'un problème concret, le modéliser par un problème de graphes, le résoudre, transposer la solution au problème initial.

Le vocabulaire de base

• deux sommets sont voisins s'ils sont reliés par une arête ; les deux sommets d'une arête en sont les extrémités ;
• dans un graphe orienté, les arêtes ont une direction : les prédécesseurs (voisins entrants) de x sont les y tels que (y, x) est une arête, les successeurs (voisins sortants) les y tels que (x, y) est une arête ;
• un chemin est une suite de sommets où chaque sommet est successeur du précédent ; une chaîne est une suite où chaque sommet est voisin du précédent (le sens n'importe pas) ;
• un cycle est un chemin qui commence et termine au même sommet ;
• un graphe est connexe si pour tous deux sommets il existe une chaîne entre eux ; fortement connexe si pour tous deux sommets il existe un chemin de l'un vers l'autre.

Les arbres

Un arbre non orienté est un graphe connexe sans cycle. Un arbre orienté est un graphe orienté connexe qui contient un unique sommet sans prédécesseur — la racine — et dont tous les autres sommets ont exactement un prédécesseur. Conséquence : dans un arbre orienté, pour chaque sommet il existe exactement un chemin depuis la racine ; le prédécesseur de chaque sommet est bien défini, et seule la racine n'en a pas.

Représenter un graphe

Trois représentations servent tout le semestre :

1. l'ensemble des sommets et l'ensemble des arêtes — la définition ;
2. la matrice d'adjacence : matrice carrée booléenne, ligne x colonne y valant 1 exactement quand il existe une arête de x à y (symétrique si le graphe n'est pas orienté) ;
3. les listes de successeurs : pour chaque sommet, la liste de ses successeurs — économique en mémoire pour les graphes creux, et c'est ce format qu'utilise Grapp.

La matrice d'adjacence fait plus que décrire : avec la somme ⊕ et le produit ⊗ booléens (ET/OU logiques), la matrice M puissance k indique s'il existe des chemins de longueur k, et M≤k = M ⊕ M² ⊕ … ⊕ Mᵏ indique l'accessibilité en au plus k pas. Le produit usuel de matrices compte, lui, les chaînes de chaque longueur — et le nombre de cycles. C'est ainsi qu'on identifie les sommets centraux d'un réseau social : l'excentricité d'un sommet est la distance maximale qui le sépare d'un autre sommet, et un centre est un sommet de plus faible excentricité.

Le premier algorithme : le parcours en largeur

Entrées : un graphe G et un sommet s0. Résultat : un arbre orienté de racine s0 dont les sommets sont ceux accessibles depuis s0 (un sommet y est accessible depuis x s'il existe un chemin de x à y) et dont les arêtes sont des arêtes de G.

soit Pred(y) = indéfini pour tout y sommet de G   // table des prédécesseurs
soit D = { s0 }                                   // ensemble des sommets découverts
soit F = [ s0 [                                   // file d'exploration
tant que NON F.estVide()
  soit s = F.tête()
  si s possède un successeur x qui n'est pas dans D alors
    ajouter x à D
    F.enfiler(x)
    Pred(x) = s
  sinon
    F.défiler()
retourner l'arbre défini par Pred

La structure de contrôle est une file (premier entré, premier sorti) ; le résultat — l'arbre de parcours — est donné par la table Pred. Sur le problème du routage d'antennes, l'arbre de parcours répond d'un coup : qui peut recevoir le message, et par quel relais.

Chemins particuliers à connaître

Un chemin eulérien contient une fois et une seule chaque arête du graphe ; un chemin hamiltonien, une fois et une seule chaque sommet. Le cycle hamiltonien est le cœur du problème du voyageur de commerce — visiter chaque ville une seule fois au coût minimal — un problème à beaucoup d'applications, mais pour lequel il n'existe pas d'algorithme qui trouve rapidement une solution dans un grand graphe. Les casse-têtes des TD (l'échange de cavaliers) se résolvent exactement de cette manière : une modélisation par graphe, puis une recherche de chemin.

A retenir

• graphe = (S, A) ; orienté ou non ; chemin (successeurs) vs chaîne (voisins) vs cycle ;
• connexe (chaînes) vs fortement connexe (chemins) ;
• arbre non orienté = connexe sans cycle ; arbre orienté = racine unique, un seul prédécesseur par sommet, un seul chemin depuis la racine ;
• matrice d'adjacence : Mᵏ = existence de chemins de longueur k, M≤k = accessibilité, produit usuel = comptage ; excentricité et centre pour la centralité ;
• le parcours en largeur (file, ensemble D, table Pred) construit l'arbre de parcours depuis un sommet.