MOKSLASplius.lt

Perkoliacija

Žodis ,,perkoliacija'' reiškia skysčių gebėjimą prasisunkti pro porėtą medžiagą. Fizikoje šis terminas naudojamas ir bendresne prasme: fizinės sistemos virsmui iš vienos būsenos į kitą nusakyti. Įsivaizduokime, kad turime dėžę, prikrautą elektros srovei nelaidžių plastikinių ir laidžių metalinių rutuliukų. Jei metalinių rutuliukų yra daug, tada gretimi rutuliukai liesis ir dėžė bus laidi elektros srovei. Tačiau jei dėžėje yra daugiau plastikinių rutuliukų, metaliniai rutuliukai greičiausiai bus izoliuoti ir srovė tekėti negalės. Įdomiausia tai, kad didinant metalinių rutuliukų skaičių dėžė pasidarys laidi ne palaipsniui, o staiga, esant tam tikram metalinių ir plastmasiniu rutuliukų santykiui. Pagrindinis perkoliacijos klausimas yra toks: kiek turi būti metalinių rutuliukų dėžėje, kad pradėtų tekėti elektros srovė? Arba bendriau: kada feromagnetikas savaime įsimagnetins, arba amorfinis puslaidininkis iš nelaidžios būsenos pereis į laidžią, arba kada susidarys žvaigždžių spiečius? Šiuos ir panašius klausimus nagrinėja perkoliacijos teorija. Perkoliacijos uždaviniai yra taip pat svarbūs ir praktikoje, nes jie leidžia sužinoti, pavyzdžiui, ar vanduo prasisunks pro jūsų sukonstruotą pylimą, ar bus įmanoma išsiurbti naftą iš porėtos uolienos. Epidemiologai, pasitelkę perkoliacijos teorijos metodus, gali pranašauti, ar užkrečiama liga išplis regione. Paminėtuose uždaviniuose susiduriame su atsitiktinėmis didelės apimties sistemomis. Dėl šios priežasties perkoliacijos uždaviniams spręsti reikalingi spartūs kompiuteriai. Skyriuje apsiribosime paprasta dvimate sistema, sudaryta iš didelio skaičiaus juodų ir baltų (laidžių ir nelaidžių) kvadratų. Pasitelkę atsitiktinių skaičių generatorių, modeliuosime, kaip susidaro begalinis klasteris ir įvyksta fazinis virsmas. Pakeliui susipažinsime su grafais bei išmoksime rūšiuoti sąrašų duomenis.

Atsitiktinės gardelės ir klasteriai

Juodi ir balti kvadratai šachmatų lentoje išdėstyti tvarkingai. Mes nagrinėsim lentą, kurioje balti ir juodi kvadratai (perkoliacijos teorijoje vadinami gardelėmis) yra išsibarstę visiškai netvarkingai. Nupiešime tokią lentą. Tam pradžioje intervale tarp nulio ir vieneto laisvai pasirinkime atsitiktinį skaičių $ p $. Tegu kompiuterio atsitiktinių skaičių generatorius kiekvienam langeliui priskiria atsitiktinį skaičių $ r $, kurio vertė taip pat yra tarp nulio ir vieneto: $ 0\leq r\leq 1 $. Jei langeliui priskirtas atsitiktinis skaičius yra mažesnis už pasirinktąjį, $ r\leq p $, jį nudažysime juodai, priešingu atveju — paliksim baltą. Pasinaudoję tokiu ,,spalvinimo'' būdu, lentą paversime netvarkinga baltų ir juodų kvadratų mozaika. Jei $ n $ ir $ m $ žymi langelių skaičių atitinkamai horizontalioje ir vertikalioje lentos briaunose, spalvinimo metodą realizuoja toks algoritmas:
\boldmath\begin{eqnarray*}lenta[p\_\mathrm{Real},\{n\_\mathrm{Integer},  m\_\mathrm{Integer}\}]:=\mathrm{Table}[\mathrm{If}[\mathrm{Random}[]<p,1,   0],\{n\},\{m\}]\end{eqnarray*}

