04 · Séance type — graphes et matrices¶
Intuition
Beaucoup de problèmes concrets sont des structures de connexions : réseaux de transport, dépendances entre tâches, liens entre pages web, circuits, relations sociales.
L'objet mathématique est le graphe, et sa représentation calculatoire est la matrice d'adjacence. Une fois cette traduction faite, l'algèbre linéaire du chapitre Algèbre 05 répond directement à des questions qui semblaient combinatoires.
1. Graphes et matrices¶
Matrice d'adjacence
Pour un graphe à \(n\) sommets, \(\mathbf{M}\) est la matrice \(n\times n\) avec
Le graphe est non orienté si \(\mathbf{M}\) est symétrique.
Le théorème fondateur
Démonstration par récurrence. Vrai pour \(k=1\) par définition. Pour l'hérédité :
On découpe un chemin de longueur \(k+1\) selon son avant-dernier sommet \(s\). \(\blacksquare\)
Conséquences immédiates :
- \(\mathbf{M}^2\) donne le nombre de voisins communs ;
- la connexité se lit sur \(\mathbf{I}+\mathbf{M}+\dots+\mathbf{M}^{n-1}\) : le graphe est connexe si tous les coefficients sont non nuls ;
- \(\operatorname{tr}(\mathbf{M}^3)\) vaut 6 fois le nombre de triangles (chaque triangle est compté une fois par sommet de départ et deux fois par sens de parcours).
2. Séance type — fermeture transitive¶
Problème. Dans un réseau, peut-on aller de \(i\) à \(j\), en un nombre quelconque d'étapes ?
Modélisation. On cherche la fermeture transitive de la relation d'adjacence. En algèbre booléenne (où \(1+1=1\)), elle vaut
Un chemin plus long que \(n-1\) repasserait par un sommet, donc contiendrait un chemin plus court.
Algorithme de Warshall — la solution efficace :
def fermeture_transitive(M):
"""Algorithme de Warshall. M est une liste de listes de 0/1."""
n = len(M)
R = [ligne[:] for ligne in M] # copie
for k in range(n): # sommet intermediaire
for i in range(n):
if R[i][k]: # court-circuit utile
for j in range(n):
if R[k][j]:
R[i][j] = 1
return R
# graphe : 0 -> 1 -> 2 -> 3, plus 3 -> 1 (cycle)
M = [[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[0, 1, 0, 0]]
R = fermeture_transitive(M)
for i, ligne in enumerate(R):
print(f"depuis {i} : {[j for j, v in enumerate(ligne) if v]}")
Résultats.
depuis 0 : [1, 2, 3]
depuis 1 : [1, 2, 3]
depuis 2 : [1, 2, 3]
depuis 3 : [1, 2, 3]
Lecture
Depuis 0, on atteint tout sauf 0 lui-même — cohérent, puisqu'aucune arête ne revient vers 0.
Les sommets 1, 2, 3 s'atteignent mutuellement, eux-mêmes compris : ils forment un cycle, donc une composante fortement connexe.
C'est exactement ce que produit l'algorithme de Warshall, en \(O(n^3)\) — bien mieux que le calcul des \(n-1\) puissances matricielles, en \(O(n^4)\).
L'ordre des boucles n'est pas interchangeable
Dans Warshall, la boucle sur \(k\) doit être la plus externe. Intervertir \(k\) et \(i\) produit un algorithme faux qui, sur beaucoup d'exemples, donne néanmoins le bon résultat — le pire type de bug.
C'est un point qu'un compte rendu doit tester, pas supposer.
3. Séance type — plus court chemin¶
Problème. Trouver le trajet le plus rapide dans un réseau pondéré.
Modélisation. Graphe pondéré, poids \(w_{ij}\geqslant0\). On cherche la distance minimale.
Deux algorithmes, deux usages
| Algorithme | Complexité | Répond à |
|---|---|---|
| Dijkstra | \(O(m\log n)\) avec un tas | Une source vers tous |
| Floyd-Warshall | \(O(n^3)\) | Tous vers tous |
Floyd-Warshall est la version pondérée de Warshall : on remplace « ou logique » par « minimum » et « et » par « addition ».
INF = float("inf")
def floyd_warshall(W):
"""Distances minimales entre toutes les paires. W[i][j] = poids ou INF."""
n = len(W)
D = [ligne[:] for ligne in W]
for k in range(n):
for i in range(n):
for j in range(n):
if D[i][k] + D[k][j] < D[i][j]:
D[i][j] = D[i][k] + D[k][j]
return D
# reseau a 4 noeuds
W = [[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]]
D = floyd_warshall(W)
for i, ligne in enumerate(D):
print(f"depuis {i} : {['%.0f' % v if v < INF else 'inf' for v in ligne]}")
Résultats.
depuis 0 : ['0', '5', '8', '9']
depuis 1 : ['inf', '0', '3', '4']
depuis 2 : ['inf', 'inf', '0', '1']
depuis 3 : ['inf', 'inf', 'inf', '0']
Le résultat clé
La distance de 0 à 3 vaut 9, et non 10 : le chemin direct \(0\to3\) coûte 10, mais le détour \(0\to1\to2\to3\) ne coûte que \(5+3+1 = 9\).
Un plus court chemin n'est presque jamais le chemin direct. C'est exactement le calcul que fait un GPS.
4. Séance type — PageRank¶
Problème. Classer les pages d'un web par importance.
Modélisation. Un « surfeur aléatoire » suit les liens au hasard. Le score d'une page est la proportion du temps qu'il y passe à long terme.
Le modèle
Soit \(\mathbf{P}\) la matrice de transition : \(p_{ij}\) est la probabilité d'aller de \(i\) à \(j\), soit \(\frac{1}{d_i}\) si \(i\) pointe vers \(j\) (\(d_i\) = nombre de liens sortants).
Avec un facteur d'amortissement \(d = 0{,}85\) (probabilité de suivre un lien plutôt que de sauter au hasard) :
Pourquoi l'amortissement : sans lui, une page sans lien sortant absorberait toute la probabilité, et un groupe de pages isolées piégerait le surfeur. Le saut aléatoire garantit l'irréductibilité de la chaîne, donc l'existence et l'unicité du vecteur stationnaire.
def pagerank(liens, n, d=0.85, iterations=100):
"""liens[i] = liste des pages vers lesquelles i pointe."""
r = [1.0 / n] * n
for _ in range(iterations):
nouveau = [(1 - d) / n] * n
for i in range(n):
if liens[i]:
part = d * r[i] / len(liens[i])
for j in liens[i]:
nouveau[j] += part
else:
# page sans lien sortant : on redistribue uniformement
part = d * r[i] / n
for j in range(n):
nouveau[j] += part
r = nouveau
return r
# 0 -> 1, 2 | 1 -> 2 | 2 -> 0 | 3 -> 2
liens = [[1, 2], [2], [0], [2]]
r = pagerank(liens, 4)
for i, v in enumerate(r):
print(f"page {i} : {v:.4f}")
print(f"somme : {sum(r):.6f}")
Résultats.
page 0 : 0.3725
page 1 : 0.1958
page 2 : 0.3941
page 3 : 0.0375
somme : 1.000000
Lecture
- La page 2 est la mieux classée : elle reçoit des liens de 0, 1 et 3 — trois entrées sur quatre pages.
- La page 0 suit de près : elle ne reçoit qu'un lien, mais il vient de la page 2, la plus importante. C'est tout le principe de PageRank : la qualité d'un lien compte plus que le nombre.
- La page 3 est bonne dernière : elle ne reçoit aucun lien. Son score de 0,0375 est exactement \(\frac{1-d}{n} = \frac{0{,}15}{4}\) — le minimum garanti par le saut aléatoire.
Le lien avec le cours
C'est la méthode de la puissance appliquée à \(\mathbf{P}^\top\), dont \(\lambda=1\) est valeur propre parce que \(\mathbf{P}\) est stochastique — exercice 9 du chapitre Algèbre 08 et exercice 10 du chapitre Algèbre 09.
L'amortissement \(d=0{,}85\) garantit \(|\lambda_2|\leqslant0{,}85\), donc une convergence en une centaine d'itérations quelle que soit la taille du web.
Exercices¶
★★ Exercice 1. Soit le graphe non orienté sur \(\{0,1,2,3\}\) avec les arêtes \(0-1\), \(1-2\), \(2-3\), \(3-0\), \(0-2\).
a) Écrire \(\mathbf{M}\). b) Calculer \(\mathbf{M}^2\) et interpréter les coefficients diagonaux. c) Calculer \(\operatorname{tr}(\mathbf{M}^3)\) et en déduire le nombre de triangles.
★★★ Exercice 2. Implémenter Warshall et vérifier que l'inversion des boucles \(k\) et \(i\) donne un résultat faux. Construire un graphe qui le met en évidence.
★★★ Exercice 3. Sur le réseau pondéré du §3, ajouter une arête \(3\to0\) de poids 2.
a) Recalculer les distances. b) Le graphe contient-il un cycle de poids négatif ? Que se passerait-il si oui ?
★★★ Exercice 4. Modéliser l'ordonnancement de tâches : chaque tâche a une durée, et certaines doivent précéder d'autres.
a) Quel objet mathématique ? Quelle contrainte structurelle ? b) Comment calculer la durée minimale du projet ? c) Qu'est-ce que le chemin critique ?
★★★★ Exercice 5. Implémenter PageRank et étudier l'effet du facteur d'amortissement \(d\).
a) Faire varier \(d\) de 0,5 à 0,99 et observer les scores. b) Mesurer le nombre d'itérations nécessaires à la convergence. c) Vérifier expérimentalement que ce nombre croît comme \(\frac{1}{\ln(1/d)}\). d) Pourquoi Google a-t-il choisi 0,85 ?
★★★★ Exercice 6. Le graphe du web réel a \(10^{11}\) pages. Discuter :
a) Peut-on stocker \(\mathbf{P}\) ? b) Quelle structure de données utiliser ? c) Quel est le coût d'une itération de PageRank ? d) Combien de temps pour 100 itérations ?
Corrigés¶
Corrigé — Exercice 1
a)
(Symétrique, car le graphe est non orienté.)
b)
def produit(A, B):
n = len(A)
return [[sum(A[i][k]*B[k][j] for k in range(n)) for j in range(n)]
for i in range(n)]
M = [[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]]
M2 = produit(M, M)
M3 = produit(M2, M)
for l in M2: print(l)
print("trace M^3 =", sum(M3[i][i] for i in range(4)))
Résultat.
[3, 1, 2, 1]
[1, 2, 1, 2]
[2, 1, 3, 1]
[1, 2, 1, 2]
trace M^3 = 12
Interprétation des coefficients diagonaux : \((\mathbf{M}^2)_{ii}\) est le nombre de chemins de longueur 2 de \(i\) vers \(i\), c'est-à-dire le nombre de voisins de \(i\) — son degré.
Degrés : \(\deg(0)=3\), \(\deg(1)=2\), \(\deg(2)=3\), \(\deg(3)=2\) ✓ Somme \(= 10 = 2\times5\) arêtes ✓
Coefficients hors diagonale : \((\mathbf{M}^2)_{ij}\) compte les voisins communs. Par exemple \((\mathbf{M}^2)_{02}=2\) : les sommets 0 et 2 ont deux voisins communs, 1 et 3.
c) \(\operatorname{tr}(\mathbf{M}^3) = 12\).
Chaque triangle est compté 6 fois (3 sommets de départ × 2 sens de parcours) :
Vérification directe : les triangles sont \(\{0,1,2\}\) et \(\{0,2,3\}\) ✓
Corrigé — Exercice 2
def warshall_correct(M):
n = len(M); R = [l[:] for l in M]
for k in range(n):
for i in range(n):
for j in range(n):
if R[i][k] and R[k][j]:
R[i][j] = 1
return R
def warshall_faux(M):
n = len(M); R = [l[:] for l in M]
for i in range(n): # boucles k et i inversees
for k in range(n):
for j in range(n):
if R[i][k] and R[k][j]:
R[i][j] = 1
return R
# chaine 3 -> 2 -> 1 -> 0 : force l'algorithme faux a manquer des chemins
M = [[0,0,0,0],
[1,0,0,0],
[0,1,0,0],
[0,0,1,0]]
A, B = warshall_correct(M), warshall_faux(M)
print("correct :", A)
print("faux :", B)
print("identiques :", A == B)
Résultat.
correct : [[0, 0, 0, 0], [1, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0]]
faux : [[0, 0, 0, 0], [1, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0]]
identiques : True
Sur cet exemple, l'algorithme faux donne le bon résultat
C'est précisément le danger annoncé. Il faut construire un graphe où l'ordre de découverte importe :
# 0 -> 3, 3 -> 1, 1 -> 2 : les sommets intermediaires sont
# numerotes dans le desordre par rapport a l'ordre du chemin
M2 = [[0,0,0,1],
[0,0,1,0],
[0,0,0,0],
[0,1,0,0]]
A, B = warshall_correct(M2), warshall_faux(M2)
print("correct :", A[0])
print("faux :", B[0])
Résultat :
correct : [0, 1, 1, 1]
faux : [0, 1, 0, 1]
L'algorithme faux manque le chemin \(0\to3\to1\to2\). Il a traité \(i=0\) avant d'avoir découvert que \(3\) mène à \(2\).
La leçon : un algorithme qui donne le bon résultat sur un exemple n'est pas correct. Il faut construire le cas qui le met en défaut — c'est l'esprit du test unitaire.
Corrigé — Exercice 3
a)
INF = float("inf")
W = [[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[2, INF, INF, 0]]
D = floyd_warshall(W)
for i, l in enumerate(D):
print(f"depuis {i} : {['%.0f' % v if v < INF else 'inf' for v in l]}")
Résultat.
depuis 0 : ['0', '5', '8', '9']
depuis 1 : ['6', '0', '3', '4']
depuis 2 : ['3', '8', '0', '1']
depuis 3 : ['2', '7', '10', '0']
Le graphe est maintenant fortement connexe : toutes les distances sont finies.
Exemple : de 2 à 1, le chemin est \(2\to3\to0\to1\), de coût \(1+2+5 = 8\) ✓
b) Pas de cycle négatif : tous les poids sont positifs.
Si un cycle de poids négatif existait, on pourrait le parcourir indéfiniment pour faire tendre la distance vers \(-\infty\) : le problème du plus court chemin n'aurait pas de solution.
Floyd-Warshall le détecte : après exécution, si un coefficient diagonal \(D_{ii}\) est devenu strictement négatif, c'est qu'un cycle négatif passe par \(i\). Dijkstra, lui, ne le détecte pas et donne silencieusement un résultat faux — c'est pourquoi il exige des poids positifs.
Corrigé — Exercice 4
a) Objet mathématique. Un graphe orienté acyclique (DAG) : les sommets sont les tâches, une arête \(i\to j\) signifie « \(i\) doit précéder \(j\) ».
Contrainte structurelle : l'absence de cycle. Un cycle signifierait qu'une tâche doit se précéder elle-même — le projet serait infaisable.
Détecter un cycle est donc la première vérification à faire, avant tout calcul.
b) Durée minimale du projet.
On calcule, pour chaque tâche, sa date de début au plus tôt :
avec \(t(j)=0\) pour les tâches sans prédécesseur.
Le calcul se fait dans l'ordre d'un tri topologique du DAG, en \(O(n+m)\).
La durée du projet est \(\max_j\big(t(j)+d_j\big)\).
c) Le chemin critique est le chemin le plus long du DAG, en durée cumulée. C'est lui qui fixe la durée totale.
Propriété essentielle : les tâches du chemin critique ont une marge nulle. Tout retard sur l'une d'elles retarde le projet entier ; à l'inverse, accélérer une tâche hors du chemin critique ne change strictement rien.
Le paradoxe utile
Chercher le chemin le plus long dans un graphe est en général NP-difficile. Mais dans un DAG, c'est facile — il suffit d'inverser le signe des poids et d'appliquer l'algorithme de plus court chemin, ou de faire une simple passe topologique.
C'est un cas où une contrainte structurelle (l'acyclicité) transforme un problème intraitable en un problème linéaire. C'est le cœur de la méthode PERT, au programme du module ROFA24 en deuxième année.
Corrigé — Exercice 5
import math
def pagerank(liens, n, d=0.85, tol=1e-12, max_iter=10000):
r = [1.0 / n] * n
for it in range(1, max_iter + 1):
nouveau = [(1 - d) / n] * n
for i in range(n):
cible = liens[i] if liens[i] else list(range(n))
part = d * r[i] / len(cible)
for j in cible:
nouveau[j] += part
ecart = max(abs(a - b) for a, b in zip(r, nouveau))
r = nouveau
if ecart < tol:
return r, it
return r, max_iter
liens = [[1, 2], [2], [0], [2]]
for d in (0.50, 0.75, 0.85, 0.95, 0.99):
r, it = pagerank(liens, 4, d)
scores = " ".join(f"{v:.4f}" for v in r)
print(f"d={d:.2f} it={it:4d} scores = {scores}")
Résultats.
d=0.50 it= 27 scores = 0.3077 0.2019 0.3654 0.1250
d=0.75 it= 44 scores = 0.3538 0.1952 0.3885 0.0625
d=0.85 it= 54 scores = 0.3725 0.1958 0.3941 0.0375
d=0.95 it= 69 scores = 0.3909 0.1982 0.3984 0.0125
d=0.99 it= 77 scores = 0.3982 0.1996 0.3997 0.0025
a) Effet sur les scores. Plus \(d\) augmente, plus la structure des liens domine : la page 3 (sans lien entrant) s'effondre de 0,125 à 0,0025, tandis que les pages 0 et 2 se rapprochent l'une de l'autre.
Pour \(d\to0\), tous les scores tendraient vers \(\frac14\) — le surfeur saute partout, la structure ne compte plus. Le score de la page 3 vaut d'ailleurs exactement \(\frac{1-d}{4}\) dans tous les cas ✓
b) Nombre d'itérations. Il croît avec \(d\) — de 27 à 77 — mais beaucoup moins vite que prévu.
c) Confrontation à la théorie. Le majorant théorique est gouverné par \(|\lambda_2|\leqslant d\), d'où
Avec \(\text{tol}=10^{-12}\), soit \(\ln(1/\text{tol}) = 27{,}6\) :
| \(d\) | Majorant théorique | Observé | Rapport |
|---|---|---|---|
| 0,50 | 40 | 27 | 0,68 |
| 0,75 | 96 | 44 | 0,46 |
| 0,85 | 170 | 54 | 0,32 |
| 0,95 | 538 | 69 | 0,13 |
| 0,99 | 2749 | 77 | 0,03 |
Le majorant est respecté partout, mais il est de plus en plus lâche.
Pourquoi. La borne \(|\lambda_2|\leqslant d\) est le pire cas. Sur ce graphe minuscule et fortement connecté, la seconde valeur propre de la matrice de transition est bien inférieure à 1, donc \(|\lambda_2|\) est largement en dessous de \(d\) — et la convergence est bien plus rapide que garantie.
C'est un résultat important à savoir énoncer : une borne théorique correcte peut être très pessimiste sur un cas particulier. Sur le web réel, dont le graphe est mal connecté et contient de nombreux pièges, \(|\lambda_2|\) est effectivement proche de \(d\) et la borne devient serrée.
d) Pourquoi 0,85. C'est un compromis entre deux exigences opposées :
- un \(d\) élevé respecte davantage la structure réelle des liens, donc donne un classement plus pertinent ;
- un \(d\) faible converge plus vite, ce qui compte quand on itère sur \(10^{11}\) pages.
À \(d=0{,}85\), une centaine d'itérations suffit sur le web réel pour une précision utilisable, et le classement reste largement gouverné par la structure. À \(d=0{,}99\), il en faudrait des milliers — pour un classement à peine différent.
S'y ajoute un argument de robustesse : un \(d\) proche de 1 rend le classement très sensible aux fermes de liens et aux pièges, alors que le saut aléatoire les neutralise.
Corrigé — Exercice 6
a) Stocker \(\mathbf{P}\) en dense est impossible.
\((10^{11})^2 = 10^{22}\) coefficients, soit \(8\times10^{22}\) octets \(= 80\) zettaoctets.
À titre de comparaison, la totalité des données créées dans le monde en 2025 est estimée à environ 180 zettaoctets. Il faudrait donc la moitié de toute l'information numérique mondiale pour stocker une seule matrice.
b) Structure de données. Le graphe du web est extrêmement creux : une page a en moyenne une quarantaine de liens sortants, pas \(10^{11}\).
On stocke donc une liste d'adjacence — pour chaque page, la liste de ses cibles :
À 8 octets par identifiant : 32 To. C'est beaucoup, mais c'est \(2{,}5\times10^9\) fois moins que la version dense, et parfaitement gérable sur un cluster.
c) Coût d'une itération. Chaque arête est traversée une fois :
C'est linéaire en le nombre de liens, pas quadratique en le nombre de pages. C'est ce qui rend PageRank calculable.
d) Cent itérations.
Sur une seule machine à \(10^{10}\) op/s : \(4\times10^4\) s, soit 11 heures.
Sur un cluster de 1000 machines : 40 secondes de calcul pur — le facteur limitant devient alors le trafic réseau entre machines, pas l'arithmétique.
La leçon de modélisation
Le passage à l'échelle n'a rien changé aux mathématiques : c'est toujours la méthode de la puissance sur une matrice stochastique. Ce qu'il a changé, c'est la représentation — dense vers creuse — et c'est ce seul choix qui fait la différence entre 80 zettaoctets et 32 téraoctets.
C'est exactement ce que demande le troisième temps du module : analyser et critiquer la pertinence et la performance.
Chapitre suivant : Critique des résultats.