| | 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 / 129
First pagePrevious page12345678910Next pageLast page
1.
Diskretne strukture
Iztok Peterin, 2020

Abstract: 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.
Keywords: izjavni račun, indukcija, kombinatorika, rekurzivna relacija, časovna zahtevnost, teorija števil, relacija, mreža, Booleova algebra, graf
Published: 27.10.2020; Views: 336; Downloads: 106
.pdf Full text (5,40 MB)

2.
Lastnosti grafov Hanojskega stolpa
Eva Zmazek, 2019, master's thesis

Abstract: Hanojski grafi $H_p^n$, $n \geq 1$, $p \geq 3$, so modeli predstavitve problema Hanojskega stolpa z $n$ diski in $p$ nosilci. Njihova rekurzivna konstrukcija vodi do izpeljave nekaterih lastnosti. Kromatično število $\chi(H_p^n)$ Hanojskega grafa $H_p^n$ je na primer enako številu nosilcev $p$ prirejenega problema Hanojskega stolpa, kromatični indeks $\chi'(H_p^n)$ tega Hanojskega grafa pa je enak njegovi maksimalni stopnji vozlišč $\Delta(H_p^n)$. Vsi Hanojski grafi so Hamiltonovi, $(p-1)$-povezani, nekateri med njimi so tudi ravninski. \end{sloppypar} \begin{sloppypar} Barvanje povezav $c: E(G) \to [k]$ je mavrica, če za poljubni različni povezavi $e,f \in E(G)$ velja $c(e) \not= c(f)$. Anti-Ramseyevo število na paru grafov $G$ in $H$ je najmanjše tako število $n$, za katerega pri vsakem barvanju $c$ povezav grafa $G$ z natanko $n$ barvami, obstaja $H$-podgraf grafa $G$, za katerega je zožitev $c|H$ mavrica. V magistrski nalogi si ogledamo anti-Ramseyeva števila $\ar(H_p^n,H_q^m)$, $p,q \geq 3$, $n,m \geq 1$, na paru Hanojskih grafov, kjer je $m=n=1$ in $q=3$, in na paru Hanojskih grafov, kjer je $p=q$. Za anti-Ramseyevo število $\ar(H_p^n,H_3^1)$, $p \geq 3$, $n \geq 1$, izpeljemo rekurzivno zvezo. Pokažemo tudi, da je anti-Ramseyevo število $\ar(H_4^2,H_3^2)$ omejeno navzdol s $30$ ter navzgor s $34$.
Keywords: Hanojski graf, Hanojski stolp, anti-Ramseyevo število, mavrica
Published: 05.11.2019; Views: 402; Downloads: 72
.pdf Full text (554,90 KB)

3.
Množice točk in vozlišč v splošni legi
Barbara Gašparič, 2019, master's thesis

Abstract: Magistrsko delo obravnava klasični problem “no-three-in-line” in dve njegovi pospološitvi. Klasični problem “no-three-in-line” je, poiskati največje možno število točk, ki jih lahko postavimo na n × n mrežo tako, da nobene tri med njimi ne bodo ležale v ravni črti. Posplošitvi, ki ju bomo obravnavali, sta problem “no-three-in-line” v 3D in problem splošne lege v teoriji grafov. Problem “no-three-in-line” v 3D je, poiskati največje možno število točk, ki jih lahko postavimo na n × n × n mrežo tako, da nobene tri med njimi ne bodo ležale v ravni črti. Problem splošne lege v teoriji grafov pa je, poiskati največjo množico vozlišč, za katero bo veljalo, da nobena tri vozlišča iz te množice ne ležijo na skupni najkrajši poti. V prvem poglavju je navedenih nekaj definicij in pomembnih rezultatov iz področja diskretne matematike in teorije števil, ki jih bomo potrebovali v nadaljnjih poglavjih. V drugem poglavju predstavimo klasični problem “no-three-in-line”, pokažemo koliko je pričakovana zgornja meja za število nekolinearnih točk na n × n mreži pri velikih n in vidimo, da lahko na n × n mrežo zmeraj postavimo n nekolinearnih točk. V tretjem poglavju predstavimo problem “no-three-in-line” v 3D, pokažemo, kako je ta problem povezan s 3D-sliko grafa Kn in povemo, kakšno je pričakovano število nekolinearnih točk na n × n × n mreži. V zadnjem poglavju predstavimo problem splošne lege v teoriji grafov ter njegove zgornje in spodnje meje. Zgornje meje so podane na podlagi različnih izometričnih pokritij grafov, spodnje pa dobimo tako, da množice v splošni legi povežemo s premerom grafa in njegovim pakiranjem.
Keywords: problem “no-three-in-line”, splošna lega, celoštevilska mreža, 3D-slika grafa, izometrično pokritje, izometrični podgraf
Published: 15.03.2019; Views: 453; Downloads: 61
.pdf Full text (1,06 MB)

