TP3 : Parcours de graphes et percolation

Milieux plus ou moins poreux

_images/TP3__Exemple_milieu_peu_poreux.png _images/TP3__Exemple_milieu_poreux.png _images/TP3__Exemple_milieu_très_poreux.png

Documentation

TP3 au Lycée Lakanal (sujet rédigé par Arnaud Basson).

TP3.parcoursLabyrinthe(laby, full=False)[source]

Parcours le labyrinthe laby avec l’algorithme détaillé dans le TP.

  • \(O(n^2)\) en espace additionnel (dejavues prend \(n^2\) et p prend au pire \(O(n^2)\) pour graphe complet),
  • \(O(n^2)\) en temps (chaque case ne peut être empilée et dépilée qu’une seule fois).
  • Si full est True, on renvoie aussi le tableau des cases visitées (dejavues).
TP3.creerMilieu(n, p)[source]

Créé un labyrinthe aléatoire de taille (n, n) représentant un milieu de porosité p.

TP3.simulationEcoulement(n, p, nb=20)[source]

Lance nb (20) simulations pour n, p et affiche le nombre de fois où l’eau s’est écoulée jusqu’en bas.

TP3.afficheMilieuPoreux(milieuPoreux, title=None, filename=None)[source]

Affiche le milieu poreux et l’écoulement d’eau comme dans le TP.

  • On peut fournir le titre et le nom du fichier vers lequel on sauvegarde l’image.
TP3.verifierChemin(A, chemin)[source]

Vérifie que le chemin donné par la liste des sommets successifs (chemin) est bien un chemin valable pour le graphe A.

  • \(O(1)\) en espace, \(O(\text{Nb chemin})\) en temps.
TP3.parcoursGraphe(A, j, k)[source]

Parcours (en largeur) du graphe A, en partant de j, et tentant d’atteindre k, renvoie True ou False selon qu’un chemin existe entre j et k dans A.

  • Mémoire \(O(n)\), temps max \(O(n^2)\) pour n le nombre de sommets.
TP3.cheminGraphe(A, j, k)[source]

Parcours (en largeur) du graphe A, en partant de j, et tentant d’atteindre k, renvoyant un chemin valable s’il existe, False sinon.

  • Mémoire \(O(n)\), temps max \(O(n^2)\) pour n le nombre de sommets.

Sortie du script

$ python TP3.py
Exemple 1 : Le labyrinthe exemple donne par le TP est :
[[0 1 0 0 0 0]
 [0 1 1 1 1 0]
 [0 1 0 1 0 0]
 [0 1 0 1 1 0]
 [0 1 1 0 1 0]
 [0 0 0 0 1 0]]
 ==> Et il admet une solution car : parcoursLabyrinthe(laby) = True
Exemple 2 : ce labyrinthe n'a pas de solution :
[[0 1 0 0 0 0]
 [0 1 1 1 1 0]
 [0 0 1 0 1 0]
 [0 1 1 1 1 0]
 [0 1 1 0 0 0]
 [0 0 0 0 0 0]]
 ==> En effet parcoursLabyrinthe(laby2) = False