Paimkime $ m\times m $ lentą ir , pavyzdžiui, keturias $ p $ reikšmes: $ p=0{,}2;\ 0{,}4;\ 0{,}6;\ 0{,}8 $. Atsitiktinių skaičių generatoriaus nuspalvintas ,,šachmatų lentas'' vizualizuosime grafikos komanda \boldmath$ListDensityPlot[~]$:
Tikimybės vertė: \boldmath$pr$=
Lentelės dimensija: \boldmath$m$=

\boldmath\begin{eqnarray*}\mathrm{ListDensityPlot}[-\mathrm{Reverse}[lenta[\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{pr}$},\{\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{m}$},\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{m}$}\}]],  PlotLabel\to "p="<>\mathrm{ToString}[\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{pr}$}]]\end{eqnarray*}

  

Iš sugeneruotų piešinių matyti, kad didinant spalvinimo slenkstį nustatančią tikimybę $ p $ juodų langelių daugėja. Klasteriu vadinsime tokią juodų langelių sankaupą, kurioje kiekvienas juodas langelis liečiasi su kitu juodu langeliu viena ar keliomis briaunomis. Kai $ p=0{,}2 $, klasteriai yra izoliuoti, o kai $ p=0{,}8 $, modeliuodami dažniausiai gausime tik vieną didelį klasterį. Patį paprasčiausią netrivialų (ne iš vieno langelio) klasterį sudaro du juodi langeliai. Kad būtų aiškiau, $ 4\times 4 $ lentoje mubraižykim po du juodus ir baltus langelius:
\boldmath\begin{eqnarray*}&&g1 = \mathrm{ListDensityPlot}[\mathrm{Reverse}[-\{\{1, 0\}, \{1, 0\}\}],       \mathrm{Frame}\to \mathrm{False},       \mathrm{DisplayFunction}\to \mathrm{Identity}];\\ &&g2 = \mathrm{ListDensityPlot}[\mathrm{Reverse}[-\{\{1, 0\}, \{0, 1\}\}],       \mathrm{Frame}\to \mathrm{False}, \mathrm{DisplayFunction}\to \mathrm{Identity}]; \\&&\mathrm{Show}[\mathrm{GraphicsArray}[\{g1, g2\}], \mathrm{ImageSize}\to 216,     \mathrm{DisplayFunction}\to \$\mathrm{DisplayFunction}];\end{eqnarray*}

  

Parinktimi \boldmath$\mathrm{DisplayFunction}\rightarrow\mathrm{Identity}$ pradžioje sustabdėme grafikų braižymą tam, kad komanda \boldmath$\mathrm{GraphicsArray}[~]$ galėtume juos išdėstyti vienoje eilutėje. Tik po to panaudoję\boldmath$\mathrm{DisplayFunction}\rightarrow\$\mathrm{DisplayFunction}$ leidome viską iš karto nubraižyti.Kairėje pusėje turime mažiausią klasterį. Dešinėje pusėje dvi gardelės klasterio nesudaro, nes langeliai liečiasi viršūnėmis, o ne briaunomis. Kaip matėme, realioje struktūroje klasterių dydžiai priklauso nuo tikimybės $ p $. Kai $ p $ yra mažas, klasteriai dažniausiai esti maži ir sudaryti vos iš kelių gardelių. Didinant $ p $, didėja ir klasteriai. Įdomiausia yra tai, kad pasiekus tam tikrą $ p $ reikšmę, vadinamą perkoliacijos slenksčiu $ p_c $, begalinėje lentoje staiga susidaro begalinis klasteris. Jei lenta yra baigtinė, toks klasteris sujungia priešingas lentos briaunas. Taip atsitikus tarp priešingų lentos kraštų pradės tekėti srovė, jei juodi langeliai yra laidūs srovei, o prie lentos kraštų prijungėme įtampos šaltinį. Tokiu atveju sakoma, kad sistemoje įvyko fazinis virsmas.

Klasterių rūšiavimas

