PL 
EnglishDomyślny
Українська🌐 Graf losowy — gigantyczna składowa i przejście fazowe
Zbuduj losowy graf Erdősa-Rényiego G(n,p): gdy średni stopień <k>=(n-1)p przekracza 1, nagle wyłania się gigantyczna spójna składowa — ostre przejście fazowe w sieci.
O tej symulacji
Ta symulacja buduje losowy graf Erdősa-Rényiego G(n,p): dla każdej pary spośród n wierzchołków krawędź jest dodawana niezależnie z prawdopodobieństwem p. Przeszukiwanie wszerz następnie dzieli graf na spójne składowe, kolorując największą na czerwono, a układ skierowany siłami (sprężynowe przyciąganie na krawędziach, elektrostatyczne odpychanie między wszystkimi wierzchołkami) rozmieszcza graf tak, by jego struktura stała się widoczna. Wykres na żywo śledzi udział składowej olbrzymiej względem p i oznacza teoretyczny próg krytyczny pc = 1/(n−1) linią przerywaną, dzięki czemu można obserwować przejście fazowe w czasie rzeczywistym, a nie tylko o nim czytać.
🔬 Co przedstawia
Gdy podnosisz p ponad próg krytyczny pc = 1/(n−1), wiele małych, drzewiastych składowych nagle łączy się w jedną olbrzymią spójną składową obejmującą makroskopowy ułamek wszystkich n wierzchołków. Panel informacyjny podaje bieżący średni stopień <k> = (n−1)p, liczbę oddzielnych składowych, rozmiar składowej olbrzymiej oraz jej udział w całym grafie, podczas gdy wykres w lewym dolnym rogu śledzi zmierzony udział olbrzymiej składowej względem teoretycznej krzywej S = 1 − exp(−<k>S).
🎮 Jak korzystać
Przeciągnij suwak n (20–200), by ustawić liczbę wierzchołków, oraz suwak p (0–1), by ustawić prawdopodobieństwo krawędzi. Powoli przesuwaj p przez podświetlony próg, by obserwować, jak izolowane skupiska łączą się w jedną, wyróżnioną na czerwono olbrzymią składową. Pauza zatrzymuje układ skierowany siłami, dzięki czemu można obejrzeć bieżące rozmieszczenie, a Reset generuje nowy losowy graf z tymi samymi n i p.
💡 Czy wiesz, że?
Przejście składowej olbrzymiej jest matematycznie tym samym zjawiskiem co perkolacja wiązań na grafie pełnym i pojawia się daleko poza teorią grafów: epidemia staje się samopodtrzymująca się, gdy jej liczba reprodukcji R₀ przekracza 1 — dokładnie ten sam próg warunkowy co przekroczenie 1 przez <k> tutaj.
Najczęściej zadawane pytania
Jakiego modelu grafu losowego używa ta symulacja?
Implementuje klasyczny model Erdősa-Rényiego G(n,p). Przy n wierzchołkach każda z n(n−1)/2 możliwych krawędzi jest dołączana niezależnie z prawdopodobieństwem p, generowana przez pojedynczą pętlę losującą liczbę dla każdej pary. Nie ma tu dołączania preferencyjnego ani przełączania — każda krawędź to niezależny rzut monetą, co czyni próg składowej olbrzymiej matematycznie klarownym.
Jak symulacja znajduje spójne składowe?
Po wygenerowaniu krawędzi kod uruchamia przeszukiwanie wszerz (BFS) z każdego nieodwiedzonego wierzchołka: eksploruje wszystkie wierzchołki osiągalne przez istniejące krawędzie warstwa po warstwie za pomocą kolejki, oznaczając każdy identyfikatorem składowej. Powtarzanie tego z dowolnego pozostałego nieodwiedzonego wierzchołka dzieli cały graf na składowe w czasie O(n + m). Największa wynikowa składowa jest wyróżniana na czerwono jako składowa olbrzymia.
Co decyduje o tym, czy powstanie składowa olbrzymia?
Kontrolującą wielkością jest średni stopień <k> = (n−1)·p, pokazywany na żywo w panelu informacyjnym. Poniżej wartości krytycznej <k> = 1 (równoważnie p poniżej pc = 1/(n−1)) graf pozostaje rozdrobniony na małe składowe o rozmiarze O(log n). Powyżej tej wartości powstaje pojedyncza olbrzymia składowa, której udział S wszystkich wierzchołków spełnia samospójne równanie S = 1 − exp(−<k>S), które symulacja rozwiązuje numerycznie i wykreśla obok zmierzonych danych.
Co dokładnie robi układ skierowany siłami?
Jest to element czysto kosmetyczny, niebędący częścią samego modelu grafu losowego: każda para wierzchołków odpycha się jak naładowane cząstki (odpychanie odwrotnie proporcjonalne do kwadratu odległości), każda krawędź działa jak sprężyna ściągająca swoje dwa końce do długości spoczynkowej, a słaba siła ciągnie wszystkie wierzchołki w stronę środka płótna. Iterowanie tych sił w każdej klatce pozwala połączonym skupiskom oddalać się od niepołączonych, dzięki czemu wyłaniająca się składowa olbrzymia staje się wizualnie oczywista, a nie tylko raportowana liczbowo.
Czy model Erdősa-Rényiego jest realistyczny dla rzeczywistych sieci?
Zwykle nie. Rzeczywiste sieci — grafy społeczne, sieć WWW, sieci energetyczne — mają zwykle rozkłady stopni z ciężkim ogonem (prawo potęgowe), wysokie klastrowanie i strukturę społeczności, czego G(n,p) nie generuje, ponieważ każda krawędź ma tu dokładnie takie samo, niezależne prawdopodobieństwo. Bardziej realistyczne alternatywy obejmują model dołączania preferencyjnego Barabásiego-Alberta oraz model małego świata Wattsa-Strogatza, ale Erdős-Rényi pozostaje podstawowym matematycznym punktem odniesienia, z którym porównuje się te bogatsze modele.