| | 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 - 10 / 42
Na začetekNa prejšnjo stran12345Na naslednjo stranNa konec
1.
GEODETSKO IN OVOJNIŠKO ŠTEVILO PRODUKTOV GRAFOV
Jasna Mrkonjić, 2010, diplomsko delo

Opis: Diplomsko delo obravnava geodetsko in ovojniško število standardnih produktov grafov s poudarkom na kartezičnem in krepkem produktu. V prvem delu so zapisane osnovne definicije s področja teorije grafov, ki se uporabljajo v nadaljevanju. V naslednjem poglavju si pogledamo grafe, za katere je geodetsko število enako ali za ena manjše od števila vozlišč ter enako za ovojniško število. Sledi poglavje v katerem se osredotočimo na geodetsko in ovojniško število v kartezičnem produktu grafov in si pogledamo robne množice. Zadnji del diplomske naloge je namenjen geodetskemu in ovojniškemu številu v krepkem produktu grafov, kjer so podane meje za obe števili in natančne vrednosti za določene tipe grafov.
Ključne besede: konveksnost, ovojnica, geodetska množica grafa, geodetsko število, ovojniško število, poln graf, cikel, produkt grafov, kartezični produkt grafov, krepki produkt grafov, robne množice
Objavljeno: 15.12.2010; Ogledov: 1909; Prenosov: 97
.pdf Celotno besedilo (754,64 KB)

2.
PARTICIJSKA DIMENZIJA GRAFOV
Adrijana Tivadar, 2011, diplomsko delo

Opis: Diplomsko delo obravnava particijsko dimenzijo grafov in je sestavljeno iz treh poglavij. V prvem poglavju bomo predstavili osnovne pojme iz teorije grafov in spoznali bomo štiri najbolj poznane produkte grafov, s poudarkom na kartezičnem produktu. Drugo poglavje bomo namenili predstavitvi dveh, za nas najbolj pomembnih dimenzij grafov. To sta metrična in particijska dimenzija grafov. Najprej bomo definirali metrično dimenzijo grafov in spoznali njene lastnosti. Nato se bomo posvetili particijski dimenziji grafov in njenim lastnostim. Pri obeh dimenzijah bomo za boljšo predstavitev podali tudi nekaj primerov. Na koncu tega poglavja pa si bomo še pogledali povezanost omenjenih dveh dimenzij. V zadnjem poglavju bomo definirali particijsko dimenzijo kartezičnega produkta grafov. Pogledali si bomo zgornjo mejo te dimenzije, nato bomo spoznali njeno povezavo z metrično dimenzijo in na koncu navedli še dva aktualna odprta problema.
Ključne besede: rešljiva particija, particijska dimenzija grafov, rešljiva množica, metrična dimenzija grafov, kartezični produkt grafov.
Objavljeno: 28.06.2011; Ogledov: 1873; Prenosov: 129
.pdf Celotno besedilo (4,31 MB)

3.
HAMILTONSKE PRIZME
Žan Močivnik, 2012, diplomsko delo

Opis: obstoja hamiltonske prizme v grafu leži med problemoma obstoja Hamiltonove poti in obstoja 2-sprehoda v grafu, kar v diplomskem delu podrobneje osvetlimo. Pri dokazovanju obstoja hamiltonskih prizem nad grafi si pomagamo s posebnim barvanjem povezav grafa. V prvem poglavju so opisane osnovne definicije in rezultati, povezani z grafi, prizmami in hamiltonskostjo. V drugem poglavju podrobneje obravnavamo prizme nad dvodelnimi grafi, kubičnimi grafi, posplošenimi Halinovimi grafi in grafi povezav ter predstavimo nekatere rezultate, ki se nanašajo na iskanje njihovih Hamiltonovih prizem.
Ključne besede: Teorija grafov, prizma, kartezični produkt, Hamiltonov cikel, Hamiltonov graf, Hamiltonova prizma, k-sprehod, k-drevo, k-faktor.
Objavljeno: 27.02.2012; Ogledov: 2045; Prenosov: 171
.pdf Celotno besedilo (2,17 MB)

4.
VENNOVI DIAGRAMI
Nina Plošnik, 2011, diplomsko delo

