Probleme – Accessibilité, puissances booléennes et fermeture transitive

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 13 — Le modèle des graphes

Énoncé

Que compte $(I + M)^{k}$ en arithmétique booléenne ?
En déduire un calcul de la relation d'accessibilité, et sa complexité.
Comparer à un parcours depuis chaque sommet.
Vérifier sur le graphe du chapitre.

Corrigé

On travaille dans l'algèbre booléenne : les coefficients valent $0$ ou $1$ , la somme est le « ou » et le produit le « et ». Le produit matriciel s'écrit alors

$(A B)_{u, v} = w ⋁ (A_{u, w} \land B_{w, v}),$

et il vaut $1$ exactement quand il existe un $w$ reliant $u$ à $v$ par les deux relations.

1. Ce que compte $(I + M)^{k}$ . La matrice $I + M$ décrit la relation « $u = v$ ou $u \to v$ », c'est-à-dire « on va de $u$ à $v$ en au plus un arc ». Par récurrence immédiate sur $k$ :

$((I + M)^{k})_{u, v} = 1 ⟺ il existe un chemin de u a ˋ v de longueur \leq k .$

Le $I$ est ce qui transforme « exactement $k$ » en « au plus $k$ » : il autorise à rester sur place.

2. La fermeture transitive. Dans un graphe à $n$ sommets, si $v$ est accessible depuis $u$ , il l'est par un chemin élémentaire — sans sommet répété : en excisant la portion entre deux passages par un même sommet, on raccourcit sans changer les extrémités. Un tel chemin a au plus $n - 1$ arcs. Donc

$M^{*} = (I + M)^{n - 1}$

est exactement la matrice d'accessibilité, ou fermeture transitive (et réflexive) de $M$ .

Complexité. Calculée naïvement, $n - 2$ produits à $Θ (n^{3})$ chacun : $Θ (n^{4})$ . Par exponentiation rapide — on calcule $(I + M)^{2}$ , puis son carré, etc. —, il suffit de $⌈ lo g_{2} (n - 1)⌉$ produits, soit $Θ (n^{3} lo g n)$ . On peut faire mieux : l'algorithme de Floyd-Warshall (chapitre chap:parcours) obtient la même matrice en $Θ (n^{3})$ sans logarithme, et le chapitre note que c'est justement l'algorithme « en lien avec la représentation par matrice d'adjacence ».

3. La comparaison avec les parcours. Lancer un parcours depuis chaque sommet coûte $n$ fois $Θ (n + m)$ , soit $Θ (n^{2} + nm)$ .

	temps	mémoire
puissances booléennes	$Θ (n^{3} lo g n)$	$Θ (n^{2})$
Floyd-Warshall	$Θ (n^{3})$	$Θ (n^{2})$
$n$ parcours sur listes	$Θ (n^{2} + nm)$	$Θ (n + m)$

Sur un graphe creux, les $n$ parcours gagnent nettement : avec $m = Θ (n)$ , ils coûtent $Θ (n^{2})$ contre $Θ (n^{3})$ . Sur un graphe dense, $m = Θ (n^{2})$ , les deux valent $Θ (n^{3})$ et la matrice l'emporte par sa constante — le produit matriciel est une boucle serrée sur de la mémoire contiguë, là où le parcours suit des pointeurs.

Il reste que le résultat occupe $Θ (n^{2})$ dans les deux cas : la fermeture transitive d'un graphe creux n'est pas creuse. Sur le réseau routier français, elle occuperait les $400$ téraoctets calculés plus haut. On ne calcule donc jamais la fermeture transitive d'un grand graphe : on répond aux questions d'accessibilité une par une, par un parcours en $Θ (n + m)$ .

4. La vérification. Mesuré sur le graphe du chapitre, $n = 4$ :

$(I + M)^{3} = 1000110011111101 .$

On lit que tout est accessible depuis $0$ ; que le sommet $2$ n'atteint que lui-même — c'est un puits ; et que la diagonale est la seule partie symétrique, ce qui traduit l'absence de cycle. Vérifié par un parcours en largeur depuis chacun des quatre sommets : les deux matrices sont identiques, case par case.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.