DIKUL - logo
Univerza na Primorskem Univerzitetna knjižnica - vsi oddelki (UPUK)
  • Algoritmi in ovire za vlaganje grafov v torus : doktorska disertacija
    Juvan, Martin
    Disertacija sodi na področje topološke teorije grafov, tesno pa je povezana tudi s teorijo algoritmov na grafih. V drugem poglavju so predstavljeni nekateri teoretični in algoritmični rezultati o ... izbranem računskem modelu, o povezanosti grafov, o (kombinatornem) opisu vložitev grafov v ploskve in o celični širini vloženih grafov. Tretje poglavje podaja definicije osnovnih pojmov, ki jih potrebujemo pri izbranem pristopu k vlaganju grafov v ploskve. Vpeljani so pojmi, kot so most grafa glede na podgraf, lokalni in globalni most, vložitvena shema, nabor vložitvenih shem, bistveni podgraf, itn. Izpeljane so tudi njihove osnovne lastnosti. V četrtem poglavju obravnavamo posebno vrst razširitvenih problemov; 2 -omejene enostavne celične razširitvene probleme. Opisan je linearni algoritem za reševanje takih razširitvenih problemov, opravljena pa je tudi natančna analiza možnih ovir. Rezultati iz tega poglavja predstavljajo osnovo za linearna algoritma za vlaganje grafov v projektivno ravnino in v torus, ki sta opisana v zadnjih dveh poglavjih. Iz dokazov pravilnosti obeh algoritmov sledi, da za projektivno ravnino in za torus obstaja le končno mnogo prepovedanih podgrafov. V petem poglavju je dokazana tudi zveza med celično širino vložitev v projektivno ravnino in orientabilnim rodom grafa, opisan pa je tudi algoritem, ki v času ▫${\cal O}(kn)$▫ odloči, ali ima v projektivno ravnino vloženi graf z ▫$n$▫ točkami celično širino manjšo od ▫$k$▫. Podan je tudi kratek pregled nekaterih lastnosti prepovedanih podgrafov za projektivno ravnino. V zadnjem poglavju so v opisu linearnega algoritma za iskanje vložitev grafov v torus združeni glavni rezultati iz prejšnjih poglavij. Dodatno so v zadnjem razdelku povzeti znani rezultati o prepovedanih podgrafih za torus in opisani vsi tisti prepovedani minorji za torus, ki imajo vložitev v projektivno ravnino. Ti minorji so bili poiskani s pomočjo računalnika.
    Vrsta gradiva - disertacija ; neleposlovje za odrasle
    Založništvo in izdelava - Ljubljana : [M. Juvan], 1995
    Jezik - slovenski
    COBISS.SI-ID - 3968345

Signatura – lokacija, inventarna št. ... Status izvoda Rezervacija
Univerzitetna knjižnica skladišče
dis JUVAN MARTIN Algoritmi
IN: 04000000310 Univerzitetna knjižnica skladišče
dis JUVAN MARTIN Algoritmi
IN: 04000000310 		prosto - za čitalnico
loading ...
loading ...
loading ...

Vnos na polico