Opis: Diplomsko delo obravnava Vennove diagrame. Osrednja tema so splošni Vennovi diagrami in grafi, ki so povezani z Vennovimi diagrami. V uvodnem poglavju predstavimo osnovne definicije iz teorije grafov, ki jih potrebujemo v nadaljevanju, definiramo Vennove diagrame ter povemo nekaj o njihovi uporabi in o primerjavi z Eulerjevimi diagrami. V drugem poglavju prikažemo obstoj Vennovih diagramov za n≥3 na primerih dveh konstrukcij in pokažemo, kdaj se jih lahko nariše z uporabo skladnih krogov. V zadnjem poglavju podrobno obravnavamo grafe, ki so povezani z Vennovimi diagrami. Najprej predstavimo Vennove duale, definiramo kdaj so Vennovi diagrami izomorfni in obravnavamo Vennove diagrame in Vennove razrede. Nato raziščemo razširitev Vennovega diagrama in podamo Winklerjevo domnevo, ki pa ostaja nepotrjena. Z odpravo omejitve enostavnosti v nadaljevanju dokažemo Grünbaumov izrek. Na koncu poglavja obravnavamo tudi minimalne in monotone Vennove diagrame.
Ključne besede: Vennov diagram, Eulerjev diagram, izomorfizem dveh grafov, dvodelni graf, ravninski graf, dual ravninskega grafa, polni graf, kartezični produkt grafov
Objavljeno: 26.10.2011; Ogledov: 2580; Prenosov: 107
.pdf Celotno besedilo (1,79 MB)

5.
DINAMIČNO BARVANJE GRAFOV
Tjaša Grahornik, 2012, diplomsko delo

Opis: V diplomskem delu je predstavljeno dinamično barvanje grafov. V uvodnih poglavjih so predstavljeni osnovni pojmi iz teorije grafov, ki so pomembni za razumevanje diplomskega dela. Pogledali si bomo kakšno je dinamično kromatično število za polne grafe, drevesa in cikle. V nalogi so opisane znane zgornje meje za dinamično kromatično število. Primerjali smo kromatično število in dinamično kromatično število za normalne grafe in regularne grafe. Ugotovili smo, da je razlika med dinamičnim kromatičnim številom in kromatičnim številom poljubno velika za nekatere grafe. Del diplomske naloge bomo posvetili tudi dinamičnemu barvanju kartezičnega produkta dveh grafov ter zaključili s posplošitvijo dinamičnega barvanja.
Ključne besede: dinamično barvanje grafov, zgornje meje, kartezični produkt, posplošitev dinamičnega barvanja
Objavljeno: 11.10.2012; Ogledov: 951; Prenosov: 102
.pdf Celotno besedilo (586,39 KB)

6.
On subgraphs of Cartesian product graphs
Sandi Klavžar, Alenka Lipovec, Marko Petkovšek, 1999

Opis: Karakterizirani so grafi, ki jih lahko predstavimo kot netrivialen podgraf kartezičnega produkta grafov. Kot posledica je pokazano, da ima vsak dvodelni graf z radijem 2, ki ne vsebuje ▫$K_{2,3}$▫, tako predstavitev. Neskončna družina bazičnih podgrafov je tudi konstruirana - dosedaj je bilo znanih le končno takih grafov.
Ključne besede: matematika, teorija grafov, kartezični produkt grafov, podgrafi, mathematics, graph theory, Cartesian product graphs, subgraphs
Objavljeno: 10.07.2015; Ogledov: 269; Prenosov: 22
URL Povezava na celotno besedilo

7.
On cube-free median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2003

Opis: Naj bo ▫$G$▫ mediansk graf brez 3-kocke. Pokazano je, da velja ▫$frac{k}{2} ge sqrt{n}-1 ge frac{m}{2sqrt{n}} ge sqrt{s} ge r-1$▫, kjer so ▫$n, m, s, k$▫ in ▫$r$▫ števila točk, povezav, kvadratov, ▫$Theta$▫-razredov in število povezav najmanšega ▫$Theta$▫-razreda grafa ▫$G$▫. Enakosti so dosežene natanko tedaj, ko je ▫$G$▫ kartezični produkt dveh dreves istega reda. Obravnavan je tudi polinom kock medianskih grafov in pokazano je, da lahko ravninske medianske grafe brez 3-kocke prepoznamo v linearnem času.
Ključne besede: matematika, teorija grafov, medianski graf, kartezični produkt, prepoznavni algoritem, mathematics, graph theory, median graph, cube-free graph, Cartesian product, recognition algoritem
Objavljeno: 10.07.2015; Ogledov: 414; Prenosov: 9
URL Povezava na celotno besedilo

