| | 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 / 26
First pagePrevious page123Next pageLast page
1.
Nekateri rezultati o povezanosti in neodvisnih množicah v produktih grafov
Tjaša Paj Erker, 2018, doctoral dissertation

Abstract: Doktorska disertacija obravnava nekatere rezultate na grafovskih produktih. V uvodu bomo na kratko predstavili vsebino doktorske disertacije in ponovili nekatere osnovne pojme teorije grafov, ki jih bomo uporabljali v nadaljevanju. Prva tema, ki jo bomo predstavili so neodvisne množice v direktnem produktu. Govorili bomo o velikosti in strukturi največjih neodvisnih množic v direktnem produktu. Najprej bomo predstavili pomembnejše znane rezultate, nato pa bomo pokazali, da ima direkten produkt lihe poti in poljubnega grafa, ter direkten produkt sodega cikla in poljubnega grafa največjo neodvisno množico, ki je unija dveh pravokotnikov. Ugotovili bomo, da obstajajo v direktnem produktu sode poti in poljubnega grafa največje neodvisne množice, ki so lahko tudi drugačne oblike ter zapisali natančno karakterizacijo teh največjih neodvisnih množic. Zapisali bomo zadostni pogoji za drevesa, da ima direkten produkt drevesa in poljubnega grafa največjo neodvisno množico oblike dveh pravokotnikov. V nadaljevanju bomo raziskali posplošeno 3-povezanost v kartezičnem produktu grafov. Prikazali bomo več naravnih načinov, kako dobiti 3-presečno množico S, pri kateri nam graf razpade na vsaj tri komponente. Nato bomo dokazali, da je eden izmed teh načinov vedno optimalen, če sta G in H 2-povezana grafa na vsaj šestih vozliščih. Tako dobimo natančno vrednost posplošene 3-povezanosti kartezičnega produkta dveh 2-povezanih grafov na vsaj šestih vozliščih. Na koncu se bomo ukvarjali z vprašanjem o zgornji meji najmanjšega diametra krepko orientiranega krepkega produkta. Določili bomo natančno vrednost najmanjšega diametra krepkega produkta dveh poti.
Keywords: direktni produkt, kartezični produkt, krepki produkt, neodvisna množica, povezanost, posplošena povezanost, diameter, krepka orientacija
Published: 11.12.2018; Views: 725; Downloads: 75
.pdf Full text (603,74 KB)

2.
Matematika 1
Tina Sovič, Simon Špacapan, 2018, other educational material

Abstract: Skripta Matematika 1 zajema osnovna znanja matematike, ki ga potrebujejo študentje visokošolskih programov Fakultete za gradbeništvo,prometno inženirstvo in arhitekturo. V prvem delu skripte so predstavljena poglavja iz področja analize, v drugem delu pa poglavja iz področja algebre. Natančneje, začnemo z zaporedji, kjer opredelimo osnovne pojme, kot so omejenost, monotonost in konvergenca zaporedja. Sledi poglavje, ki na kratko predstavi kompleksna števila in operacije med njimi. Nato so opisane osnovne elementarne funkcije ter predstavljena pojma limita funkcije in zveznost. Definiramo odvod funkcije in pokažemo njegovo uporabo pri določanju lokalnih ekstremov. Odvodu sledi definicija integrala skupaj z njegovo uporabo. Prvi del skripte zaključuje poglavje o funkcijah dveh spremenljivk. V drugem delu predstavimo geometrijske vektorje in operacije med njimi. V nadaljevanju obravnavamo premice in ravnine v prostoru. Skripto zaključimo s poglavjem o matrikah, kjer opišemo osnovne matrične operacije, sisteme enačb in matriko linearne preslikave.
Keywords: zaporedja, funkcije, odvod, integral, vektorji, sistemi enačb, matrike
Published: 17.04.2018; Views: 1790; Downloads: 473
.pdf Full text (2,44 MB)

3.
Hiperbolična geometrija in regularna tlakovanja
Barbara Arcet, 2017, master's thesis

