| | 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 / 22
Na začetekNa prejšnjo stran123Na naslednjo stranNa konec
1.
Igralno kromatično število nekaterih grafovskih produktov
Lea Podpečan, 2019, magistrsko delo

Opis: 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.
Ključne besede: igralno kromatično število, kartezični produkt, direktni produkt, leksikografski produkt
Objavljeno: 15.02.2019; Ogledov: 621; Prenosov: 67
.pdf Celotno besedilo (541,63 KB)

2.
Nekateri rezultati o povezanosti in neodvisnih množicah v produktih grafov
Tjaša Paj Erker, 2018, doktorska disertacija

Opis: 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.
Ključne besede: direktni produkt, kartezični produkt, krepki produkt, neodvisna množica, povezanost, posplošena povezanost, diameter, krepka orientacija
Objavljeno: 11.12.2018; Ogledov: 817; Prenosov: 87
.pdf Celotno besedilo (603,74 KB)

3.
p-grupe
Urška Bezjak, 2017, magistrsko delo

Opis: 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.
Ključne besede: p-grupe, izreki Sylowa, enačba razreda, izomorfizem grup, direktni produkt grup, grupe majhnih redov, Prüferjeve grupe
Objavljeno: 19.09.2017; Ogledov: 778; Prenosov: 143
.pdf Celotno besedilo (497,43 KB)

4.
Some results on total domination in direct products of graphs
Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Špacapan, izvirni znanstveni članek

Opis: 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.
Ključne besede: mathematics, graph theory, direktni produkt, total domination, ▫$k$▫-tuple domination, open packing, domination
Objavljeno: 31.03.2017; Ogledov: 715; Prenosov: 324
.pdf Celotno besedilo (156,67 KB)
Gradivo ima več datotek! Več...

5.
Grupa kot direktni produkt svojih nerazcepnih podgrup
Barbara Štulac, 2016, magistrsko delo

Opis: 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.
Ključne besede: 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.
Objavljeno: 19.01.2017; Ogledov: 1272; Prenosov: 82
.pdf Celotno besedilo (628,10 KB)

6.
Poldirektni produkt grup
Luka Turk, 2016, diplomsko delo

Opis: 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.
Ključne besede: grupa, podgrupa, direktni produkt grup, poldirektni produkt grup
Objavljeno: 11.11.2016; Ogledov: 922; Prenosov: 91
.pdf Celotno besedilo (384,19 KB)

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

Opis: 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.
Ključne besede: učinkovita odprta dominacija, leksikografski produkt, direktni produkt, kartezični produkt
Objavljeno: 11.11.2016; Ogledov: 857; Prenosov: 106
.pdf Celotno besedilo (462,68 KB)

8.
b-barvanja regularnih grafov in grafovskih produktov
Mojca Premzl, 2016, magistrsko delo

Opis: 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.
Ključne besede: b-barvanje, b-kromatično število, NP-poln problem, regularni graf, kartezični produkt, krepki produkt, leksikografski produkt, direktni produkt.
Objavljeno: 14.10.2016; Ogledov: 813; Prenosov: 76
.pdf Celotno besedilo (1,97 MB)

9.
Povezanost v produktih grafov
Sandra Cigula, 2016, magistrsko delo

Opis: 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.
Ključne besede: produkti grafov, kartezični produkt, direktni produkt, krepki produkt, leksikografski produkt, povezanost.
Objavljeno: 23.08.2016; Ogledov: 952; Prenosov: 120
.pdf Celotno besedilo (3,58 MB)

10.
A characterization of the edge connectivity of direct products of graphs
Simon Špacapan, 2013, izvirni znanstveni članek

Opis: 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.
Ključne besede: matematika, teorija grafov, direktni produkt, povezanost po povezavah, mathematics, graph theory, direct product, edge connectivity
Objavljeno: 10.07.2015; Ogledov: 643; Prenosov: 85
URL Povezava na celotno besedilo

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