| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 110
First pagePrevious page12345678910Next pageLast page
1.
2.
POLNO ZASTRAŽENI GRAFI
Polona Pavlič, 2009, undergraduate thesis

Abstract: Množica X v grafu G je zastražena, če za vsako vozlišče iz GX v X obstaja enolično določeno vozlišče, preko katerega so razdalje do vozlišč iz X najkrajše. Diplomsko delo preučuje grafe, v katerih je vsaka konveksna množica grafa zastražena - polno zastražene grafe. Prva opazka glede teh grafov je, da morajo biti nujno dvodelni. S preprostim algoritmom, ki deluje v polinomskem času, lahko za poljuben (dvodelni) graf preverimo, ali je polno zastražen ali ne. Algoritem, ki temelji na zoženju preverjanja vseh konveksnih množic le na tiste, ki so konveksne lupine parov vozlišč, je predstavljen v 3. poglavju. Do prvih pravih primerov polno zastraženih grafov nas pripeljejo hiperkocke. Z nekaj ozadja iz teorije grafov lahko dokažemo tudi, da so medianski grafi natanko polno zastražene delne kocke. Iz znanih polno zastraženih grafov pa lahko nadalje s pomočjo nekaterih operacij nad grafi konstruiramo nove take. Hitro vidimo, da kartezični produkt ohranja polno zastraženost, prav tako je s konveksno amalgamacijo grafov. Iz danih polno zastraženih grafov prav take tvori tudi posplošena konveksna ekspanzija, nekaj več preglavic pa povzroča konveksna podvojitev, kjer so potrebne dodatne predpostavke. Polna zastraženost se ohranja le če konveksna množica, ki jo podvajamo, zadošča dodatnim predpostavkam podvojljivosti. Z znanjem o podvojitvi pa pridemo še do druge povezave dvodelnih in polno zastraženih grafov, namreč vsak dvodelni graf je izometrični podgraf nekega polno zastraženega grafa. Iz poljubnega povezanega dvodelnega grafa lahko tudi hitro, brez zgornjih operacij, dobimo polno zastražen graf - v vsako množico razbitja dodamo vozlišče, ki je sosednje z vsemi vozlišči iz druge množice razbitja (dvodelni dominator).
Keywords: Razdalja v grafu, dvodelni graf, konveksna množica grafa, zastražena množica
Published: 22.04.2009; Views: 3035; Downloads: 275
.pdf Full text (663,08 KB)

3.
KREPKO RAZDALJNO URAVNOTEŽENI GRAFI
Mihael Mihalič, 2009, undergraduate thesis

Abstract: V diplomskem delu sta obravnavana razreda razdaljno uravnoteženih in krepko razdaljno uravnoteženih grafov. Obravnavane so osnovne lastnosti teh grafov in pod kakšnimi pogoji standardni grafovski produkti ohranjajo lastnost biti (krepko) razdaljno uravnotežen.
Keywords: razdaljno uravnotežen graf, krepko razdaljno uravnotežen graf, kartezični produkt, leksikografski produkt, krepki produkt, direktni produkt
Published: 07.07.2009; Views: 2163; Downloads: 113
.pdf Full text (4,22 MB)

4.
Prireja mleka in krmna baza na družinskih kmetijah Kmetijske zadruge Šentjur
Lidija Mužerlin, 2009, undergraduate thesis

Abstract: Namen diplomskega dela je bil primerjati različna odkupna območja mleka po kvalitativnih lastnostih. Tako smo med seboj primerjali mleko odkupljeno na območju Kmetijske zadruge Šentjur, odkupnem območju Mlekarne Celeia in odkupljeno mleko celotnega območja Slovenije. Prireja mleka je v veliki meri odvisna tudi od prehrane krav, zato nas je zanimalo, kako imajo boljše družinske kmetije na območju Kmetijske zadruge Šentjur izravnane krmne obroke za krave molznice. Zbrali smo 36 mesečnih obračunov. Proučevali smo odkupljene količine mleka, vsebnost mikroorganizmov, skupno število somatskih celic ter vsebnost maščob in beljakovin za obdobje 2006 - 2008. Na obravnavanih kmetijah smo ugotovili dejansko sestavo krmnih obrokov. Krmne obroke smo ovrednotili na podlagi tabelarnih vrednosti. Živalim je bil skozi vso leto na voljo zimski krmni obrok na osnovi koruzne in travne silaže, sena ter dodatka koncentrirane krme. Molznice so bile ustrezno oskrbljene z energijo medtem, ko je bil pri beljakovinah ugotovljen primanjkljaj (6 % prebavljivih surovih beljakovin). Odkupljeno mleko iz obravnavanih območij se ni razlikovalo po bistvenih mikrobioloških kakovostnih postavkah.
Keywords: Ključne besede: odkupljeno mleko/ maščobe/ beljakovine/ mikroorganizmi/ somatske celice, /krmni obrok OP: 59 s., 16 pregl., 10 graf., 55 ref.
Published: 19.10.2009; Views: 2271; Downloads: 314 
(1 vote)
.pdf Full text (363,75 KB)

