Search the digital library catalog

Abstract: Magistrsko delo obravnava klasični problem “no-three-in-line” in dve njegovi pospološitvi. Klasični problem “no-three-in-line” je, poiskati največje možno število točk, ki jih lahko postavimo na n × n mrežo tako, da nobene tri med njimi ne bodo ležale v ravni črti. Posplošitvi, ki ju bomo obravnavali, sta problem “no-three-in-line” v 3D in problem splošne lege v teoriji grafov. Problem “no-three-in-line” v 3D je, poiskati največje možno število točk, ki jih lahko postavimo na n × n × n mrežo tako, da nobene tri med njimi ne bodo ležale v ravni črti. Problem splošne lege v teoriji grafov pa je, poiskati največjo množico vozlišč, za katero bo veljalo, da nobena tri vozlišča iz te množice ne ležijo na skupni najkrajši poti. V prvem poglavju je navedenih nekaj definicij in pomembnih rezultatov iz področja diskretne matematike in teorije števil, ki jih bomo potrebovali v nadaljnjih poglavjih. V drugem poglavju predstavimo klasični problem “no-three-in-line”, pokažemo koliko je pričakovana zgornja meja za število nekolinearnih točk na n × n mreži pri velikih n in vidimo, da lahko na n × n mrežo zmeraj postavimo n nekolinearnih točk. V tretjem poglavju predstavimo problem “no-three-in-line” v 3D, pokažemo, kako je ta problem povezan s 3D-sliko grafa Kn in povemo, kakšno je pričakovano število nekolinearnih točk na n × n × n mreži. V zadnjem poglavju predstavimo problem splošne lege v teoriji grafov ter njegove zgornje in spodnje meje. Zgornje meje so podane na podlagi različnih izometričnih pokritij grafov, spodnje pa dobimo tako, da množice v splošni legi povežemo s premerom grafa in njegovim pakiranjem.
Keywords: problem “no-three-in-line”, splošna lega, celoštevilska mreža, 3D-slika grafa, izometrično pokritje, izometrični podgraf
Published in DKUM: 15.03.2019; Views: 1281; Downloads: 124
Full text (1,06 MB)

Abstract: Doktorska disertacija obravnava predvsem resonančne grafe tubulenov in fulerenov. V prvem poglavju so predstavljeni nekateri že znani rezultati o resonančnih grafih, prav tako pa je podana struktura doktorske disertacije. V naslednjem poglavju so definirani nekateri osnovni pojmi teorije grafov, ki jih potrebujemo v preostalih poglavjih. V tretjem poglavju so predstavljene tri pomembne družine kemijskih struktur, to so benzenoidni sistemi, tubuleni in fulereni. Omenjene družine predstavljajo molekule, ki jih imenujemo benzenoidni ogljikovodiki, ogljikove nanocevke in fulereni. V četrtem poglavju je najprej pokazana povezava med Kekuléjevimi strukturami določene molekule ter popolnimi prirejanji ustreznega kemijskega grafa. V nadaljevanju poglavja je definiran resonančni graf benzenoidnega sistema, tubulena in fulerena. Glavni namen tega koncepta je modeliranje interakcij med posameznimi Kekuléjevimi strukturami molekule. Nato se lotimo raziskovanja osnovnih lastnosti resonančnih grafov. Pokazano je, da je resonančni graf tubulena ali fulerena dvodelni graf, vsaka njegova povezana komponenta pa je bodisi pot bodisi graf z ožino štiri. Prav tako dokažemo, da je 2-jedro vsake povezane komponente resonančnega grafa širokega tubulena ali fulerena, ki ni pot, vedno 2-povezan graf. Nato podamo primer neskončne družine tubulenov, katerih resonančni grafi niso povezani. Na koncu poglavja definiramo resonančni graf za katerikoli graf, ki je vložen na zaprto ploskev. Dokažemo tudi, da so taki resonančni grafi inducirani podgrafi hiperkock. V petem poglavju definiramo Zhang-Zhangov polinom, ki je namenjen štetju posebnih struktur, imenovanih Clarova pokritja. Dokazano je, da je Zhang-Zhangov polinom grafa, vloženega na zaprto ploskev, enak polinomu kock ustreznega resonančnega grafa. Ta rezultat posplošuje podobne rezultate za benzenoidne sisteme, tubulene in fulerene. Na koncu se ukvarjamo s strukturo distributivne mreže resonančnih grafov. Dokazano je, da je vsaka povezana komponenta resonančnega grafa tubulena graf pokritja neke distributivne mreže. Prav tako pokažemo, da je vsaka povezana komponenta resonančnega grafa tubulena medianski graf, njen graf blokov pa je pot. Nazadnje podamo primer fulerena, katerega resonančni graf ni graf pokritja nobene distributivne mreže.
Keywords: benzenoidni sistem, ogljikova nanocevka, tubulen, fuleren, resonančni graf, Z-transformirani graf, Clarovo pokritje, Zhang-Zhangov polinom, polinom kock, distributivna mreža, medianski graf, graf blokov, grafi na ploskvah
Published in DKUM: 09.01.2018; Views: 1721; Downloads: 282
Full text (1,40 MB)

