VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Graph Laplacians
    Mohar, Bojan, 1956-
    Lastne vrednosti Laplaceove matrike grafa so v tesni povezavi z raznimi kombinatoričnimi lastnostmi grafa. Dajejo nam pomembno informacijo o nekaterih invariantah grafa, ki jih je težko izračunati ... ali oceniti. Mednje sodijo količine, ki so definirane na osnovi širjenja grafa ali delitve vozlišč na dve ali več skupin. Najmanjšo in največjo lastno vrednost lahko izrazimo kot problem kvadratične optimizacije. Izkaže se, da nam pravšnjo posplošitev ponudi semidefinitno programiranje, kjer lahko uporabimo teorijo dualnosti in tako pridemo do pomembnih uporab. Tak primer je podrobneje obdelan za problem maksimalnega prereza in delno za trgovskega potnika. Vsa teorija je prikazana za grafe z uteženimi povezavami im tako naravno pridemo tudi do probleme slučajnih sprehodov po grafu, saj se da prehodno matriko slučajnega sprehoda izraziti kot Laplaceovo matriko uteženega grafa.
    Vir: Topics in algebraic graph theory (Str. 113-136)
    Vrsta gradiva - članek, sestavni del
    Leto - 2004
    Jezik - angleški
    COBISS.SI-ID - 13209433

Vnos na polico