4.
Strong edge geodetic problem in networks
Paul Manuel, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj, Elizabeth Thomas, 2017, original scientific article

Abstract: Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. Here we introduce a variation of the geodetic problem and call it strong edge geodetic problem. We illustrate how this problem is evolved from social transport networks. It is shown that the strong edge geodetic problem is NP-complete. We derive lower and upper bounds for the strong edge geodetic number and demonstrate that these bounds are sharp. We produce exact solutions for trees, block graphs, silicate networks and glued binary trees without randomization.
Keywords: geodetic problem, strong edge geodetic problem, computational complexity, transport networks
Published: 03.11.2017; Views: 573; Downloads: 322
.pdf Full text (657,86 KB)
This document has many files! More...

5.
Omega polynomial revisited
Mircea V. Diudea, Sandi Klavžar, 2010, original scientific article

Abstract: Omega polynomial was proposed by Diudea (Omega Polynomial, Carpath. J. Math., 2006, 22, 43-47) to count the opposite topologically parallel edges in graphs, particularly to describe the polyhedral nanostructures. In this paper, the main definitions are re-analyzed and clear relations with other three related polynomials are established. These relations are supported by close formulas and appropriate examples.
Keywords: mathematics, chemical graph theory, counting polynomials, Ommega polynomial, Theta polynomial, Pi polynomial, PI index, Sadhana polynomial, Cluj-Ilmenau index, CI index
Published: 24.08.2017; Views: 463; Downloads: 68
.pdf Full text (263,85 KB)
This document has many files! More...

6.
Guarded subgraphs and the domination game
Boštjan Brešar, Sandi Klavžar, Gašper Košmrlj, Douglas F. Rall, 2015, original scientific article

Abstract: V članku vpeljemo koncept zaščitenega podgrafa. Množica le-teh po definicji leži med množico konveksnih in 2-izometričnih podgrafov, hkrati pa ni primerljiva z množico izometričnimih podgrafov. Dokažemo nekatere metrične lastnosti zaščitenih podgrafov ter koncept uporabimo v dominacijski igri, v kateri dva igralca, Dominator in Zavlačevalka, izmenično izbirata vozlišča grafa, tako da vsako izbrano vozlišče poveča množico dominiranih vozlišč. Dominatorjev cilj je končati igro, tj. dominirati celoten graf, čim hitreje, medtem ko je Zavlačevalkin cilj odigrati čim več potez. Igralno dominacijsko število je število potez v igri, ko Dominator začne in oba igralca igrata optimalno. Kot glavni rezultat članka dokažemo, da igralno dominacijsko število grafa ni nikoli manjše, kot igralno dominacijsko število njegovega zaščitenega podgrafa. Predstavljenih je tudi več aplikacij tega rezultata.
Keywords: dominacijska igra, igralno dominacijsko številko, konveksni podgraf, (2-)izometrični podgraf
Published: 10.07.2017; Views: 684; Downloads: 90
.pdf Full text (690,85 KB)
This document has many files! More...

