Náhodný graf

V matematice rozumíme pojmem náhodný graf specifickou distribuci na konečných grafech. Tato distribuce je typicky zadána na grafech na pevné množině vrcholů. Proto si náhodný graf lze představit jako danou množinu vrcholů do níž jsou „náhodně přidány hrany". Studium náhodných grafů iniciovali v roce 1959 nezávisle Edgar Gilbert a Paul Erdős a Alfréd Rényi. Původní článek Erdőse a Rényiho byl výrazně obsažnější než Gilbertův a proto se modelu, který zavedli (a jim příbuznému), říká Erdős-Rényi model náhodných grafů. Tento model je v současnosti jednou z nejstudovanějších náhodných diskrétních struktur v matematice (spolu s modely statistické fyziky, jako například Isingův model). Náhodné grafy se používají v informatice, fyzice, biologii a dalších oborech k modelování náhodně vznikajících interakcí. V těchto aplikacích stejně jako v matematické teorii náhodných grafů se zkoumá zejména asymptotické chování grafů na limitně velkém počtu vrcholů.

Erdős-Rényi modely G(n,p) a G(n,m)

Pod pojmem Erdős-Rényi model se rozumí buď model G(n,p) nebo velmi podobný model G(n,m). Zatímco model G(n,p) je z matematického hlediska ve většině případů jednodušeji analyzovatelný, byl to model G(n,m), který byl popsán v původním článku Erdőse a Rényiho z roku 1959. Gilbert ve svém článku popsal model G(n,p).

Pro přirozené číslo n a číslo p, 0≤p≤1, je můžeme definovat náhodný graf G(n,p) jako graf na množině vrcholů {1,…,n} do kterého je každý možný pár vrcholů vložen jako hrana s pravděpodobností p (a tyto hrany jsou vloženy nezávisle). Náhodný graf G(n,0.5) odpovídá uniformní distribuci na množině všech grafů s množinou vrcholů {1,…,n}.

Pro přirozené číslo n a m, ${\textstyle 0\leq m\leq {n \choose 2}}$, definujeme náhodný graf G(n,m) jako graf na množině vrcholů {1,…,n} do kterého je vložena náhodná množina m hran. Modely G(n,p) a G(n,m) pro ${\textstyle m=p{n \choose 2}}$ se chovají přibližně pomalu, neboť realizace náhodného grafu G(n,p) bude mít podle zákona velkých čísel s velkou pravděpodobností přibližně

${\textstyle p{n \choose 2}}$ hran.

Mezi nejdůležitější oblasti v teorii náhodných grafů patří studium prahových funkcí monotónních grafových vlastností. Místo formální definice uveďme příklad. Pro libovolné $\epsilon >0$ platí, že pro ${\textstyle p_{1}={\frac {(1-\epsilon )\log n}{n}}}$, náhodný graf $G(n,p_{1})$ asymptoticky skoro jistě není hamiltonovský, zatímco pro $p_{2}={\frac {(1+\epsilon )\log n}{n}}$, náhodný graf $G(n,p_{2})$ asymptoticky skoro jistě hamiltonovský je. Jinak řečeno, pro n jdoucí do nekonečna je limita pravděpodobnosti, že je $G(n,p_{1})$ hamiltonovský 0, zatímco ta stejná limita je 1 pro ${\textstyle G(n,p_{2})}$. Podobná prudká změna chování se projevuje vzhledem k mnoha přirozeným grafovým vlastnostem a je popsána Friedgutovou větou.

Podobně jako v uvedeném příkladu hamiltonovskosti se ve většině praktických modelů stejně jako ve většině matematické teorie uvažuje režim kdy p jde k nule podle zvolené funkce v n.

Vlastnosti Erdős-Rényi náhodných grafů inspirovaly koncept kvazináhodných grafů.

K rozvoji teorie náhodných grafů přispěli zejména Paul Erdős, Béla Bollobás a Alan Frieze.

Dolní odhad Ramseyova čísla

Nejdůležitější kvantitativní otázkou v Ramseyově teorii je zkoumání čísla R(k,k). To je definováno jako minimální číslo r takové, že každý graf na r vrcholech obsahuje kliku nebo nezávislou množinu velikosti alespoň r. Erdős implicitním použitím technik tehdy ještě neexistující teorie grafů ukázal v roce 1947, že $R(k,k)>2^{k/2}$. (Nepatrně přesnější odhad stejnou metodou je možný. Za sedm dekád od Erdősova důkazu byl před obrovské úsilí tento dolní odhad na R(k,k) vylepšen pouze málo.) Přesněji, Erdősův důkaz může být chápán jako důkaz tvrzení, že pro $n=\lceil 2^{k/2}\rceil$ platí, že G(n,0.5) s kladnou pravděpodobností neobsahuje ani kliku ani nezávislou množinu velikosti k. Tato interpretace důkazu je jedním z nejzákladnějších aplikací pravděpodobnostní metody. Díky podobným aplikacím jsou náhodné grafy nejužitečnější třídou objektů pro aplikace pravděpodobnostní metody.

Jiné modely

Jiné modely náhodných grafů zahrnují model náhodných stromů, model náhodných regulárních grafů a Barabási–Albertův model náhodných bezškálových sítí. Barabási–Albertův model v mnoha případech může lépe vystihovat reálný model (sociální sítě, epidemiologie, ...). Náhodné grafy je možno vnímat jako speciální třídu perkolačních modelů.

Podobným způsobem jako náhodné grafy lze zavést náhodné k-uniformní hypergrafy a další náhodné struktury.

Reference

Autoritní data	NKC: ph664004 BNF: cb12288320t (data) LCCN: sh85111348 NLI: 987007563131005171

Portály: Matematika