MakarovSuites
Français
EnglishDeutschРусскийУкраїнськаFrançaisEspañolItalianoPolski
Contact et licences

Math

Percolation

Une entrée, une sortie et un échantillon d'un réseau aléatoire : prédisez à quel p cet échantillon laisse passer un flot pour la première fois, augmentez p ou ouvrez des sites à la main et regardez la région atteinte s'étendre - puis lancez de nombreux échantillons de plusieurs tailles et voyez le point de passage se disperser autour de p_c et se resserrer quand le réseau grandit.

Percolation — Image réelle de l’application
Image réelle de l’application

Ce qui se passe

Ouvrez des sites (ou des liens) au hasard avec probabilité p, et demandez si quelque chose relie le bord gauche du réseau au bord droit. Sous un seuil, rien ; au-dessus, presque sûrement - et le changement est brusque. Ici un échantillon est pris au sérieux : un flot se répand depuis l'entrée à travers ce qui est ouvert, le passage s'ouvre à l'instant où il touche la sortie, et cet instant a son propre p pour chaque échantillon. Prédisez-le, augmentez p, ouvrez des sites à la main ; puis lancez des centaines d'échantillons de plusieurs tailles. Leurs points de passage se dispersent autour de p_c = 0,5927 pour les sites et 1/2 pour les liens, et la dispersion se resserre quand le réseau grandit - p_c est là où elle se refermerait pour un réseau infini.

Équations du module
Équations
un site est ouvert avec la probabilité p ; les voisins ouverts forment un seul amas
chaîne 1D :  P(traversée) = p^L exactement
réseau carré 2D, sites :  p_c = 0.592746 (mesuré) ;  liens :  p_c = 1/2 EXACTEMENT - autodualité
dualité :  le réseau dual traverse exactement lorsque le réseau primal ne traverse pas, donc un rectangle (L+1) x L de sites est traversé en p = 1/2 avec la probabilité 1/2 pour tout L
réseau cubique 3D, sites :  p_c = 0.3116
amas géant :  sous p_c le plus grand amas est local ; au-dessus, il occupe une fraction finie de toute la grille

Autres expériences

Retour au catalogue
Théorie des graphes — Image réelle de l’application

Math

Théorie des graphes

Plus courts chemins, arbres couvrants et flots sur un même graphe, dessinés pendant qu'ils se calculent : l'onde de Dijkstra, les îles de Kruskal, les chemins d'Edmonds-Karp et la coupe qui égale le flot.

Voronoï et Delaunay — Image réelle de l’application

Math

Voronoï et Delaunay

Des cellules du plus proche voisin qui se reforment quand on déplace leurs points, la triangulation de Delaunay qui leur est duale avec ses cercles vides, des disques qui grandissent jusqu'à remplir les cellules, et la relaxation de Lloyd qui en fait des hexagones.

Voyageur de commerce — Image réelle de l’application

Math

Voyageur de commerce

Une tournée qui raccourcit sous tes yeux - gloutonne, 2-opt décroisant arête par arête, recuit escaladant le mur - contre l'optimum exact pour treize villes et la force brute sur chaque tournée pour huit.