8.
Roots of cube polynomials of median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2003

Opis: Polinom kock ▫$c(G,X)$▫ grafa ▫$G$▫ je definiran z ▫$sum_{i ge 0}alpha_i(G)x^i$▫, kjer ▫$alpha_i(G)$▫ označuje število induciranih ▫$i$▫-kock v ▫$G$▫. Naj bo ▫$G$▫ medianski graf. Dokazano je, da je vsaka racionalna ničla polinoma ▫$c(G,x)$▫ oblike ▫$-frac{t+1}{t}$▫ za neko celo število ▫$t>0$▫ in da ima ▫$c(G,x)$▫ vedno realno ničlo na intervalu ▫$[-2,-1)$▫. Nadalje ima ▫$c(G,x)$▫ ▫$p$▫-kratno ničlo natanko tedaj, ko je ▫$G$▫ kartezični produkt ▫$p$▫ dreves istega reda. Grafi acikličnih kubičnih kompleksov so karakterizirani kot grafi za katere velja ▫$c(H,-2)=0$▫ za vsak 2-povezan konveksen podgraf ▫$H$▫.
Ključne besede: matematika, teorija grafov, polinom kock, koren, medianski graf, kartezični produkt grafov, mathematics, graph theory, cube polynomial, root, median graph, Cartesian product
Objavljeno: 10.07.2015; Ogledov: 292; Prenosov: 21
URL Povezava na celotno besedilo

9.
On domination numbers of graph bundles
Blaž Zmazek, Janez Žerovnik, 2005

Opis: Let ▫$gamma(G)$▫ be the domination number of a graph ▫$G$▫. It is shown that for any ▫$k ge 0$▫ there exists a Cartesian graph bundle ▫$B Box_varphi F$▫ such that ▫$gamma(B Box_varphi F) = gamma(B)gamma(F) - 2k$▫. The domination numbers of Cartesian bundles of two cycles are determined exactly when the fibre graph is a triangle or a square. A statement similar to Vizing's conjecture on strong graph bundles is shown not to be true by proving the inequality ▫$gamma(B boxtimes_varphi F) le gamma(B)gamma(F)$▫ for strong graph bundles. Examples of graphs ▫$B$▫ and ▫$F$▫ with ▫$gamma(B boxtimes_varphi F) < gamma(B)gamma(F)$▫ are given.
Ključne besede: matematika, teorija grafov, kartezični produkt grafov, dominantno število, dominantna množica, grafovski sveženj, mathematics, graph theory, graph bundle, dominating set, domination number, Cartesian product
Objavljeno: 10.07.2015; Ogledov: 444; Prenosov: 33
URL Povezava na celotno besedilo

10.
The distinguishing chromatic number of Cartesian products of two complete graphs
Janja Jerebic, Sandi Klavžar, 2008

Opis: Označitev grafa ▫$G$▫ je razlikovalna, če jo ohranja le trivialni avtomorfizem grafa ▫$G$▫. Razlikovalno kromatično število grafa ▫$G$▫ je najmanjše naravno število, za katero obstaja razlikovalna označitev grafa, ki je hkrati tudi dobro barvanje. Za vse ▫$k$▫ in ▫$n$▫ je določeno razlikovalno kromatično število kartezičnih produktov ▫$K_kBox K_n$▫. V večini primerov je enako kromatičnemu številu, kar med drugim odgovori na vprašanje Choia, Hartkeja and Kaula, ali obstajajo še kakšni drugi grafi, za katere velja enakost.
Ključne besede: teorija grafov, razlikovalno kromatično število, grafovski avtomorfizem, kartezični produkt grafov, graph theory, distinguishing chromatic number, graph automorphism, Cartesian product of graphs
Objavljeno: 10.07.2015; Ogledov: 314; Prenosov: 25
URL Povezava na celotno besedilo

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