| | 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 / 22
First pagePrevious page123Next pageLast page
1.
Igralno kromatično število nekaterih grafovskih produktov
Lea Podpečan, 2019, master's thesis

Abstract: V magistrskem delu bomo predstavili igro barvanja vozlišč grafa in igralno kromatično število grafa. Podrobneje si bomo pogledali igro barvanja vozlišč grafa na kartezičnih, direktnih in leksikografskih produktih nekaterih družin grafov. Pri kartezičnih produktih K_2 \square P_n, n \in \NN, K_2 \square C_n, n \geq 3, K_2 \square K_n, n \in \NN, in toroidnih grafih, ki jih dobimo s kartezičnim produktom dveh ciklov, C_{2m} \square C_n, m\geq 3, n \geq 7, bomo predstavili in pokazali natančne vrednosti igralnih kromatičnih števil le-teh. Predstavili bomo tudi igralna kromatična števila naslednjih direktnih produktov: K_{1,n} \times K_{1,m}, m,n \in \NN, K_{m,n} \times K_{a,b}, a,b,n \geq 2, m \in \NN, P_n \times K_{1,m}, m \geq 3, n \geq 2, in P_2 \times W_n, n \geq 3, P_2 \times C_n, n \geq 3. Nazadnje bomo predstavili še igralna kromatična števila naslednjih leksikografskih produktov: P_2 \circ P_n, n \geq 2, P_2 \circ K_{1,n}, n \in \NN, in P_2 \circ W_n, n \geq 8.
Keywords: igralno kromatično število, kartezični produkt, direktni produkt, leksikografski produkt
Published: 15.02.2019; Views: 514; Downloads: 58
.pdf Full text (541,63 KB)

2.
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: 672; Downloads: 73
.pdf Full text (603,74 KB)

3.
p-grupe
Urška Bezjak, 2017, master's thesis

Abstract: Cilj magistrskega dela je spoznati p-grupe in z njimi povezane izreke Sylowa. Najprej obravnavamo osnovne pojme teorije grup, ki jih potrebujemo za razumevanje magistrskega dela. Spoznamo enačbo razreda in proučimo morfizme grup ter vpeljemo direktni produkt grup. Največjo pozornost namenimo p-grupam, izrekom Sylowa in njihovi uporabi v klasifikaciji grup majhnih redov. Obravnavamo končne p-grupe in njihove najpomembnejše lastnosti, nekaj časa pa namenimo tudi neskončnim p-grupam, ki jih spoznavamo na primeru Prüferjevih grup.
Keywords: p-grupe, izreki Sylowa, enačba razreda, izomorfizem grup, direktni produkt grup, grupe majhnih redov, Prüferjeve grupe
Published: 19.09.2017; Views: 646; Downloads: 125
.pdf Full text (497,43 KB)

4.
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: 575; Downloads: 291
.pdf Full text (156,67 KB)
This document has many files! More...

5.
Grupa kot direktni produkt svojih nerazcepnih podgrup
Barbara Štulac, 2016, master's thesis

Abstract: Cilj magistrskega dela je spoznati, pod katerimi pogoji lahko grupe razcepimo na direktni produkt nerazcepnih podgrup. Spoznamo nove pojme kot so notranji direktni produkt grup, razcepna grupa, padajoči in naraščujoči verižni pogoj. Ugotovimo, da če grupa G zadošča vsaj enemu izmed verižnih pogojev na svojih podgrupah edinkah, potem je grupa G enaka direktnemu produktu končnega števila nerazcepnih podgrup. Definiramo normalni endomorfizem in novo operacijo seštevanja preslikav. Ugotovimo, da je kompozitum naravnih vložitev in projekcij direktnega produkta grupe G, normalni endomorfizem grupe. S pomočjo lastnosti in povezav med vsemi novimi pojmi na koncu formuliramo in dokažemo Krull-Schmidtov izrek, ki pravi, da lahko vsako grupo G, ki zadošča pogojema naraščujočih in padajočih verig svojih podgrup edink, na enoličen način zapišemo v obliki direktnega produkta nerazcepnih podgrup grupe G.
Keywords: grupa, podgrupa, notranji in zunanji direktni produkt grup, nerazcepna grupa, naraščujoči in padajoči verižni pogoj, normalni nilpotentni endomorfizem, Krull-Schmidtov izrek.
Published: 19.01.2017; Views: 1127; Downloads: 79
.pdf Full text (628,10 KB)

6.
Poldirektni produkt grup
Luka Turk, 2016, undergraduate thesis

Abstract: V diplomskem delu obravnavamo poldirektni produkt grup, ki je posplošitev direktnega produkta. Poldirektni produkt omogoča konstrukcije precej večjega nabora grup. Pokažemo razliko med direktnim in poldirektnim produktom grup in poiščemo kriterij, kdaj je dana grupa poldirektni produkt grup. Pokažemo tudi primere uporabe poldirektnega produkta grup in primitivnih korenov po modulu p na grupah reda pq, kjer je p praštevilo, q pa deli p-1.
Keywords: grupa, podgrupa, direktni produkt grup, poldirektni produkt grup
Published: 11.11.2016; Views: 793; Downloads: 84
.pdf Full text (384,19 KB)

