| | 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 / 19
Na začetekNa prejšnjo stran12Na naslednjo stranNa konec
1.
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: 741; Prenosov: 80
.pdf Celotno besedilo (603,74 KB)

2.
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: 767; Prenosov: 74
.pdf Celotno besedilo (1,97 MB)

3.
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: 896; Prenosov: 114
.pdf Celotno besedilo (3,58 MB)

4.
Intervals and convex sets in strong product of graphs
Iztok Peterin, 2013, izvirni znanstveni članek

Opis: Obravnavamo intervale in konveksne množice krepkega produkta. Vozlišča poljubnega intervala iz ▫$G boxtimes H$▫ so klasificirana z najkrajšimi potmi v enem faktorju in s sprehodi v dugem rahlo modificiranem faktorju. Konveksne množice krepkega produkta so karakterizirane s konveksnostjo obeh projekcij in še tremi lokalnimi lastnostmi, med katerimi je tudi 2-konveksnost.
Ključne besede: teorija grafov, krepki produkt, geodetska konveksnost, interval, graph theory, strong product, geodesic convexity, interval
Objavljeno: 10.07.2015; Ogledov: 515; Prenosov: 84
URL Povezava na celotno besedilo

5.
On the b-chromatic number of some graph products
Marko Jakovac, Iztok Peterin, 2012, izvirni znanstveni članek

Opis: Pravilno barvanje vozlišč grafa kjer vsak barvni razred vsebuje vozlišče, ki ima soseda v vseh preostalih barvnih razredih, imenujemo b-barvanje. Največje naravno število ▫$varphi (G)$▫, za katero obstaja b-barvanje grafa ▫$G$▫, imenujemo b-kromatično število. Določimo nekatere spodnje in zgornje meje b-kromatičnega števila za krepki produkt ▫$G,boxtimes, H$▫, leksikografski produkt ▫$G[H]$▫ in za direktni produkt ▫$G,times, H$▫. Prav tako določimo nekatere točne vrednosti za produkte poti, ciklov, zvezd in polnih dvodelnih grafov. Pokažemo tudi, da lahko določimo b-kromatično število za ▫$P_n ,boxtimes, H$▫, ▫$C_n ,boxtimes, H$▫, ▫$P_n[H]$▫, ▫$C_n[H]$▫ in ▫$K_{m,n}[H]$▫ za poljuben graf ▫$H$▫, če sta le ▫$m$▫ in ▫$n$▫ dovolj veliki.
Ključne besede: teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product
Objavljeno: 10.07.2015; Ogledov: 599; Prenosov: 71
URL Povezava na celotno besedilo

6.
NZ-flows in strong products of graphs
Wilfried Imrich, Iztok Peterin, Simon Špacapan, Cun-Quan Zhang, 2010, izvirni znanstveni članek

Opis: Za krepki produkt ▫$G_1 boxtimes G_2$▫ grafov ▫$G_1$▫ in ▫$G_2$▫ dokažemo, da je ▫${mathbb{Z}}_3$▫-pretočno kontraktibilen natanko tedaj, ko ▫$G_1 boxtimes G_2$▫ ni izomorfen ▫$Tboxtimes K_2$▫ (kar poimenujemo ▫$K_4$▫-drevo), kjer je ▫$T$▫ drevo. Sledi, da za ▫$G_1 boxtimes G_2$▫ obstaja NZ 3-pretok, razen če je ▫$G_1 boxtimes G_2$▫ ▫$K_4$▫-drevo. Dokaz je konstruktiven in implicira polinomski algoritem, ki nam vrne NZ 3-pretok, če ▫$G_1 boxtimes G_2$▫ ni ▫$K_4$▫-drevo, oziroma NZ 4-pretok sicer.
Ključne besede: matematika, teorija grafov, celoštevilski pretoki, krepki produkt, poti, cikli, nikjer ničelni pretok, mathematics, graph theory, integer flows, strong product, paths, cycles
Objavljeno: 10.07.2015; Ogledov: 521; Prenosov: 100
URL Povezava na celotno besedilo

7.
Weak reconstruction of strong product graphs
Blaž Zmazek, Janez Žerovnik, 2007, izvirni znanstveni članek

Opis: We prove that any nontrivial connected strong product graph can be uniquely reconstructed from each of its one vertex deleted subgraphs.
Ključne besede: matematika, teorija grafov, problem rekonstrukcije, šibka rekonstrukcija, krepki produkt grafov, mathematics, graph theory, reconstruction problem, strong product, composite graphs
Objavljeno: 10.07.2015; Ogledov: 528; Prenosov: 352
URL Povezava na celotno besedilo

8.
On induced and isometric embeddings of graphs into the strong product of paths
Janja Jerebic, Sandi Klavžar, 2006, izvirni znanstveni članek

Opis: Primerjani sta krepka izometrična dimenzija in sosedna izometrična dimenzija grafov. Koncepta sta ekvivalentna za grafe premera 2 in v tem primeru se problem določitve dimenzije reducira na problem pokritja s polnimi dvodelnimi grafi. S pomočjo tega pristopa je določena krepka izometrična dimenzija in sosedna izometrična dimenzija za različne grafe (na primer za Petersenov graf). Podan je pozitiven odgovor na Problem 4.1 iz [Fitzpatrick, Nowakowski, The strong isometric dimension of finite reflexive graphs, Discuss. Math. Graph Theory 20 (2000) 23-38], ali obstaja tak graf ▫$G$▫, ki ima krepko izometrično dimenzijo večjo od ▫$lceil |V(G)|/2 rceil$▫.
Ključne besede: matematika, teorija grafov, krepki produkt grafov, krepka izometrična dimenzija, sosedna izometrična dimenzija, mathematics, graph theory, strong product of graphs, adjacent isometric dimension, strong isometric dimension
Objavljeno: 10.07.2015; Ogledov: 689; Prenosov: 70
URL Povezava na celotno besedilo

9.
On the weak reconstruction of strong product graphs
Blaž Zmazek, Janez Žerovnik, 2003, objavljeni znanstveni prispevek na konferenci

Opis: We prove that any nontrivial connected strong product graph can be uniquely reconstructed from each of its one vertex deleted subgraphs.
Ključne besede: matematika, teorija grafov, problem rekonstrukcije, šibka rekonstrukcija, krepki produkt grafov, mathematics, graph theory, reconstruction problem, strong product, composite graphs
Objavljeno: 10.07.2015; Ogledov: 553; Prenosov: 62
URL Povezava na celotno besedilo

10.
Chromatic numbers of strong product of odd cycles
Janez Žerovnik, 2002, objavljeni znanstveni prispevek na konferenci

Opis: The problem of determining the chromatic numbers of the strong product of cycles is considered. A construction is given proving ▫$chi(G) = 2^p + 1$▫ for a product of ▫$p$▫ odd cycles of lengths at least ▫$2^p + 1$▫. Several consequences are discussed. In particular it is proved that the strong product of ▫$p$▫ factors has chromatic number at most ▫$2^p + 1$▫ provided that each factor admits the homomorphism to sufficiently long odd cycle ▫$C_{m_i}, ; m_i ge 2^p + 1$▫.
Ključne besede: matematika, teorija grafov, krepki produkt grafov, kromatično število, lih cikel, minimalna neodvisna dominantna množica, mathematics, graph theory, strong product, chromatic number, odd cycle, minimal independent dominating set
Objavljeno: 10.07.2015; Ogledov: 889; Prenosov: 62
URL Povezava na celotno besedilo

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