Abstract: Magistrska naloga obravnava hiperbolično geometrijo in regularna tlakovanja v njej. Hiperbolična geometrija je ena izmed treh možnih geometrij poleg evklidske in sferične. V tem magistrskem delu si podrobneje ogledamo regularna tlakovanja, t.j. pokritja ravnine s samimi skladnimi pravilnimi mnogokotniki. V tem pogledu smo v evklidski in sferični geometriji precej omejeni, saj v prvi obstajajo le trije primeri regularnih (platonskih) tlakovanj, v drugi pa pet. V hiperbolični geometriji jih obstaja neskončno. Magistrsko delo je organizirano v tri dele. Najprej spoznamo osnove hiperbolične geometrije, opišemo njen razvoj skozi zgodovino ter si ogledamo tri modele za njeno predstavitev. Drugi del je namenjen lastnostim hiperbolične geometrije ter njeni primerjavi z evklidsko in sferično geometrijo. Definiramo razdaljo med poljubnima točkama, ogledamo si ukrivljenost ploskve in kote trikotnikov v vseh treh geometrijah. Seznanimo se s Pitagorovim izrekom, zapisanim tudi v okviru sferične in hiperbolične geometrije. V zadnjem delu se osredotočimo na regularna tlakovanja v vseh treh omenjenih geometrijah ter predstavimo nekaj matematičnih umetnij neevklidske geometrije nizozemskega umetnika M. C. Escherja, katerih osnova so prav regularna tlakovanja v hiperbolični geometriji. Razmislimo tudi o razlogih in možnostih vpeljave hiperbolične geometrije v šolski pouk.
Keywords: hiperbolična geometrija, regularna tlakovanja
Published: 08.11.2017; Views: 871; Downloads: 159
.pdf Full text (10,32 MB)

4.
Maximum independent sets in direct products of cycles or trees with arbitrary graphs
Tjaša Paj, Simon Špacapan, 2015, original scientific article

Abstract: The direct product of graphs ▫$G = (V(G),E(G))$▫ and ▫$H = (V(H),E(H))$▫ is the graph, denoted as ▫$G \times H$▫, with vertex set ▫$V(G \times H) = V(G )\times V(H)$▫, where vertices ▫$(x_1,y_1)$▫ and ▫$(x_2,y_2)$▫ are adjacent in ▫$G \times H$▫ if ▫$x_1x_2 \in E(G)$▫ and ▫$y_1y_2 \in E(H)$▫. Let ▫$n$▫ be odd and ▫$m$▫ even. We prove that every maximum independent set in ▫$P_n \times G$▫, respectively ▫$C_m \times G$▫, is of the form ▫$(A \times C) \cup (B \times D)$▫, where ▫$C$▫ and ▫$D$▫ are nonadjacent in ▫$G$▫, and ▫$A \cup B$▫ is the bipartition of ▫$P_n$▫ respectively ▫$C_m$▫. We also give a characterization of maximum independent subsets of ▫$P_n \times G$▫ for every even ▫$n$▫ and discuss the structure of maximum independent sets in ▫$T \times G$▫ where ▫$T$▫ is a tree.
Keywords: direct product, independent set
Published: 07.04.2017; Views: 826; Downloads: 344
.pdf Full text (173,48 KB)
This document has many files! More...

5.
Some results on total domination in direct products of graphs
Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Špacapan, original scientific article

Abstract: Upper and lower bounds on the total domination number of the direct product ofgraphs are given. The bounds involve the ▫$\{2\}$▫-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
Keywords: mathematics, graph theory, direktni produkt, total domination, ▫$k$▫-tuple domination, open packing, domination
Published: 31.03.2017; Views: 656; Downloads: 310
.pdf Full text (156,67 KB)
This document has many files! More...

6.
On acyclic colorings of direct products
Simon Špacapan, Aleksandra Tepeh, 2008, original scientific article

Abstract: A coloring of a graph ▫$G$▫ is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees ▫$T_1$▫ and ▫$T_2$▫ equals ▫$\min\{ \Delta(T_1) + 1, \Delta(T_2) + 1\}$▫. We also prove that the acyclic chromatic number of direct product of two complete graphs ▫$K_m$▫ and ▫$K_n$▫ is ▫$mn-m-2$▫, where ▫$m \ge n \ge 4$▫. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.
Keywords: mathematics, graph theory, coloring, acyclic coloring, distance-two coloring, direct product
Published: 31.03.2017; Views: 391; Downloads: 62
.pdf Full text (142,13 KB)
This document has many files! More...

7.
Edge-connectivity of strong products of graphs
Boštjan Brešar, Simon Špacapan, 2007, original scientific article