Abstract: V diplomskem delu so obravnavani parakompaktni prostori. To so Hausdorffovi prostori za katere velja, da ima vsako njihovo odprto pokritje finejše lokalno končno odprto pokritje. V prvem delu so opisani osnovni pojmi, ki jih potrebujemo za razumevanje celotnega dela, nato sta opisani lokalna končnost in kompaktnost. V zadnjem poglavju so opisani parakompaktni prostori in njihove lastnosti. Spoznali bomo, kateri prostori so parakompaktni, prav tako bomo spoznali pojem particija enote in jo povezali s pojmom parakompaktnosti. Na koncu se bomo posvetili še nekaterim pokritjem kot sta zvezdno pokritje in baricentrično pokritje, ki pomagata pri prepoznavanju parakompaktnih prostorov.
Keywords: kompaktnost, parakompaktnost, finejše pokritje, lokalna končnost
Published in DKUM: 25.09.2014; Views: 1373; Downloads: 95
Full text (778,75 KB)

Abstract: Lindelöfovi prostori so regularni topološki prostori, katerih vsako odprto pokritje vsebuje števno podpokritje. Lindelöfova lastnost je poslošitev bolj znanega pojma kompaktnosti, ki zahteva obstoj končnega podpokritja. V diplomskem delu so zajete lastnosti Lindelöfovih prostorov, opisani so njihovi osnovni primeri in izreki. V prvem delu so navedeni osnovni pojmi, ki jih potrebujemo pri opisovanju Lindelöfovih prostorov. Drugi del obravnava pojem kompaktnosti. V tretjem delu je opisano kaj so Lindelöfovi prostori, njihove lastnosti, primeri in kaj velja za produkt Lindelöfovih prostorov. Na koncu se diplomsko delo dotakne še zgodovine Lindelöfovih prostorov. Končna ugotovitev kaže na to, da določene lastnosti kompaktnih prostorov veljajo tudi za Lindelöfove prostore. Na primer, da je vsak 2-števen prostor Lindelöfov in da je vsak Lindelöfov prostor normalen. Tudi zvezna preslikava ohranja Lindelöfovo lastnost, kar pa ne velja za produkt, saj niti produkt dveh Lindelöfovih prostorov ni nujno Lindelöfov.
Keywords: Lindelöf, kompaktnost, pokritje, podpokritje
Published in DKUM: 30.01.2014; Views: 1512; Downloads: 87
Full text (435,58 KB)

Abstract: Diplomsko delo obravnava vozliščno pokritje k-poti v grafih. Na začetku so predstavljeni osnovni pojmi teorije grafov, ki so potrebni za razumevanje nadaljne snovi. V nalogo so vključeni pojmi NP-polnost, regularni grafi in drevesa. Konec pa vključuje vozliščna pokritja k-poti za nekatere grafovske produkte. Za velikost najmanjšega vozliščnega pokritja glede na stopnjo vozlišča bodo določene zgornje in spodnje meje grafa. Izboljšani bosta zgornja in spodnja ocena za najmanjše možno število vozlišč v pokritju k-poti pri kartezičnem, krepkem in leksikografskem produktu.
Keywords: Vozliščno pokritje, NP-polnost, regularni graf, kartezični produkt, krepki produkt, leksikografski produkt.
Published in DKUM: 22.04.2013; Views: 2323; Downloads: 220
Full text (287,73 KB)