Apie tolygių atsitiktinių sankirtų grafų hamiltoniškumą

Santrauka

Darbe nagrinėjamas Hamiltono ciklo egzistavimas tolygiame atsitiktiniame sankirtų grafe G_n,m,d. Tai grafas, turintis n viršnių. Kiekviena viršnė iš duotos m raktų aibės atsitiktinai ir nepriklausomai išsirenka d raktų rinkinį. Dvi viršnės jungiamos briauna, jei jos turi bent vieną bendrą raktą. Darbe parodoma, jog su tikimybe, artėjančia prie 1, grafas G_n,m,d turi Hamiltono ciklą, jeigu n = 2^-1m(ln m + ln ln m + ω(m)), kur ω(m) → +∞, kai m → ∞.