5.
METODA ZA PREŠTEVANJE POTI MED VRHOVI IN DOLINAMI BENZENOIDNEGA GRAFA
Ines Goger, 2009, undergraduate thesis

Abstract: Glavno področje diplomskega dela je metoda za preštevanje poti med vrhovi in dolinami benzenoidnega grafa. Predstavljena je uporaba teorije grafov v kemiji in povezava med kemijo in matematiko. V uvodnih poglavjih diplomskega dela so zato predstavljeni osnovni pojmi teorije grafov in kemijski pojmi, ki so potrebni za razumevanje nadaljne snovi. V nadaljevanju so podane osnovne lastnosti in definicije benzenoidnih grafov. Priložena je programska koda metoda za preštevanje poti med vrhovi in dolinami v benzenoidnem grafu. Na koncu so za lažje razumevanje podani različni primeri z rešitvami.
Keywords: graf, vrh, dolina, benzenoidni sistem, benzenoidni graf, Kekulejeve strukture, 1-faktor
Published: 25.11.2009; Views: 2185; Downloads: 60
.pdf Full text (7,85 MB)

6.
PROBLEM KITAJSKEGA POŠTARJA S PRIORITETNIMI VOZLIŠČI
Tomaž Kramberger, 2010, dissertation

Abstract: V doktorski disertaciji z naslovom Problem kitajskega poštarja s prioritetnimi vozlišči je preučevana posplošitev problema kitajskega poštarja, v kateri je podmnožica vozlišč utežena in vrstni red obiska vozlišč vpliva na vrednost namenske funkcije. Preučevan problem je dokazano NP-težek. V disertaciji sta predstavljeni in preučevani dve konstrukcijski hevristiki. Za eno izmed njih je dokazano, da ob določenih pogojih vrne optimalne rešitve. Hevristiki sta implementirani in testirani na več razredih naključno tvorjenih instanc.
Keywords: problem kitajskega poštarja, problemi usmerjanja, Eulerjev graf, prioritetna vozlišča, modificiran algoritem Dijkstre, modificiran Kruskalov algoritem
Published: 27.05.2010; Views: 3009; Downloads: 303
.pdf Full text (10,28 MB)

7.
PRESEK TREH NAJDALJŠIH POTI V GRAFU
Natalija Valek, 2010, undergraduate thesis

Abstract: Diplomsko delo obravnava problem preseka najdaljših poti v grafu. Poseben poudarek je na preseku treh najdaljših poti, kateremu je namenjeno četrto poglavje. V prvem delu so zapisane osnovne definicije s področja teorije grafov, ki se uporabljajo v nadaljevanju. V naslednjem poglavju se najprej dokaže nepraznost preseka dveh najdaljših poti, nato pa se presek iz dveh najdaljših poti posploši na presek n najdaljših poti. Podanih je nekaj grafov s praznim presekom najdaljših poti. V zadnjem delu poglavja se dokaže nepraznost preseka za sledljiv, hiposledljiv in razcepljen graf. Sledi poglavje, v katerem se osredotočimo na presek najdaljših poti v posameznih blokih grafa. Dokaže se, da je presek najdaljših poti v grafu neprazen natanko tedaj, ko je neprazen presek v vseh blokih grafa. Zadnje poglavje je namenjeno preseku treh najdaljših poti. Podan je tudi dokaz o nepraznosti preseka treh najdaljših poti v zunanje ravninskih grafih.
Keywords: Pot, najdaljša pot, presek najdaljših poti, blok, zunanje ravninski graf, Hamiltonovo povezan blok, skoraj Hamiltonovo povezan dvodelni blok.
Published: 07.07.2010; Views: 1808; Downloads: 124
.pdf Full text (1,62 MB)

