Akademska digitalna zbirka SLovenije - logo
ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Spektralna metoda za določanje pasovnosti grafa : diplomsko delo : Prešernova nagrada študentom
    Juvan, Martin
    V diplomskem delu je obravnavan problem določanja pasovnosti grafov. Najprej je vpeljana posplošitev pasovnosti, ki jo imenujemo ▫$p$▫-pasovnost. Opravljen je pregled važnejših rezultatov s tega ... področja, izpeljanih pa je tudi nekaj povezav med različnimi pasovnostmi. V nadaljevanju je vpeljana še Laplaceova matrika grafa, dokazane so nekatere znane lastnosti te matrike in njenega spektra, poudarek pa je predvsem na prikazu pomembnosti druge najmanjše lastne vrednosti ▫$\lambda_2$▫ te matrike. Iz izpeljanih lastnosti spektra Laplaceove matrike dobimo zanimive "spektralne" ocene za nekatere ▫$p$▫-pasovnosti, ▫$p\in\{1,2,\infty\}$▫. Omenjena je tudi prerezna pasovnost. Prikazan je še hevristični algoritem za iskanje približka k optimalni označitvi grafa s pomočjo lastnih vrednosti ▫$\lambda_2$▫ pripadajočega lastnega vektorja ▫$x^{(2)}$▫. Opravljena je kratka analiza napake algoritma, iz izračunanih primerov pa ugotovimo, da je njegovo obnašanje zadovoljivo.
    Type of material - undergraduate thesis
    Publication and manufacture - Ljubljana : [M. Juvan], 1989
    Language - slovenian
    COBISS.SI-ID - 3534937

    Link(s):

    http://www.matknjiz.si/diplome/uni/u/1989/10668-394.pdf

Library/institution City Acronym For loan Other holdings
FMF and IMFM, Mathematical Library, Ljubljana Ljubljana MAKLJ reading room 2 cop.
University of Primorska University Library Koper - Capodistria UPUK reading room 1 cop.
loading ...
loading ...
loading ...

Shelf entry