Abstract: The strong product ▫$G_1 \boxtimes G_2$▫ of graphs ▫$G_1$▫ and ▫$G_2$▫ is the graph with ▫$V(G_1) \times V(G_2)$▫ as the vertex set, and two distinct vertices ▫$(x_1,x_2)$▫ and ▫$(y_1,y_2)$▫ are adjacent whenever for each ▫$i\in \{1,2\}$▫ either ▫$x_i=y_i$▫ or ▫$x_iy_i \in E(G_i)$▫. In this note we show that for two connected graphs ▫$G_1$▫ and ▫$G_2$▫ the edge-connectivity ▫$\lambda(G_1 \boxtimes G_2)$▫ equals ▫$\min\{\delta(G_1\boxtimes G_2), \lambda(G_1)(|V(G_2)|+2|E(G_2)|), \lambda(G_2)(|V(G_1)|+2|E(G_1)|)\}$▫. In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.
Keywords: mathematics, graph theory, connectivity, strong product, graph product, separating set
Published: 31.03.2017; Views: 687; Downloads: 272
.pdf Full text (173,26 KB)
This document has many files! More...

8.
Povezanost v produktih grafov
Sandra Cigula, 2016, master's thesis

Abstract: V tej nalogi bomo obravnavali pojma povezanost po povezavah in povezanost po vozliščih v produktih grafov. Drugi cilj bo opisati strukturo in ostale lastnosti najmanjših presečnih množic vozlišč in najmanjših presečnih množic povezav v produktih grafov. Osredotočili se bomo predvsem na kartezični, direktni, krepki in leksikografski produkt grafov. Zanimalo nas bo, kako izraziti povezanost produkta z lastnostmi posameznih faktorjev produkta, kot so najmanjša stopnja, red grafa in povezanost. Pri direktnem produktu grafov bomo ugotovili, da je povezanost po povezavah odvisna od povezanosti faktorjev, pa tudi od tega, kako daleč sta faktorja $G$ in $H$ od tega, da bi bila dvodelna. Nato bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav kartezičnih produktov grafov. Podan bo dokaz trditve $lambda(G , Box , H)= textrm{min}left{lambda(G)left|V(H)right|,lambda(H)left|V(G)right|,delta(G)+delta(H)right}.$ Dokaz podobne trditve za povezanost po vozliščih kartezičnega produkta bo naveden v nadaljevanju. Na koncu bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav krepkih produktov grafov in povezanost v leksikografskem produktu.
Keywords: produkti grafov, kartezični produkt, direktni produkt, krepki produkt, leksikografski produkt, povezanost.
Published: 23.08.2016; Views: 884; Downloads: 111
.pdf Full text (3,58 MB)

9.
Prirejanja v dvodelnih grafih
Maja Burič, 2015, undergraduate thesis

Abstract: Diplomsko delo z naslovom Prirejanja v dvodelnih grafih je razdeljeno na tri dele.Prvo poglavje opisuje osnovne pojme v teoriji grafov. Na kratko so predstavljene tiste osnovne definicije in lastnosti grafov, ki so potrebne za lažje nadaljno razumevanje snovi. Podrobneje so obravnavani dvodelni grafi in njihove lastnosti. Dokazan je izrek, ki karakterizira dvodelne grafe kot tiste grafe, ki nimajo lihih ciklov. V drugem poglavju sta predstavljeni definiciji prirejanja in pokritija. Zapisane in slikovno ponazorjene so definicije prirejanja in pokritja, kar je pomembno za celotno obravnavo diplomskega dela. V tretjem in najpomembnejšem poglavju povežemo vso prejšnjo snov v celoto in razložimo celotno temo diplomskega dela. Dokažemo dva najpomembnejša izreka o dvodelnih grafih; Königov izrek o moči največjega prirejanja v dvodelnem grafu in Hallov izrek, ki podaja potreben in zadosten pogoj za obstoj prirejanja, ki pokrije enega izmed obeh delov dvodelne particije. Ta dva izreka sta za lažje razumevanje tudi predstavljena na primerih. Diplomsko nalogo zaključimo s posledicami, ki sledijo Hallovemu izreku in njihovimi dokazi.
Keywords: dvodelni grafi, prirejanja, pokritja, Hallov pogoj
Published: 23.07.2015; Views: 1098; Downloads: 84
.pdf Full text (2,37 MB)

10.
A characterization of the edge connectivity of direct products of graphs
Simon Špacapan, 2013, original scientific article

Abstract: V članku dokažemo formulo za povezanost po povezavah direktnega produkta grafov. V formuli se povezanost po povezavah produkta izraža kot funkcija povezanosti po povezavah, najmanjše stopnje, števila povezav in dvodelne frustracije obeh faktorjev. Prav tako v članku opišemo strukturo najmanjših presečnih množic v direktnih produktih grafov.
Keywords: matematika, teorija grafov, direktni produkt, povezanost po povezavah, mathematics, graph theory, direct product, edge connectivity
Published: 10.07.2015; Views: 594; Downloads: 81
URL Link to full text

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