| | 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 - 6 / 6
First pagePrevious page1Next pageLast page
1.
KARTEZIČNI PRODUKT GRAFOV
Iris Merkač, 2009, undergraduate thesis

Abstract: Diplomsko delo je sestavljeno iz treh poglavij. V prvem poglavju predstavimo osnovne pojme teorije grafov in podamo definicije ter osnovne lastnosti kartezičnega produkta dveh ali večih grafov. V naslednjem poglavju podamo definiciji hiperkocke in delne kocke, ter spoznamo da so hiperkocke najpreprostejši razred kartezičnega produkta. Nato se posvetimo Djoković-Winklerjevi relaciji Θ, za katero ugotovimo, da je definirana na množici povezav grafa in da je bistvenega pomena za kartezični produkt. Poglavje zaključimo s preprostim algoritmom prepoznavanja hiperkock. V zadnjem poglavju definiramo Hammingove grafe in delne Hammingove grafe. Opazimo tudi, da so hiperkocke edini dvodelni Hammingovi grafi. V nadaljevanju raziščemo kanonično vložitev grafov v kartezični produkt dveh ali večih kvocientnih grafov, katere dobimo iz ekvivalenčnih razredov tranzitivne ovojnice relacije Θ. Nato dokažemo Graham-Winklerjev izrek, ki pove, da je kanonična vložitev izometrija. Ker je izračunavanje tranzitivne ovojnice relacije Θ bistveno pri izračunavanju kanonične vložitve, na koncu podamo algoritem, ki izračuna tranzitivno ovojnico relacije Θ.
Keywords: kartezični produkt, hiperkocke, delne kocke, Hammingovi grafi, relacija Θ, kvocientni graf, kanonična vložitev
Published: 27.01.2021; Views: 126; Downloads: 8
.pdf Full text (411,17 KB)

2.
Razred grafov H(n, k)
Nuša Flajšman, 2016, undergraduate thesis

Abstract: Naj bosta n in k naravni števili in n≥k. To diplomsko delo predstavlja nov razred grafov H(n,k), ki vsebuje hiperkocke ter Johnsonove in Kneserjeve grafe kot njegove podgrafe. V prvem poglavju so povzeti osnovni pojmi iz teorije grafov, v drugem delu pa bodo predstavljeni nekateri rezultati vezani na družino H(n,k). Na primer, H(n,k) ima maksimalno povezanost (n nad k), H(n,k) je Hamiltonov, če je k liho število ter je sestavljen iz dveh izomorfnih povezanih komponent, če je k sodo število.
Keywords: teorija grafov, hiperkocke, hamiltonovi grafi, Johnsonovi grafi, Kneserjevi grafi
Published: 23.09.2016; Views: 901; Downloads: 73
.pdf Full text (1,69 MB)

3.
[Theta]-graceful labelings of partial cubes
Boštjan Brešar, Sandi Klavžar, 2006, original scientific article

Abstract: Delne kocke so grafi, ki dopuščajo izometrične vložitve v hiperkocke. V članku so vpeljane ▫$Theta$▫-gracilne označitve delnih kock kot naravna razširitev gracilnih označitev dreves. Pokazano je, da so različni razredi delnih kock ▫$Theta$▫-gracilni, na primer sodi cikli, Fibonaccijeve kocke in (na novo vpeljane) leksikografske podkocke. Kartezični produkt ▫$Theta$▫-gracilnih delnih kock je spet tak in sprašujemo se, ali je morda vsaka delna kocka ▫$Theta$▫-gracilna. Pokazana je povezava med ▫$Theta$▫-gracilnimi označitvami in reprezentacijami celih števil v določenih številskih sistemih. Predlaganih je tudi nekaj smeri za nadaljnje raziskovanje.
Keywords: matematika, teorija grafov, drevesa, Ringel-Kotzigova domneva, delne kocke, Fibonaccijeve kocke, hiperkocke, mathematics, graph theory, graceful labelings, trees, Ringel-Kotzig conjecture, partial cubes, Fibonacci cubes, hypercubes
Published: 10.07.2015; Views: 505; Downloads: 26
URL Link to full text

4.
Cubic inflation, mirror graphs, regular maps, and partial cubes
Boštjan Brešar, Sandi Klavžar, Alenka Lipovec, Bojan Mohar, 2003

Abstract: Kubično napihovanje je operacija, ki transformira 2-celično vložen graf ▫$G$▫ v kubični graf vložen v isto ploskev; njen rezultat lahko opišemo tudi kot dual baricentrične subdivizije grafa ▫$G$▫. Vpeljana sta koncepta zrcalnega in pra-zrcalnega grafa. Platonski grafi so karakterizirani kot (i) pra-zrcalni grafi in kot (ii) ravninski grafi z minimalno stopnjo vsaj tri, katerih kubični napihnjenci so zrcalni grafi. Kot aplikacija je pokazano, da so napihnjeni platonski grafi kubične delne kocke. Konstruiranih je še pet sporadičnih primerov takih grafov.
Keywords: matematika, teorija grafov, vložitve grafov, baricentrična subdivizija, platonski grafi, izometrični podgrafi, hiperkocke, avtomorfizmi grafov., mathematics, graph theory, graph embeddings, barycentric subdivision, Platonic graphs, isometric subgraphs, hypercubes, graph automorphisms
Published: 10.07.2015; Views: 645; Downloads: 79
URL Link to full text

5.
INTERVALNO RAZDALJNO MONOTONI GRAFI
Nina Črešnjevec, 2012, undergraduate thesis

Abstract: Interval I(u,v) je zaprt, če za vsako vozlišče w iz množice V(G)I(u,v) obstaja tako vozlišče w' v I(u,v), da velja d(w,w')>d(u,v). Če so vsi intervali povezanega grafa G zaprti, pravimo, da je graf G razdaljno monotoni graf. Diplomsko delo proučuje grafe, katerih vsak interval inducira razdaljno monotoni graf - intervalno razdaljno monotone grafe.
Keywords: hiperkocke, interval, razdaljna monotonost, intervalno razdaljna monotonost
Published: 23.04.2012; Views: 1925; Downloads: 92
.pdf Full text (1,20 MB)

6.
METRIČNA DIMENZIJA GRAFA
Mateja Žuželj, 2011, undergraduate thesis

Abstract: V prvem poglavju diplomskega dela predstavimo osnovne pojme iz teorije grafov, podamo definicije in preproste primere grafov. V drugem poglavju definiramo metrično dimenzijo grafa. V tretjem poglavju se posvetimo grafom z majhno metrično dimenzijo. Poti so edini grafi z metrično dimenzijo ena. Ogledamo si lastnosti, ki so značilne za grafe z metrično dimenzijo dva. Ob koncu tega poglavja se seznanimo še z metrično dimenzijo ciklov, ki so predstavniki grafov z metrično dimenzijo dva. V četrtem poglavju obravnavamo metrično dimenzijo različnih primerov grafov. Najprej spoznamo metrično dimenzijo polnih grafov, nato dreves in na koncu še mrež pri katerih kot poseben primer pogledamo hiperkocke. Za drevesa podamo tudi enostaven algoritem za postavitev baznih vozlišč. V zadnjem poglavju se ukvarjamo z uporabo metrične dimenzije. Podamo primere uporabe metrične dimenzije v miselnih problemih in igrah, navigaciji, računalništvu in kemiji.
Keywords: Metrična dimenzija, razdalja v grafih, NP-težek problem, pot, cikel, polni graf, drevo, mreže, hiperkocke, Hammingov graf.
Published: 27.09.2011; Views: 2393; Downloads: 162
.pdf Full text (607,74 KB)

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