Pour n = 20 et p = 0.1 :
[[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
 [0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
 [0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
 [0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
 [0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0]
 [0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
 [0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]]

Pour n = 20 et p = 0.5 :
[[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 0]
 [0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0]
 [0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0]
 [0 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0]
 [0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0]
 [0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0]
 [0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0]
 [0 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0]
 [0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 0]
 [0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0]
 [0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0]
 [0 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0]
 [0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0]
 [0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0]
 [0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0]
 [0 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]]

Pour n = 20 et p = 0.9 :
[[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0]
 [0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0]
 [0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0]
 [0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0]
 [0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0]
 [0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0]
 [0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]]
Pour n = 50 et p = 0.1 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 50 et p = 0.2 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 50 et p = 0.3 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 50 et p = 0.4 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 50 et p = 0.5 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 50 et p = 0.6 et 20 exemples, l'ecoulement a lieu 60.0 % des fois.
Pour n = 50 et p = 0.7 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 50 et p = 0.8 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 50 et p = 0.9 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 50 et p = 0.56 et 20 exemples, l'ecoulement a lieu 10.0 % des fois.
Pour n = 50 et p = 0.58 et 20 exemples, l'ecoulement a lieu 65.0 % des fois.
Pour n = 50 et p = 0.59 et 20 exemples, l'ecoulement a lieu 55.0 % des fois.
Pour n = 50 et p = 0.6 et 20 exemples, l'ecoulement a lieu 65.0 % des fois.
Pour n = 50 et p = 0.61 et 20 exemples, l'ecoulement a lieu 85.0 % des fois.
Pour n = 50 et p = 0.62 et 20 exemples, l'ecoulement a lieu 95.0 % des fois.
Pour n = 100 et p = 0.1 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 100 et p = 0.2 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 100 et p = 0.3 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 100 et p = 0.4 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 100 et p = 0.5 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 100 et p = 0.6 et 20 exemples, l'ecoulement a lieu 70.0 % des fois.
Pour n = 100 et p = 0.7 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 100 et p = 0.8 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 100 et p = 0.9 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 100 et p = 0.56 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 100 et p = 0.58 et 20 exemples, l'ecoulement a lieu 35.0 % des fois.
Pour n = 100 et p = 0.59 et 20 exemples, l'ecoulement a lieu 45.0 % des fois.
Pour n = 100 et p = 0.6 et 20 exemples, l'ecoulement a lieu 65.0 % des fois.
Pour n = 100 et p = 0.61 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 100 et p = 0.62 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 200 et p = 0.1 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 200 et p = 0.2 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 200 et p = 0.3 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 200 et p = 0.4 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 200 et p = 0.5 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 200 et p = 0.6 et 20 exemples, l'ecoulement a lieu 80.0 % des fois.
Pour n = 200 et p = 0.7 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 200 et p = 0.8 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 200 et p = 0.9 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 200 et p = 0.56 et 20 exemples, l'ecoulement a lieu 0.0 % des fois.
Pour n = 200 et p = 0.58 et 20 exemples, l'ecoulement a lieu 10.0 % des fois.
Pour n = 200 et p = 0.59 et 20 exemples, l'ecoulement a lieu 50.0 % des fois.
Pour n = 200 et p = 0.6 et 20 exemples, l'ecoulement a lieu 85.0 % des fois.
Pour n = 200 et p = 0.61 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
Pour n = 200 et p = 0.62 et 20 exemples, l'ecoulement a lieu 100.0 % des fois.
==> On a fait quelques simulations, apparemment p_c = 0.6 a 0.01 pres.
Exemple d'un milieu tres peu poreux (p = 0.50) :
Exemple d'un milieu moyennement poreux (p = 0.60) :
Exemple d'un milieu tres poreux (p = 0.70) :
Le graphe exemple de l'enonce est :
[[0 1 1 0 1 0 0 0 0]
 [1 0 0 0 1 1 0 0 0]
 [1 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 1]
 [1 1 0 0 0 0 1 0 0]
 [0 1 0 0 0 0 1 0 0]
 [0 0 0 0 1 1 0 0 0]
 [0 0 0 1 0 0 0 0 0]
 [0 0 0 1 0 0 0 0 0]]
Le chemin [0, 1, 4, 6, 5] est valable dans le graphe g.
Le chemin [0, 1, 4, 5, 6] n'est pas valable dans le graphe g.
Le chemin [5, 6, 3, 7, 8] n'est pas valable dans le graphe g.
Le chemin [0, 1, 0] est valable dans le graphe g.
Pour le graphe g :
[[0 1 1 0 1 0 0 0 0]
 [1 0 0 0 1 1 0 0 0]
 [1 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 1]
 [1 1 0 0 0 0 1 0 0]
 [0 1 0 0 0 0 1 0 0]
 [0 0 0 0 1 1 0 0 0]
 [0 0 0 1 0 0 0 0 0]
 [0 0 0 1 0 0 0 0 0]]
Existe-t-il un chemin entre j = 0 = A et k = G = 6 ? True (oui)
Existe-t-il un chemin entre j = 0 = A et k = D = 3 ? False (non)
Pour le graphe g :
[[0 1 1 0 1 0 0 0 0]
 [1 0 0 0 1 1 0 0 0]
 [1 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 1]
 [1 1 0 0 0 0 1 0 0]
 [0 1 0 0 0 0 1 0 0]
 [0 0 0 0 1 1 0 0 0]
 [0 0 0 1 0 0 0 0 0]
 [0 0 0 1 0 0 0 0 0]]
Existe-t-il un chemin entre j = 0 = A et k = G = 6 ?
Oui, le voici : [0, 4, 6]
   ([A, B, E, G] ou [A, E, G] ou [A, B, F, G] soit [0, 1, 4, 6] ou [0, 4, 6] ou [0, 1, 6])
Existe-t-il un chemin entre j = 0 = A et k = D = 3 ? False (non)

Le fichier Python se trouve ici : TP3.py.

Note

L’étude du phénomène de percolation est encore très active, en mathématiques comme en physique (e.g. cet article datant du 30 mai 2016).