Iskanje po katalogu digitalne knjižnice

Opis: Let ▫$G=(V,E)$▫ be a graph. A set of vertices ▫$A$▫ is an incidence generator for ▫$G$▫ if for any two distinct edges ▫$e,f \in E(G)$▫ there exists a vertex from ▫$A$▫ which is an endpoint of either ▫$e$▫ or ▫$f$▫. The smallest cardinality of an incidence generator for ▫$G$▫ is called the incidence dimension and is denoted by ▫$\dim_I(G)$▫. A set of vertices ▫$P \subseteq V(G)$▫ is a 2-packing of ▫$G$▫ if the distance in ▫$G$▫ between any pair of distinct vertices from ▫$P$▫ is larger than two. The largest cardinality of a 2-packing of ▫$G$▫ is the packing number of ▫$G$▫ and is denoted by ▫$\rho(G)$▫. In this article, the incidence dimension is introduced and studied. The given results show a close relationship between ▫$\dim_I(G)$▫ and ▫$\rho(G)$▫. We first note that the complement of any 2-packing in graph ▫$G$▫ is an incidence generator for ▫$G$▫, and further show that either ▫$\dim_I(G)=|V(G)|-\rho(G)$▫ or ▫$\dim_I(G)=|V(G)-|\rho(G)-1$▫ for any graph ▫$G$▫. In addition, we present some bounds for ▫$\dim_I(G)$▫ and prove that the problem of determining the incidence dimension of a graph is NP-hard.
Ključne besede: incidence dimension, incidence generator, 2-packing
Objavljeno v DKUM: 18.08.2023; Ogledov: 58; Prenosov: 6
Celotno besedilo (434,03 KB)
Gradivo ima več datotek! Več...

Opis: V tem magistrskem delu predstavimo različne dominacijske množice, in sicer popolno, učinkovito ter neodvisno. V prvem delu so navedeni osnovni pojmi v teoriji grafov, vse potrebne definicije, izreki in trditve. V nadaljevanju predstavimo nekaj znanih NP-polnih problemov s področja dominacije na grafih in jih podkrepimo s primeri za namen dokazovanja časovne zahtevnosti. Za izbrane dominacijske probleme prikažemo kompleksnost odločitvenih problemov z dominacijskimi lastnostmi za glavne dominacijske množice (popolna, učinkovita in neodvisna) in druge izbrane dominacije. Nazadnje posežemo še po problemih popolnega dominacijskega števila za neodvisno, povezano in celotno dominacijo.
Ključne besede: dominacijska množica, popolna dominacijska množica, neodvisna dominacijska množica, učinkovita dominacijska množica, NP-polni problemi, dominacijsko število
Objavljeno v DKUM: 07.10.2021; Ogledov: 462; Prenosov: 16
Celotno besedilo (694,82 KB)

Opis: V učbeniku so predstavljene nekatere veje diskretne matematike, ki so še posebej uporabne v računalništvu. Tako se sprehodimo skozi logiko, s posebnim poudarkom na dokazu. Sledijo teorije, pri katerih igra poglavitno vlogo matematična indukcija oziroma bolj splošno induktivna posplošitev. Spoznamo osnove kombinatorike in teorije števil. Predstavljene so rekurzivne relacije, s katerimi lahko opišemo ponavljajoče se procese. To nam omogoča tudi vrednotenje algoritmov glede na čas potreben za njegovo izvedbo. Relacije, ki so podmnožice kartezičnega produkta poljubnih množic, predstavljajo širok vir presenetljivih rezultatov. Eden izmed njih rezultira v mrežah in njihovih posebnih predstavnikih Booleovih algebrah. Končamo z grafi, ki predstavljajo neverjetno uporaben matematični model za simuliranje procesov iz realnega življenja.
Ključne besede: izjavni račun, indukcija, kombinatorika, rekurzivna relacija, časovna zahtevnost, teorija števil, relacija, mreža, Booleova algebra, graf
Objavljeno v DKUM: 27.10.2020; Ogledov: 1273; Prenosov: 301
Celotno besedilo (5,40 MB)

Opis: V magistrskem delu so obravnavane in s slikovnimi zgledi predstavljene nekatere lastnosti posplošenih grafov Sierpińskega, zgrajenih na poljubnem baznem grafu G. V prvem poglavju so povzete osnovne definicije iz teorije grafov, ki so pomembne pri razumevanju magistrskega dela. Nato so predstavljeni grafi Sierpińskega in definirani posplošeni grafi Sierpińskega. Tretje poglavje obravnava popolno kromatično število obravnavanih grafov, med drugim tudi za konkretne primere baznih grafov, in sicer graf hiše, kolo, cikel in hiperkocko. V četrtem poglavju so z zgledi podane formule za izračun števila listov, število vozliščnega pokritja in neodvisno število v posplošenih grafih Sierpińskega. V poglavju je tudi dokazano, da sta kromatično in klično število teh grafov enaka kot v bazi. V nadaljevanju je podana zgornja meja dominacijskega števila obravnavanih grafov in tudi točno dominacijsko število teh grafov z dotičnimi lastnostmi. V zadnjem poglavju je dokazana spodnja meja krepke metrične dimenzije posplošenih grafov Sierpińskega in podana je formula za izračun te lastnosti v obravnavanih grafih, v katerih je vsako notranje vozlišče presečno vozlišče.
Ključne besede: posplošeni grafi Sierpińskega, popolno kromatično število, število vozliščnega pokritja, dominacijsko število, krepka metrična dimenzija.
Objavljeno v DKUM: 04.03.2019; Ogledov: 955; Prenosov: 82
Celotno besedilo (627,83 KB)

Opis: The booklet contains the abstracts of the talks given at the 30th Ljubljana-Leoben Graph Theory Seminar that was held at the Faculty of Natural Sciences and Mathematics in Maribor between 13-15 September, 2017. The seminar attracted more than 30 participants from eight countries, all of which are researchers in different areas of graph theory. The topics of the talks encompass a wide range of contemporary graph theory research, notably, various types of graph colorings (b-coloring, packing coloring, edge colorings), graph domination (rainbow domination, Grundy domination, graph security), distinguishing problems, algebraic graph theory, graph algorithms, chemical graph theory, coverings, matchings and also some classical extremal problems. Beside the abstracts of the four invited speakers (Csilla Bujtás, Premysl Holub, Jakub Przybyło, Zsolt Tuza), the booklet contains also the abstracts of 18 contributed talks given at the event.
Ključne besede: mathematics, discrete mathematics, graph theory, Ljubljana-Leoben seminar, Maribor, Slovenia
Objavljeno v DKUM: 08.12.2017; Ogledov: 1220; Prenosov: 165
Celotno besedilo (457,62 KB)
Gradivo ima več datotek! Več...