Svorinio grafo trumpiausiųjų kelių medžio empirinė analizė
Straipsniai
Mindaugas Bloznelis
Vilnius University
Irmantas Radavičius
Vilnius University
Publikuota 2008-12-21
https://doi.org/10.15388/LMR.2008.18118
PDF

Reikšminiai žodžiai

trumpiausių kelių medis
atsitiktinis svorinis grafas

Kaip cituoti

Bloznelis M. ir Radavičius I. (2008) „Svorinio grafo trumpiausiųjų kelių medžio empirinė analizė“, Lietuvos matematikos rinkinys, 48(proc. LMS), p. 338–342. doi: 10.15388/LMR.2008.18118.

Santrauka

Pilnojo grafo, turinčio n viršūnių briaunoms  e1,...,em priskiriame neneigiamus svorius X1 = X(e1), ..., Xm = X(em). Čia  m = (n/2). Trajektorijos ei1,ei2,...,eik ilgiu vadiname šią trajektoriją sudarančių briaunų svorių sumą Xi1 + ··· + Xik. Trajektoriją, jungiančią viršūnes u ir v, vadiname trumpiausi keliu tarp u ir v, jei nėra kitos trajektorijos, kurios ilgis būtų mažesnis. Darbe tiriamas medis, sudarytas iš trumpiausių kelių, vedančių iš fiksuotos viršūnės u į visas kitas grafo viršūnes. Tokį medį gauname pritaikę, pvz., Dijkstros algoritmą. Darbe nagrinėjamos statistinės trumpiausių kelių medžio savybės, kai svoriai parenkami atsitiktinai ir nepriklausomai vienas nuo kito. Tiriame medžio struktūros priklausomybę nuo atsitiktinių svorių tikimybinio skirstinio parametrų. 

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.