| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 1 / 1
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Primeri uporabe mostovnih grafov in njihovih posplošitev
Tanja Gologranc, 2013, doktorska disertacija

Opis: Mostovni grafi so zelo dobro raziskana družina grafov. Pojavljajo se na različnih področjih, ne samo diskretne matematike, na primer v geometrični teoriji grup. V disertaciji se ukvarjamo z različnimi problemi, povezanimi z mostovnimi grafi in njihovimi posplošitvami. Pokažemo, do so ti grafi uporabni tudi zunaj same teorije grafov, saj jih povežemo s teorijo kompleksov. Med drugim se ukvarjamo s povezavo teh grafov in določenih tipov konveksnosti v grafih in z uporabo mostovnih grafov v grafih, prirejenih delno urejenim množicam. Disertacija je sestavljena iz treh delov, pri čemer v vsakem delu prikažemo uporabnost mostovnih grafov na izbranem področju. V prvem delu vpeljemo in proučujemo bukolične komplekse, skupno posplošitev sistoličnih in CAT(0) kubičnih kompleksov. Bukolične komplekse proučujemo z vidika teorije grafov, topološkega vidika in iz perspektive geometrijske teorije grup. Okarakteriziramo jih preko določenih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več že znanih rezultatov. Prav tako dokažemo, da so bukolični kompleksi skrčljivi in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti. V drugem delu posplošene mostovne grafe obravnavamo vzporedno s 3-Steinerjevo konveksnostjo. In sicer dokažemo, da so grafi $G$, v katerih so j-krogle g_3-konveksne za vsak j ≥ 1, natanko grafi, ki ne vsebujejo hiše niti grafov K_{2,3} in W_4^- kot induciranih podgrafov, in je vsak cikel v G, dolžine vsaj šest, dobro premostljiv. Okarakteriziramo torej grafe z g_3-konveksnimi kroglami. V tretjem delu disertacije usmerimo pozornost na grafe pokritij-neprimerljivosti delno urejenih množic (C-I grafe) in iščemo njihovo povezavo z mostovnimi grafi. Pokažemo, da v razredu C-I grafov sovpada kar nekaj različnih grafovskih družin. In sicer, v razredu C-I grafov ni razlike med mostovnimi grafi, tetivnimi grafi in grafi intervalov. Ker je problem prepoznavanja grafov pokritij-neprimerljivosti v splošnem NP-poln, se osredotočimo na določene razrede mostovnih grafov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf oziroma razcepljeni graf. Med drugim okarakteriziramo grafe pokritij-neprimerljivosti tako med bločnimi oziroma razcepljenimi grafi kot med tetivnimi kografi. Slednje karakterizacije dajo tudi linearen algoritem za prepoznavanje bločnih oziroma razcepljenih grafov, oziroma tetivnih kografov, ki so grafi pokritij-neprimerljivosti.
Ključne besede: kartezični produkt, delno urejena množica, retrakt, amalgamacija, mostovni graf, Steinerjev interval, šibko modularen graf, graf pokritij-neprimerljivosti
Objavljeno: 22.04.2015; Ogledov: 757; Prenosov: 102
.pdf Celotno besedilo (683,78 KB)

Iskanje izvedeno v 0.05 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici