Apie tolygių atsitiktinių sankirtų grafų hamiltoniškumą
Straipsniai
Mindaugas Bloznelis
Vilnius University
Irmantas Radavičius
Vilnius University
Publikuota 2010-12-21
https://doi.org/10.15388/LMR.2010.80
PDF

Reikšminiai žodžiai

atsitiktinis grafas
sankirtų grafas
Hamiltono ciklas
klasterizavimas

Kaip cituoti

Bloznelis M. ir Radavičius I. (2010) „Apie tolygių atsitiktinių sankirtų grafų hamiltoniškumą“, Lietuvos matematikos rinkinys, 51(proc. LMS), p. 443–447. doi: 10.15388/LMR.2010.80.

Santrauka

Darbe nagrinėjamas Hamiltono ciklo egzistavimas tolygiame atsitiktiniame sankirtų grafe Gn,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 Gn,m,d turi Hamiltono ciklą, jeigu n = 2-1m(ln m + ln ln m + ω(m)), kur ω(m) → +∞, kai m → ∞.

PDF
Kūrybinių bendrijų licencija

Šis kūrinys yra platinamas pagal Kūrybinių bendrijų Priskyrimas 4.0 tarptautinę licenciją.

Susipažinkite su autorių teisėmis žurnalo politikoje skiltyje Autorių teisės.