Une marche au hasard sur un graphe

Exercice d'entraînement · niveau 3 (difficile) · mathématiques appliquées (ECG 1re année), chapitre 3 — Théorie des graphes · Graphes en Python

Énoncé

On se promène sur un graphe non orienté connexe : à chaque étape, on passe du sommet courant à l'un de ses voisins, tiré au hasard de façon équiprobable. Écrire une fonction marche(A, depart, N) qui effectue $N$ pas et renvoie les fréquences de visite des sommets. Les comparer, sur le graphe d'arêtes ${1, 2}, {2, 3}, {1, 3}, {3, 4}$ , aux quotients $\frac{d e g ( i )}{2 m}$ .

Corrigé

Le programme.

import numpy.random as rd

def voisins(A, s):
    return [j for j in range(len(A)) if A[s][j] == 1]

def marche(A, depart, N):
    n = len(A)
    visites = [0] * n
    s = depart
    for _ in range(N):
        v = voisins(A, s)
        s = v[rd.randint(0, len(v))]   # entier tire dans 0, 1, ..., len(v)-1
        visites[s] = visites[s] + 1
    return [visites[i] / N for i in range(n)]

rd.randint(0, k) tire un entier dans ${0, \dots, k - 1}$ : chaque voisin a donc la probabilité $\frac{1}{d e g ( s )}$ d'être choisi, ce qui est bien l'équiprobabilité demandée.

Le graphe de l'énoncé. Les degrés valent $2$ , $2$ , $3$ , $1$ , de somme $8 = 2 m$ avec $m = 4$ . Les quotients $\frac{d e g ( i )}{2 m}$ valent donc $0, 25$ , $0, 25$ , $0, 375$ et $0, 125$ . En numérotant les sommets de $0$ à $3$ , la matrice est [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]].

Ce qu'on observe. Pour $N = 100000$ , les fréquences renvoyées sont proches de ces quatre valeurs, à quelques millièmes près : le sommet $3$ , le plus connecté, est le plus visité ; le sommet $4$ , au bout de sa branche, le moins. Une simulation ne démontre rien — elle détecte les erreurs de modèle. Si le graphe n'était pas connexe, la marche resterait enfermée dans sa composante et les autres sommets auraient une fréquence nulle quel que soit $N$ .

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.