Kadangi langeliai spalvinami atsitiktinai, tai kiekvieną kartą braižydami naują lentą joje gausite skirtingus klasterius. Jei norite pakartoti čia pavaizduotą situaciją, pradėkite nuo komandos \boldmath$SeedRandom[5025]$, kurioje skaičius \boldmath$5025$ inicializuoja tam tikrą atsitiktinių skaičių generatoriaus pradinę būseną. Jei norite gauti kitokius klasterius, šią komandą neutralizuokite apgaubdami komentarais $ \boldsymbol{(*}\textrm{ ir }\boldsymbol{*)} $, įrašykite kitą skaičių arba tiesiog komandą ištrinkite. Tolimesnis mūsų tikslas — surūšiuoti ir išrinkti reikalingus klasterius. Pradėkime nuo nedidelės atsitiktinės matricos \boldmath$rm$ generavimo.
Atsitinktinių skaičių inicializacijos reikšmė: \boldmath$inicializacija$=
Tikimybės vertė: \boldmath$pr$=
Lentelės dimensijos: \boldmath$m_1$= ir \boldmath$m_2$=

\boldmath\begin{eqnarray*}&&\mathrm{SeedRandom}[\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{inicializacija}$}];\\&&rm=lenta[\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{pr}$},\{\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{m_1}$},\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{m_2}$}\}]\end{eqnarray*}

  

Vienetinių elementų indeksus (pozicijas) matricoje rasime komanda \boldmath$\mathrm{Position}[~]$:

\boldmath\begin{eqnarray*}&&vienetai=\mathrm{Position}[rm,1]\end{eqnarray*}

  

Klasterių radimo uždavinys gali būti nesunkiai performuluotas į daug bendresnį grafo jungių dalių (connected components) radimo uždavinį. Nesigilindami į grafų teoriją (nors ir labai įdomią) tik pasakysime, kad grafą galima įsivaizduoti kaip taškų, vadinamų grafo viršūnėmis, rinkinį, kurio kai kurie ar visi taškai yra sujungti tarpusavyje linijomis, vadinamomis grafo briaunomis ar kraštinėmis. Jei linijos jungia visus taškus, t.y. jei keliaudami linijomis iš bet kurio taško galime pasiekti bet kurį kitą tašką, grafas vadinamas jungiu. Jungiomis taip pat vadinamos grafo atskiros dalys, sujungtos briaunomis. Kitame puslapyje skaitytojas pamatys matricos \boldmath$rm$ grafą, kurį sudaro $ 5 $ jungios dalys (trys atskiri, linijomis nesujungti taškai plius apatinė maža ir viršutinė didelė jungi dalis). Mūsų sugeneruotą atsitiktinę matricą \boldmath$rm$ arba lentą grafu paversti labai lengva. Grafo viršūnes atitiks gardelės su vienetais. Gardeles sujungsime linija tada, kai jos liečiasi, t.y. kai jų eilučių ir stulpelių indeksų skirtumas neviršys vieneto. Tai nusakysime tokiu paprastu kriterijumi:

\boldmath\begin{eqnarray*}&&artimasQ[i\_,j\_]:=\mathrm{If}[\mathrm{Plus}@@|i-j|\leq 1,\mathrm{True},\mathrm{False}]\end{eqnarray*}

Grafų generavimui ir darbui su jais skirtos funkcijos yra surinktos standartiniame pakete \boldmath$\mathrm{DiscreteMath}{}^\backprime\mathrm{Combinatorica}{}^\backprime$. Tai labai didelis paketas, turintis

\boldmath\begin{eqnarray*}&&<<\mathrm{DiscreteMath}^\prime\mathrm{Combinatorica}^\prime\\&&\mathrm{Names}["\mathrm{DiscreteMath}^\prime\mathrm{Combinatorica}^\prime*"]//\mathrm{Length}\end{eqnarray*}
papildomas funkcijas.