7.
Učinkovita odprta dominacija na grafovskih produktih
Miha Soršak, 2016, undergraduate thesis

Abstract: Diplomsko delo obravnava učinkovito odprto dominacijo na grafovskih produktih. Zraven natančnega opisa pojma učinkovite odprte dominacije so obravnavani še ostali pojmi in trditve, ki jih uporabimo pri utemeljitvi poglavitnih izrekov. V diplomskem delu pokažemo, kateri so potrebni in zadostni pogoji za učinkovito odprto dominianacijo grafov med direktnimi, leksikografskimi, krepkimi in disjunktnimi produkti. Za kartezični produkt je vključenih nekaj delnih rezultatov o učinkoviti odprti dominaciji torusov in cilindrov.
Keywords: učinkovita odprta dominacija, leksikografski produkt, direktni produkt, kartezični produkt
Published: 11.11.2016; Views: 726; Downloads: 98
.pdf Full text (462,68 KB)

8.
b-barvanja regularnih grafov in grafovskih produktov
Mojca Premzl, 2016, master's thesis

Abstract: Dobro barvanje vozlišč grafa $G$, v katerem v vsakem barvnem razredu obstaja vsaj eno tako vozlišče, ki ima vsaj enega soseda v vsakem drugem barvnem razredu, je b-barvanje grafa $G$. Največje naravno število $k$, za katerega graf premore b-barvanje s $k$ različnimi barvami, imenujemo b-kromatično število grafa in ga označimo s $varphi(G)$. V magistrskem delu bomo predstavili definicijo b-barvanja in podali natančne vrednosti b-kromatičnega števila za poti, cikle, polne grafe, neodvisne množice in polne dvodelne grafe. Dokazali bomo, da je določanje b-kromatičnega števila NP-poln problem, kar ima za posledico dejstvo, da lahko b-kromatično število natančno določimo le nekaterim družinam grafov. Že iz same definicije b-barvanja sledi, da je $chi(G) leq varphi(G) leq Delta(G)+1$. Podali bomo še nekaj zgornjih mej b-kromatičnega števila, ki veljajo za poljubne grafe. Med njimi izpostavimo predvsem $m$-stopnjo grafa $m(G)$; to je največje tako število $m$, za katerega graf $G$ vsebuje vsaj $m$ vozlišč stopnje vsaj $m-1$. Natančno vrednost b-kromatičnega števila lahko med drugim določimo tudi poljubnemu drevesu, in to v polinomskem času. V poglavju o regularnih grafih bomo obravnavali predvsem pogoje, ki jim mora zadoščati $d$-regularen graf, da bo njegovo b-kromatično število enako zgornji meji, to je $d+1$. Eden izmed pogojev je, da ima graf zadostno število vozlišč, in sicer vsaj $2d^3$. Dokazali bomo tudi, da je v $d$-regularnem grafu $varphi(G)=d+1$, če je ožina grafa $g(G) geq 6$ oz. če je $g(G)geq 5$ in graf bodisi ne vsebuje nobenega cikla dolžine $6$ bodisi je $d leq 6$. Nekateri $d$-regularni grafi lahko imajo kljub velikemu $d$ majhno b-kromatično število (npr. dvodelni graf $K_{d,d}$). Dokazali bomo, da velikost b-kromatičnega števila $d$-regularnih grafov, ki ne vsebujejo nobenega $4$-cikla, linearno narašča z velikostjo $d$. Za regularne grafe, ki ne vsebujejo nobenega $4$-cikla in imajo $mathrm{diam}(G) geq 6$, prav tako velja, da je $varphi(G)=d+1$. Enako velja tudi za vse regularne grafe, ki ne vsebujejo nobenega $4$-cikla, njihova vozliščna povezanost pa je $kappa(G) leq frac{d+1}{2}$. Nazadnje bomo dokazali še, da obstajajo le štirje kubični grafi, za katere je $varphi(G) leq d$, eden izmed njih je Petersenov graf. V zadnjem poglavju bomo obravnavali b-barvanja grafovskih produktov, in sicer kartezičnega, krepkega, leksikografskega in direktnega. V primeru kartezičnega in direktnega produkta je b-kromatično število navzdol omejeno z $max left{varphi(G), varphi(H) right}$, v primeru krepkega in leksikografskega produkta pa je spodnja meja enaka $varphi(G) cdot varphi(H)$. Za vsak produkt posebej bomo podali še zgornjo mejo b-kromatičnega števila. Določili bomo še nekatere natančne vrednosti b-kromatičnega števila grafovskih produktov, pri čemer bodo posamezni faktorji enaki potem, ciklom, zvezdam, v nekaterih primerih pa bo eden izmed faktorjev celo poljuben graf.
Keywords: b-barvanje, b-kromatično število, NP-poln problem, regularni graf, kartezični produkt, krepki produkt, leksikografski produkt, direktni produkt.
Published: 14.10.2016; Views: 703; Downloads: 68
.pdf Full text (1,97 MB)

9.
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: 848; Downloads: 109
.pdf Full text (3,58 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: 565; Downloads: 80
URL Link to full text

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