PL 
EnglishDomyślny
Українська🕸️ Perkolacja w sieci — próg gigantycznej składowej
Dodawaj losowe krawędzie między węzłami i obserwuj wyłanianie się gigantycznej składowej spójnej przy p_c = 1/N. Zobacz ostre przejście fazowe Erdősa-Rényiego.
O tej symulacji
Ta symulacja buduje losowy graf Erdősa-Rényiego na N wierzchołkach, dodając krawędzie po jednej, każdą losowaną jednostajnie z potasowanej listy wszystkich możliwych par wierzchołków. Struktura Union-Find (Disjoint Set Union) z kompresją ścieżek i unią według rangi śledzi spójne składowe w czasie niemal stałym w miarę pojawiania się krawędzi. Wykres fazowy na żywo przedstawia udział składowej olbrzymiej S względem średniego stopnia ⟨k⟩ = 2M/N, nakładając bieżący stan symulacji na teoretyczną krzywą S = 1 − e^(−⟨k⟩S). Próg krytyczny znajduje się dokładnie przy ⟨k⟩ = 1, gdzie tempo wzrostu największej składowej gwałtownie zmienia charakter.
🔬 Co przedstawia
N wierzchołków (50–300) połączonych losowo wybieranymi krawędziami, dodawanymi po jednej, po dziesięć lub w sposób ciągły przez Odtwórz. Każdy wierzchołek jest kolorowany według tego, do której spójnej składowej należy; największa składowa (staje się „składową olbrzymią”, gdy powstanie) jest wyróżniona na niebiesko. Panel boczny wykreśla S względem ⟨k⟩ na tle teoretycznej krzywej i oznacza punkt krytyczny ⟨k⟩ = 1 linią przerywaną, pozwalając obserwować przejście fazowe na żywo.
🎮 Jak korzystać
Ustaw liczbę wierzchołków N i docelowy średni stopień ⟨k⟩ suwakami — przesunięcie ⟨k⟩ w górę natychmiast dodaje krawędzie, przesunięcie w dół wyzwala pełny reset. Użyj Krok +1 krawędź lub Dodaj 10 krawędzi dla precyzyjnej kontroli, lub naciśnij Odtwórz, by strumieniować krawędzie w sposób ciągły z wybraną prędkością. Obserwuj, jak liczba krawędzi M, średni stopień ⟨k⟩, udział składowej olbrzymiej S i liczba składowych aktualizują się na żywo w miarę łączenia się małych skupisk.
💡 Czy wiesz, że?
Model Erdősa-Rényiego, wprowadzony przez Pála Erdősa i Alfréda Rényiego w latach 1959–60, był jedną z pierwszych rygorystycznych demonstracji, że struktury losowe mogą przechodzić gwałtowne przejście fazowe: poniżej ⟨k⟩ = 1 każda składowa jest logarytmicznie mała, ale w chwili przekroczenia przez ⟨k⟩ wartości 1 pojedyncza składowa nagle obejmuje skończony ułamek całego grafu — bez żadnej takiej składowej istniejącej tuż poniżej progu.
Najczęściej zadawane pytania
Co dokładnie jest losowane w tej symulacji?
Symulacja wstępnie tasuje pełną listę wszystkich możliwych par wierzchołków (za pomocą tasowania Fishera-Yatesa), a następnie odsłania je po jednej jako krawędzie. Jest to równoważne modelowi Erdősa-Rényiego G(N,M), w którym dokładnie M krawędzi jest wybieranych jednostajnie losowo spośród N(N−1)/2 możliwych par, zamiast dołączania każdej krawędzi niezależnie z prawdopodobieństwem p — obie formuły zbiegają dla dużych N.
Jak symulacja tak szybko wykrywa składową olbrzymią?
Wykorzystuje strukturę danych Union-Find (Disjoint Set Union). Każdy wierzchołek zaczyna we własnej składowej; dodanie krawędzi wywołuje union(a,b), które łączy dwie składowe, dołączając korzeń mniejszego drzewa do korzenia większego. Dzięki kompresji ścieżek (spłaszczaniu drzewa przy find) i unii według rangi obie operacje działają w czasie niemal stałym, więc śledzenie składowych dla setek wierzchołków i tysięcy krawędzi pozostaje szybkie nawet w czasie rzeczywistym.
Co dokładnie kontroluje suwak średniego stopnia ⟨k⟩?
⟨k⟩ to średnia liczba krawędzi na wierzchołek, obliczana jako 2M/N, gdzie M to bieżąca liczba krawędzi. Suwak ustawia docelowe ⟨k⟩; symulacja oblicza wtedy docelową liczbę krawędzi M = round(⟨k⟩·N/2) i albo dodaje krawędzie, by ją osiągnąć (jeśli zwiększasz ⟨k⟩), albo wykonuje pełny reset i buduje graf od nowa (jeśli je zmniejszasz, ponieważ krawędzi nie można stopniowo usuwać).
Dlaczego składowa olbrzymia pojawia się tak nagle wokół ⟨k⟩ = 1?
Poniżej ⟨k⟩ = 1 graf losowy jest lasem małych drzewiastych skupisk, każde o rozmiarze O(log N), i żadne z nich nie może urosnąć do skończonego ułamka grafu. Gdy ⟨k⟩ przekracza 1, proces gałęziowy opisujący wzrost skupisk staje się superkrytyczny: skupisko ma teraz średnio więcej niż jeden nowy wierzchołek do rozbudowy na każdym kroku, więc wzrost jednego skupiska kumuluje się, aż pochłonie ułamek S wszystkich N wierzchołków, spełniając S = 1 − e^(−⟨k⟩S). To prawdziwe przejście fazowe drugiego rodzaju, a nie tylko płynny trend.
Czy wizualne rozmieszczenie wierzchołków wpływa na to, które wierzchołki trafiają do składowej olbrzymiej?
Nie. Pozycje na ekranie są czysto kosmetyczne, generowane przez prosty układ odpychania skierowany siłami (lub układ siatki dla dużych N), wyłącznie po to, by wierzchołki wizualnie się nie nakładały. To, które wierzchołki dołączają do składowej olbrzymiej, jest wyznaczane wyłącznie przez losową kolejność krawędzi i spójność grafu — pozycja na ekranie nie niesie żadnej informacji o stopniu ani przynależności do składowej.