Iš jų mums bus reikalingos tik trys — grafui generuoti \boldmath$\mathrm{MakeGraph}[~]$, grafui (su viršūnių žymėmis) braižyti \boldmath$\mathrm{ShowLabeledGraph}[~]$ bei, svarbiausia, jungioms komponentėms surasti \boldmath$\mathrm{ConnectedComponents}[~]$. Jų visų sintaksė akivaizdi iš žemiau pateiktų pavyzdžių (smulkesnį aprašą gausite, surinkę klaustuką ir atitinkamos funkcijos pavadinimą). Komandai \boldmath$\mathrm{MakeGraph}[~]$ be pačių duomenų dar reikalingas kriterijus (mūsų atveju \boldmath$artimasQ[~]$) grafui iš duomenų sukonstruoti, o funkcijai \boldmath$\mathrm{ShowLabeledGraph}[~]$ — pats grafas ir jo viršūnių žymės.

\boldmath\begin{eqnarray*}&&grafas=\mathrm{MakeGraph}[vienetai, artimasQ[#1,#2]\&];\\&&\mathrm{Show}[\mathrm{Block}[\{\mathrm{DisplayFunction}=\mathrm{Identity}\},\mathrm{ShowLabeledGraph}[grafas,vienetai]],\mathrm{PlotRange}\to \mathrm{All}]\end{eqnarray*}

Klasterius rasti labai paprasta. Tai, kaip minėjome, jungios grafo dalys:

\boldmath\begin{eqnarray*}&&grafoKlasteriai = ConnectedComponents[grafas]\end{eqnarray*}

Taigi, gavome penkis klasterius: tris izoliuotus taškus {1}, {4}, {6}, vieną, jungiantį tris taškus {2,3,5} klasterį ir vieną, jungiantį dešimt taškų. Grafo viršūnės numeruojamos eilės tvarka, todėl lengva pastebėti atitikimą tarp pirminių duomenų (vienetų matricoje) ir grafo viršūnių numerių.

\boldmath\begin{eqnarray*}&&atitikmenys=\mathrm{Thread}[\mathrm{Rule}\mathrm{Range}[\mathrm{Length}[vienetai]],vienetai]]\end{eqnarray*}

\boldmath\begin{eqnarray*}&&klasteriai=grafoKlasteriai/.atitikmenys\end{eqnarray*}

Atkreipkite dėmesį į gauto sąrašo struktūrą. Jame turime klasterius, kurių elementai yra pirminės matricos indeksai. Dabar klasterius surūšiuosime pagal jų ilgį.

\boldmath\begin{eqnarray*}&&rusiuotiKlasteriai=\mathrm{Split}[\mathrm{Sort}[\mathrm{Length}/@klasteriai]]\end{eqnarray*}

Suskaičiuojame, kiek įvairių dydžio klasterių turime, ir rezultatą pavaizduojame \boldmath$\mathrm{ListPlot}[~]$.

\boldmath\begin{eqnarray*}&&suskaiciuotiKlasteriai=\mathrm{Map}[\{\mathrm{First}[#1],\mathrm{Length}[#1]\}\&,  rusiuotiKlasteriai];\\&&\mathrm{ListPlot}[suskaiciuotiKlasteriai,\mathrm{AxesLabel}\to \{Langeliai,Klasteriai\},\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{parinktys}$},\\&&\mathrm{PlotRange}\to\{\{0,\mathrm{Max}[\mathrm{Map}[\mathrm{First},suskaiciuotiKlasteriai]]+0.5\},\{0,          \mathrm{Max}[\mathrm{Map}[\mathrm{Last},suskaiciuotiKlasteriai]+0.5]\}\}]\end{eqnarray*}

Piešimo parinktys:

  

Išrinkime patį didžiausią klasterį ir jį nubraižykime. Šiuo tikslu pirmiausia ,,išmatuosime'' sąrašo \boldmath$klasteriai$ elementų ilgius ir rasime tarp jų didžiausią, po to iš viso sąrašo išrinksime elementus, kurių ilgis lygus rastam skaičiui.

\boldmath\begin{eqnarray*}&&maxKlasterioDydis=\mathrm{Max}[\mathrm{Length}/@klasteriai];\\&&maxKlasteris=\mathrm{Select}[klasteriai,\mathrm{Length}[#1]===maxKlasterioDydis\&]\end{eqnarray*}

Pasinaudoję gautu atsakymu, paruošime matricą, kuri susideda tik iš maksimalaus klasterio vienetukų. Tam komanda \boldmath$\mathrm{Table}[~]$ pradžioje paruošime nulinę matricą, kurioje klasterio pozicijose esančius nulius pakeisime vienetukais.

\boldmath\begin{eqnarray*}&&maxKlasterioMatrica=\mathrm{Map}[\mathrm{ReplacePart}[\mathrm{Table}[0,\{\mathrm{Length}[rm]\},\{\mathrm{Length}[rm[[1]]]\}],            1,#1]\&],maxKlasteris]\end{eqnarray*}

Matricą, kurios vienetukai sudaro didžiausią klasterį, vizualizuojame:

\boldmath\begin{eqnarray*}&&\mathrm{Map}[\mathrm{ListDensityPlot}[\mathrm{Reverse}[-1*#],\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{parinktys}$}]\&,maxKlasterioMatrica]\end{eqnarray*}

Piešimo parinktys:

  

Čia nupieštą didžiausią klasterį galima buvo nesunkiai pastebėti pirminėje matricoje. Tuo atveju, kai atsitiktinė pirminė matrica yra labai didelė, joje surasti patį didžiausią klasterį praktiškai įmanoma tik kompiuteriu, pavyzdžiui, čia aptartu būdu.

Perkoliacijos slenkstis

Perkoliacijos slenksčiu $ p_c $ yra vadinama tikimybės $ p $ vertė, kuriai esant begalinėje gardelėje susidaro pirmasis begalinis klasteris. Nagrinėjamos baigtinės gardelės atveju tai reiškia, kad sistemoje atsiranda klasteris, jungiantis viršutinį ir apatinį arba kairį ir dešinį atsitiktinės matricos \boldmath$rm$ kraštus. Begalinėms gardelėms galioja [Kirkpatrick73] tokia svarbi teorema: begalinėje gardelėje egzistuoja slenkstinė (krizinė) tikimybė $ p_c $ tokia, kad esant $ p\geq p_c $ yra tik vienas begalinis klasteris (pratekėjimo kanalas), o kai $ p<p_c $, nėra nė vieno tokio klasterio. Kitais žodžiais tariant, paskutiniuoju atveju visi klasteriai yra baigtinio dydžio. Atsiradus begaliniam klasteriui (baigtinės gardelės atveju turime priešingas briaunas jungiantį klasterį), juo ima tekėti skystis arba srovė. Todėl perkoliacijos sąlygų žinojimas praktikoje yra svarbus visur, kur turime reikalą su skysčių sunkimusi pro poringas medžiagas. Svarbu įsidėmėti, kad perkoliacijos slenkstis yra begalinės sistemos charakteristika. Baigtinės sistemos atveju $ p_c $ nepriklauso nuo sistemos matmenų tik tuo atveju, jei sistema yra pakankamai didelė. Pats mažiausias ,,begalinis'' (jungiantysis) klasteris $ 5\times 5 $ lentoje atrodo taip:

\boldmath\begin{eqnarray*}&&\mathrm{ListDensityPlot}[\mathrm{Table}[\mathrm{If}[j==3,0,1],\{5\},\{j,5\}],    \mathrm{Frame}\to \mathrm{False}]\end{eqnarray*}

Piešimo parinktys:

  

Kai lenta didelė, tikimybė, kad pasirodys tokio tiesaus pavidalo jungiantysis klasteris, yra be galo maža. Žymiai didesnė tikimybė, kad priešingas briaunas jungiantis klasteris bus netvarkingas. Sudarysime algoritmą, nustatantį, ar sistemoje yra jungiantysis klasteris. Apibrėšime jungiančiojo klasterio atsiradimo tikimybę tokiu būdu:

\[ p_\infty =\frac{\textrm{langeli\k u\ skai\v cius\ jungian\v ciame\ klasteryje}}{\textrm{pilnas\ juod\k u\  langeli\k u\ skai\v cius}}. \]
Norint patikrinti, ar atsirado jungiantis klasteris, reikia pažiūrėti, ar išskirtuose klasteriuose nėra tokio, kuris jungia lentos galus, t.y. ar tokiame klasteryje yra elementai, priklausantys kraštinėms pozicijoms. Nors tikrinant būtų logiška apsiriboti tik klasteriais, kurių ilgis viršija gardelės dydį, mes tikrinsime visus. Dvi pirmos \boldmath$\mathrm{FreeQ}[~]$ komandos tikrina, ar nėra jungaus klasterio tarp lentos viršaus ir apačios, o kitos dvi — tarp lentos šonų.
\boldmath\begin{eqnarray*}&&jungiantysisKlasteris=\mathrm{Select}[klasteriai,(\mathrm{Not}[\mathrm{FreeQ}[#1,\{1,\_\}]\&\& \mathrm{Not}[\mathrm{FreeQ}[#1,\{m,\_\}]] \\&& \| \mathrm{Not}[\mathrm{FreeQ}[#1,\{\_, 1\}]\&\& \mathrm{Not}[\mathrm{FreeQ}[#1,\{\_,n\}]]\&])\end{eqnarray*}

Kadangi sąrašas yra tuščias, mūsų atveju jungaus klasterio nėra. Skaičiavimuose aprašytus žingsnius lengva sujungti į atskirą žemiau pateiktą modulį \boldmath$jungusKlasteris[~]$. Jei jungaus klasterio nebus, modulis įgis nulinę vertę. Atsiradus jungiam klasteriui, modulis duos anksčiau apibrėžtą jungiančiojo klasterio atsiradimo tikimybės $ p_\infty $ vertę. Priminsime, kad modulyje pirmajame sąraše nurodyti to paties pavadinimo simboliai bus interpretuojami kaip modulio lokaliniai kintamieji, todėl su anksčiau apibrėžtais dydžiais nesimaišys

\boldmath\begin{eqnarray*}&&\$RecursionLimit=\infty ;\\&&jungusKlasteris[p\_,\{m\_,n\_\}]:=\mathrm{Module}[\{rm,vienetai,klasteriai\},\\&&\quad    rm=lenta[p,\{m,n\}];vienetai=\mathrm{Position}[rm,1];\\&&\quad klasteriai=\mathrm{ConnectedComponents}[\mathrm{MakeGraph}[vienetai,              artimasQ[#1,#2]\&]]/.\mathrm{Thread}[\mathrm{Range}[\mathrm{Length}[vienetai]]\to vienetai];\\&&jungiantysisKlasteris=\mathrm{Select}[klasteriai,(\mathrm{Not}[\mathrm{FreeQ}[#1,\{1,\_\}]\&\& \mathrm{Not}[\mathrm{FreeQ}[#1,\{m,\_\}]] \\&& \| \mathrm{Not}[\mathrm{FreeQ}[#1,\{\_, 1\}]\&\& \mathrm{Not}[\mathrm{FreeQ}[#1,\{\_,n\}]]\&]);\\&&\mathrm{If}[jungiantysisKlasteris===\{\}, 0,\frac{\mathrm{Length}[\mathrm{First}[jungiantysisKlasteris]]}{\mathrm{Length}[vienetai]}]]\end{eqnarray*}

Brėžinyje atidėkime $ p_\infty $ priklausomybę nuo balto-juodo langelio generavimo tikimybės $ p $. Tam pakanka mūsų modulį patalpinti į lentelės komandą \boldmath$\mathrm{Table}[~]$. Lentos dydį $ \textbf{m}\times\textbf{n} $ parinksime $ 11\times 11 $. Tikimybę $ p $ keisime nuo $ 0{,}2 $ iki $ 1 $ žingsniu $ 0{,}05 $.

\boldmath\begin{eqnarray*}&&\mathrm{ListPlot}[\mathrm{Table}[\{p,jungusKlasteris[p,\{\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{m}$},\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{m}$}\}]\},\{p,            \fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{p_{start}}$},\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{p_{end}}$},\fcolorbox[rgb]{1,0,0}{1,1,1}{$\vphantom{\vbox to 6pt{}}\smash{p_{step}}$}\}]]\end{eqnarray*}

Tikimybių vertės: nuo \boldmath$p_{start}$= iki \boldmath$p_{end}$= žingsniu \boldmath$p_{step}$=
Lentelės dimensija: \boldmath$m$=
Piešimo parinktys:

  

Kaip matyti iš brėžinio, kol $ p $ yra mažesnis už maždaug $ 0{,}6 $, tikimybė sugeneruoti klasterį, kuris sujungtų priešingas atsitiktinės matricos eilutes ar stulpelius, yra artima nuliui. Pirmasis jungiantysis klasteris susidaro apytiksliai prie $ p_c=0{,}6 $. Po to, kai $ p $ pasiekia kritinę vertę $ p_c $, tikimybė $ p_\infty $ auga tuo staigiau, kuo didesnę atsitiktinę matricą imame. Be galo didelės matricos atveju turėsime laiptelio pavidalo $ p_\infty $ priklausomybę nuo $ p $. Tikslesni skaičiavimai su didelėmis atsitiktinėmis matricomis rodo [Ziman79], kad šuolis įvyksta ties slenksčiu $ p_c=0{,}593 $. Panašūs dalykai stebimi ir bendresniu atveju, kai turime ne kvadratinę o, pavyzdžiui, trikampio pavidalo elementariąją gardelę, arba kai nagrinėjame ne dvimatį, o realų trimatį uždavinį. Elementarios gardelės nebūtinai turi būti tvarkingai išsidėsčiusios plokštumoje ar erdvėje: ir esant netvarkingam jų centrų išsidėstymui bei nevienodam gardelių dydžiui ties $ p_c $ susidaro be galo didelis klasteris, t.y. sistemoje įvyksta fazinis virsmas. Konkreti $ p_c $ vertė, kuriai esant įvyksta fazinis virsmas, priklauso nuo nagrinėjamos sistemos. Pavyzdžiui, trikampės plokščios gardelės atveju $ p_c=0{,}5 $. Mūsų jungių klasterių paieškos algoritmą galima pritaikyti kitokios formos elementarių lastelių, pavyzdžiui, trikampių, rūšiavimui ar bet kokios dimensijos gardelėms. Algoritmas yra labai bendras, tačiau lėtai veikiantis. Čia nagrinėjamai gardelei egzistuoja spartesni algoritmai. Vienas jų aprašytas darbe [Hoshen76]. Čia tik pastebėsime, kad visų kompiuterinės algebros sistemų, tame tarpe ir Mathematica, skaičiavimo sparta yra lėta lyginant su kompiliuojamų programavimo kalbų, tokių kaip Fortran ar C, sparta. Todėl dideliems duomenų kiekiams apdoroti tenka šiomis kalbomis rašyti atskiras programas. Programas perkoliacijos uždaviniui Basic, Fortran ir Pascal kalbomis rasite knygoje [Gould88]. Joje taip pat pateiktas ir platus literatūros šia tema sąrašas. Apie perkoliaciją populiariai papasakota A.L. Efroso knygelėje [Efros82].

Literatūra

S. Kirkpatrick, Rev. Mod. Phys. Vol. 45, No4., p.574-588 (1973)

J. Hoshen, R. Kopelman, "Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm", Phys. Rev.B, Vol. 14, No 8, p.3438-3445 (1976)

H. Gould, J. Tobochnik, "An Introduction to Computer Simulation Methods", Addison-Wesley Publishing (1988)

J. M. Ziman, "Models of disorder (The theoretical physics of homogeneously disordered systems)", Cambridge University Press, London (1979)

А. Л. Эфрос, "Физика и геометрия беспорядка" (библиотека "Квант"), Наука, Москва, (1982)

spausdinti