| | 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 - 5 / 5
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: 760; Prenosov: 102
.pdf Celotno besedilo (683,78 KB)

2.
Distributivna mreža na množici popolnih prirejanj ravninskega dvodelnega grafa
Mateja Trbovc, 2015, diplomsko delo

Opis: Glavna tema diplomskega dela je, kako priti do distributivne mreže na množici popolnih prirejanj, ravninskega dvodelnega grafa. V drugem poglavju spoznamo osnovne lastnosti grafov. Posebej se poglobimo v dvodelne ravninske grafe. Spomnimo se pojma urejenosti. Izpostavimo pojma delno urejena množica in distributivna mreža. Vse to potrebujemo v nadaljevanju diplomskega dela. Bistvo diplome se začne v tretjem poglavju, kjer definiramo resonančne grafe R(G) in usmerjene resonančne grafe ali digrafe R(G). Za vpeljavo le-teh moramo definirati popolno prirejanje oziroma 1-faktorje ter simetrično razliko med njimi. V četrtem poglavju govorimo o enotski dekompoziciji, kjer podrobneje spoznamo dekompozicijo gozda in ravnine. V predzadnjem poglavju vpeljemo delno urejeno množico kot množico popolnih prirejanj. Za konec sledi rezultat, o tem kako s pomočjo delno urejene množice M(G) in distributivne mreže pridemo do Hassejevega diagrama za končne distributivne mreže. Ta pa je v bijektivnem odnosu z resonančnim digrafom. Torej je distributivna mreža rezultat povezave resonančnih grafov in urejenosti
Ključne besede: distributivna mreža, delno urejena množica, popolno prirejanje, Z-transformirani graf, ravninski dvodelen graf, Hassejev diagram, povezani graf, dvodelni graf, ravninski graf, drevo, gozd
Objavljeno: 21.04.2016; Ogledov: 606; Prenosov: 40
.pdf Celotno besedilo (942,17 KB)

3.
Characterizing posets for which their natural transit functions coincide
Boštjan Brešar, Manoj Changat, Sandi Klavžar, Joseph Mathews, Antony Mathews, Prasanth G. Narasimha-Shenoi, 2009, izvirni znanstveni članek

Opis: Standardna tranzitna funkcija delno urejene množice ▫$P$▫ je funkcija ▫$T_P$▫, ki vsakemu paru primerljivih elementov priredi interval med njima, za neprimerljiva elementa ▫$x,y$▫ pa je ▫$T_P(x,y) = {x,y}$▫. Na tri načine, tudi s prepovedanimi delno urejenimi podmnožicami, okarakteriziramo tiste delno urejene množice, v katerih standardna tranzitna funkcija sovpada s tranzitno funkcijo najkrajših poti njenega grafa pokritij-neprimerljivosti.
Ključne besede: matematika, teorija grafov, tranzitna funkcija, rangirana delno urejena množica, temeljni graf, geodetski interval, interval induciranih poti, mathematics, graph theory, transit function, ranked poset, underlying graph, geodesic interval, induced-path interval
Objavljeno: 10.07.2015; Ogledov: 503; Prenosov: 59
URL Povezava na celotno besedilo

4.
Cover-incomparability graphs of posets
Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, Joseph Mathews, Antony Mathews, 2008, izvirni znanstveni članek

Opis: Vpeljemo graf pokritij-neprimerljivosti (ki mu na kratko rečemo CI-graf), katerega množica povezav je unija množic povezav grafa neprimerljivosti in grafa pokritja dane delno urejene množice. S pomočjo prepovedanih izometričnih delno urejenih podmnožic, okarakteriziramo tiste delno urejene množice, katerih CI-graf je tetiven (razdaljno-hereditaren, ptolemajski) in predlagamo splošen pristop k obravnavi CI-grafov. Predstavimo tudi več odprtih problemov.
Ključne besede: matematika, teorija grafov, delno urejena množica, temeljni graf, tranzitna funkcija, tetiven graf, razdaljno-hereditaren graf, mathematics, graph theory, poset, underlying graph, transit function, chordal graph, distance-hereditary graph, claw
Objavljeno: 10.07.2015; Ogledov: 306; Prenosov: 55
URL Povezava na celotno besedilo

5.
Cover-incomparability graphs and chordal graphs
Boštjan Brešar, Manoj Changat, Tanja Gologranc, Joseph Mathews, Antony Mathews, 2010, izvirni znanstveni članek

Opis: Problem prepoznavanja grafov pokritij-neprimerljivosti (to je grafov, ki jih dobimo iz delno urejenih množic kot povezavno unijo njihovega grafa pokritij in grafa neprimerljivosti) je NP-poln v splošnem, kot so dokazali v [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], medtem ko je na primer očitno polinomski v razredu dreves. V tem članku se osredotočimo na razrede tetivnih grafov in dokažemo, da je vsak graf pokritij-neprimerljivosti, ki je tetiven graf, kar graf intervalov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf, oziroma razcepljeni graf in tudi okarakteriziramo grafe pokritij-neprimerljivosti med bločnimi, oziroma razcepljenimi grafi. Slednji karakterizaciji dasta tudi linearen algoritem za prepoznavanje bločnih, oziroma razcepljenih grafov, ki so grafi pokritij-neprimerljivosti.
Ključne besede: matematika, teorija grafov, delno urejena množica, temeljni graf, tetiven graf, razcepljen graf, bločni graf, mathematics, graph theory, poset, underlying graph, chordal graph, split graf, block graph
Objavljeno: 10.07.2015; Ogledov: 447; Prenosov: 50
URL Povezava na celotno besedilo

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