7.
Covering codes in Sierpiński graphs
Laurent Beaudou, Sylvain Gravier, Sandi Klavžar, Matjaž Kovše, Michel Mollard, 2010, original scientific article

Abstract: Za dani graf ▫$G$▫ in celi števili ▫$a$▫ in ▫$b$▫ je ▫$(a,b)$▫-koda grafa ▫$G$▫ množica vozlišč ▫$C$▫, tako da ima vsako vozlišče iz ▫$C$▫ natanko ▫$a$▫ sosedov v ▫$C$▫, vsako drugo vozlišče pa natanko ▫$b$▫ sosedov v ▫$C$▫. V tem prispevku klasificiramo števila ▫$a$▫ in ▫$b$▫, za katera obstajajo ▫$(a,b)$▫-kode v grafih Sierpińskega.
Keywords: graph theory, codes in graphs, perfect codes, Sierpiński graphs
Published: 10.07.2017; Views: 510; Downloads: 90
.pdf Full text (786,68 KB)
This document has many files! More...

8.
Connectivity of Fibonacci cubes, Lucas cubes, and generalized cubes
Jernej Azarija, Sandi Klavžar, Jaehun Lee, Yoomi Rho, 2015, original scientific article

Abstract: If ▫$f$▫ is a binary word and ▫$d$▫ a positive integer, then the generalized Fibonacci cube ▫$Q_d(f)$▫ is the graph obtained from the ▫$d$▫-cube ▫$Q_d$▫ by removing all the vertices that contain ▫$f$▫ as a factor, while the generalized Lucas cube ▫$Q_d(\stackrel{\leftharpoondown}{f})$▫ is the graph obtained from ▫$Q_d$▫ by removing all the vertices that have a circulation containing ▫$f$▫ as a factor. The Fibonacci cube ▫$\Gamma_d$▫ and the Lucas cube ▫$\Lambda_d$▫ are the graphs ▫$Q_d({11})$▫ and ▫$Q_d(\stackrel{\leftharpoondown}{11})$▫, respectively. It is proved that the connectivity and the edge-connectivity of ▫$\Gamma_d$▫ as well as of ▫$\Lambda_d$▫ are equal to ▫$\left\lfloor \frac{d+2}{3}\right\rfloor$▫. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all ▫$f$▫ and all ▫$d \le9$▫.
Keywords: Fibonacci cube, Lucas cube, generalized Fibonacci cube, generalized Lucas cube, connectivity, combinatorics on words
Published: 10.07.2017; Views: 613; Downloads: 114
.pdf Full text (740,04 KB)
This document has many files! More...

9.
Wiener numbers of pericondensed benzenoid hydrocarbons
Sandi Klavžar, Ivan Gutman, Amal Rajapakse, 1997, original scientific article

Abstract: Using a recently developed technique for the calculation of the Wiener number (W) of benzenoid systems, we determine explicit expressions for W for several homologous series of pericondensed benzenoid hydrocarbons. An elementary proof for the correctness of the used method is also included.
Keywords: mathematics, chemical graph theory, distance in graphs, Wiener number, benzenoids
Published: 05.07.2017; Views: 729; Downloads: 128
.pdf Full text (16,93 MB)
This document has many files! More...

10.
How long can one bluff in the domination game?
Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj, 2017, original scientific article

Abstract: The domination game is played on an arbitrary graph ▫$G$▫ by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. Minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs ▫$K(n,2)$▫, za ▫$n \ge 6$▫, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.
Keywords: domination game, game domination number, bluff graphs, minus graphs, generalized Petersen graphs, Kneser graphs, Cartesian product of graphs, Hamming graphs
Published: 09.05.2017; Views: 671; Downloads: 361
.pdf Full text (56,60 KB)
This document has many files! More...

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