8.
Preštevanje racionalnih števil
Nuška Konec, 2010, undergraduate thesis

Abstract: V uvodu bomo spoznali pojme, ki so bistveni za razumevanje diplomske naloge. Tako se bomo seznanili z definicijo števne množice, izvedeli nekaj o grafih in drevesih, spoznali metodi iskanja v neskončnih drevesih, predstavljena pa je tudi rekurzija oz. rekurzivna zveza. V poglavju Preštevanje racionalnih števil bomo spoznali načine, s katerimi lahko dokažemo števnost racionalnih števil. To so: osnovni zgled, Calkin - Wilfovo drevo, preštevanje racionalnih števil s pomočjo največjega skupnega delitelja ter s pomočjo razcepa na prafaktorje.
Keywords: Racionalna števila, graf, Calkin-Wilfovo drevo, največji skupni delitelj.
Published: 06.09.2010; Views: 1679; Downloads: 70
.pdf Full text (538,27 KB)

9.
Barvanja grafov, ki so brez ponavljanj po licih
Sara Sabrina Zemljič, 2010, undergraduate thesis

Abstract: Diplomsko delo obravnava osnovne lastnosti barvanj grafov brez ponavljanj. Osrednja tema je barvanje povezav ravninskih grafov brez ponavljanj po licih. Na začetku diplomskega dela so predstavljene osnovne definicije iz teorije grafov, ki jih bomo potrebovali v nadaljevanju. V drugem poglavju vpeljemo barvanje grafov brez ponavljanj in naredimo pregled nad že znanimi rezultati o teh barvanjih. Na koncu drugega poglavja definiramo barvanje povezav ravninskih grafov brez ponavljanj po licih ter njemu pripadajoč Thuejev lični indeks, ki predstavlja najmanjše število barv, s katerimi lahko pobarvamo graf brez ponavljanj po licih. Tretje poglavje je v celoti namenjeno obravnavi barvanja dreves brez ponavljanj po licih. V tem poglavju dokažemo, da je Thuejev lični indeks dreves kvečjemu 4, kar je osnova za dokaz splošne zgornje meje Thuejevega ličnega indeksa. Na koncu pokažemo, da je Thuejev lični indeks poljubnega ravninskega grafa največ 8. Navedemo še nekaj posebnih družin ravninskih grafov, kjer se ta zgornja meja zmanjša.
Keywords: barvanje brez ponavljanj, Thuejevo število, Thuejev indeks, ravninski graf, drevo
Published: 11.11.2010; Views: 1729; Downloads: 144
.pdf Full text (2,53 MB)

10.
DISKRIMINATORNE KODE V DVODELNIH GRAFIH
Denis Kolarič, 2010, undergraduate thesis

Abstract: V uvodnem poglavju predstavimo osnovne definicije iz teorije grafov, ki jih potrebujemo v nadaljevanju in povemo še nekaj o kodah v grafih. V naslednjem poglavju definiramo diskriminatorne kode, podamo nekaj primerov in dokažemo spodnjo in zgornjo mejo za moč minimalne diskriminatorne kode izražene glede na število atributov. V tretjem poglavju pokažemo povezavo med diskriminatornimi in identifikacijskimi kodami v hiperkockah. V četrtem poglavju obravnavamo diskriminatorne kode v drevesih in opišemo algoritem linearne časovne zahtevnosti glede na število vozlišč drevesa, ki za dano drevo poišče minimalno diskriminatorno kodo v drevesu in njegovo delovanje prikažemo na primeru. V zadnjem poglavju podamo za vnaprej podano število atributov konstrukcijo dvodelnih ravninskih grafov brez dvojčkov, ki imajo največje število posameznikov in pokažemo povezavo z ravninskimi triangulacijami.
Keywords: identifikacijska koda, diskriminatorna koda, dvodelni graf, posameznik, atribut, hiperkocka, drevo, algoritem, ravninski graf
Published: 22.10.2010; Views: 1904; Downloads: 171
.pdf Full text (626,67 KB)

Search done in 0.21 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica