@ccueil Colles

Programmation en python d'une promenade aléatoire dans un graphe

Modèle du surfeur aléatoire et référencement

\[\psset{unit=1cm,linewidth=2pt,arrowsize=9pt} 
\begin{pspicture}(-.3,-.3)(4.3,4.3) 
%\psline(0,0)(4,0)(4,4)(0,4)(0,0)(4,4) 
\psline{->}(0,4)(3.4,4) 
\psline{<->}(.55,0)(3.55,0)(4,.55)(4,3.55)
\psarc{->}(5.4,-1.4){5.4}{111}{159} 
\psarc{->}(-1.4,5.4){5.4}{291}{339} 
\psarc{->}(-5.1,2){5.4}{-15}{15} 
\psarc{->}(5,2){5.4}{165}{195} 
\pscircle[fillstyle=solid,fillcolor=blue](0,4){.55}\rput(0,4){\bf\white$P1$} 
\pscircle[fillstyle=solid,fillcolor=blue](4,4){.55}\rput(4,4){\bf\white$P2$} 
\pscircle[fillstyle=solid,fillcolor=blue](4,0){.55}\rput(4,0){\bf\white$P4$} 
\pscircle[fillstyle=solid,fillcolor=blue](0,0){.55}\rput(0,0){\bf\white$P3$} 
\end{pspicture}\]

Pour chacun des pages, P1, P2, P3 et P4, on peut donner la liste des pages adjacentes. On remarque d'emblée que ce graphe n'est pas symétrique: une page peut avoir un lien vers une autre sans que cette dernière ne possède un lien réciproque vers elle.
On utilise donc logiquement des listes en python:
S1=[2,3]
S2=[3]
S3=[1,2]
S4=[2,3]
À l'aide la fonction len, on peut créer 4 variables contenant le nombre de pages adacentes à chaque sommet:
Ns1=len(S1)
Ns2=len(S2)
Ns3=len(S3)
Ns4=len(S4)
Enfin, on va utiliser quatre compteurs: c'est-à-dire quatre variables, qui valent initialement 0, et qu'on va augmenter de 1 à chaque passage par la page concernée:
c1=0
c2=0
c3=0
c4=0
et on appelle N le nombre de "sauts" d'une page à une autre. Par exemple, pour commencer:
N=10

On part d'une page au hasard, sur les 4 pages:
S=randint(1,4)
instruction qui nécessite qu'on ait chargé, en début de programme, la bibliothèque contenant la fonction randint:
from random import randint
Le programme en lui-même est maintenant:
for i in range(N):
    if S==1:
        j=randint(0,Ns1-1)
        S=S1[j]
        c1=c1+1
    elif S==2:
        j=randint(0,Ns2-1)
        S=S2[j]
        c2=c2+1
    elif S==3:
        j=randint(0,Ns3-1)
        S=S3[j]
        c3=c3+1
    elif S==4:
        j=randint(0,Ns4-1)
        S=S4[j]
        c4=c4+1

Exercice 1
  1. Regrouper tous les éléments de code précédents dans un même programme et bien comprendre chaque élément.
  2. Ajouter dans ce programme une, ou des, instructions pour afficher les valeurs des compteurs c1, c2, c3 et c4.
    Exécuter ensuite ce programme pour différentes valeurs du nombre N de "sauts" (par exemple N=10, puis N=100, puis N=1000, ...)
  3. Qu'observe-t'on ? Interpréter ces résultats obtenus.

Exercice 2
On considère maintenant le graphe suivant:

Modifier le programme précédent pour l'adapter à cette nouvelle situation.



Voir aussi