Search

V magistrskem delu predstavljamo osnovne pojme kombinatoričnih iger na treh variacijah igre Križci in krožci: simetrične igre, igre tipa Izdelovalec-Lomilec in igre tipa berač. Obravnavamo igre Križci in krožci zrazličnimi dimenzijami igralnega polja in predstavimo različne strategije igralcev ter opazujemo odnose med spremembo dimenzije igralnega polja ter rezultatom igre. Ugotavimo, da v simetrični igri na polju velikosti $n^d$ z uporabo ustrezne strategije zmaga Prvi igralec, če je z uporabo iste strategije zmagal na polju $n^k, k

V magistrskem delu obravnavamo izbrane vsebine s področja kombinatorične teorije iger. V uvodnih poglavjih predstavimo primere preprostih kombinatoričnih iger ter navedemo nekatere osnovne definicije in trditve, na katerih temelji teorija kombinatoričnih iger. Predstavimo dokaz Zermelovega izreka in podamo več primerov osnovnih strategij, ki jih igralca uporabljata pri igranju. Glavni poudarek je na igrah normalnega tipa, pri katerih zmaga tisti igralec, ki napravi zadnjo potezo. Ob tem obravnavamo pojme kot so: položaj in njegov tip, vsota položajev in ekvivalenca položajev, na katerih temelji kombinatorična teorija iger. V drugem delu predstavimo kombinatorično teorijo nepristranskih iger ob pomoči igre Nim in dokažemo Sprague-Grundyev izrek, ki nam omogoča celostno razumevanje ekvivalence pri nepristranskih igrah. Podobno predstavimo tudi njegovo različico za pristranske igre ob pomoči igre Hackenbush. Skozi celotno magistrsko delo povezujemo in odkrivamo zveze med obravnavanimi vsebinami, ki jih dopolnjujemo z rešenimi praktičnimi primeri. In this master's thesis, we discuss chosen topics of combinatorial game theory. In the opening section we introduce some simple combinatorial games and give some basic definitions and theorems on which the theory of combinatorial games is based. We present a proof of Zermelo's theorem, and provide some examples of basic strategies that can be used by players while playing. The main emphasis is on the normal-play games, in which the player that makes the last move wins. Along the way we study the conccepts such as position in the game and its type, sum of positions and equivalence of positions, on which the combinatorial game theory is based. In the second part we present combinatorial theory of impartial games with the help of the Nim game. We prove the Sprague-Grundy's theorem, which enables us to comprehensively understand the equivalence in impartial games. Similarly, we also present a version for partizan games with the help of the Hackenbush game. Through the entire master's thesis, we connect and discover the relations between the discussed contents, which are supplemented with the solved practical examples.

V magistrskem delu obravnavamo izbrane vsebine s področja teorije grafov, te so barvanje vozlišč grafov, tetivni grafi in grafi intervalov. V prvem delu navedemo vse potrebne definicije, trditve in izreke skupaj z dokazi. Podamo več karakterizacij tetivnih grafov in grafov intervalov, kjer se osredotočamo na obravnavo z vidika presečnih grafov. Navedene vsebine tudi povezujemo in odkrivamo zveze med njimi, posvetimo se predvsem barvanju tetivnih grafov in grafov intervalov. V drugem delu magistrskega dela podajamo primer obravnave navedenih vsebin v srednješolskem izobraževanju vključimo tudi obravnavo vsebine uvod v teorijo grafov ter vsebine, ki združuje navedeno. Vsebine podajamo v obliki vsebinsko-metodičnih priprav na poučevanje, v sklopu katerih predlagamo tudi učne oblike in metode, učne pripomočke in časovni razpored aktivnosti ter navajamo matematična znanja, ki jih dijaki razvijajo tekom učnih ur. Podajamo teoretične osnove nekaterih didaktični elementov ter navajamo načela, s katerimi je poučevanje po pripravah usmerjeno in cilje, ki jih uresničuje. In this Master’s thesis, we discuss chosen topics of graph theory. These are: vertex colouring, chordal graphs and interval graphs. In the first part, we list all of the necessary definitions, claims and theorems together with their proofs. We provide additional characterization of chordal and interval graphs. We focus on discussing them from the intersection graphs' viewpoint. We connect all of the topics and we search for relations between them. We focus on chordal graphs colouring and interval graphs colouring. In the second part, we provide example of discussing above-mentioned topics in secondary education. We also add discussion about introduction into graph theory and the topic, which combines all of the mentioned topics. Topics are presented in the form of content and methods based lesson plan. We suggest teaching forms, methods, materials, aids, time schedule for activities and we list mathematical knowledge that students develop during the lessons. We introduce theoretical base of some didactics elements, we list principles which help us direct our teaching and goals which are realized.

V magistrskem delu so obravnavane lastnosti in povezave med posameznimi robnimi množicami grafa, ki jih sestavljajo robna, ekscentrična, periferna, konturna in ekstremna vozlišča grafa. Zanimale nas bodo predvsem povezave med robnimi in geodetskimi množicami grafa, posebej se bomo posvetili preučevanju konturne množice grafa. V prvem poglavju so zapisani osnovni pojmi in definicije iz teorije grafov, ki jih bomo potrebovali v nadaljevanju. V drugem poglavju definiramo tipe robnih množic, navedemo osnovne lastnosti le-teh in dokažemo dva realizacijska izreka, ki govorita o obstoju poljubnega grafa pri podanih kardinalnostih različnih skupin robnih množic. V tretjem poglavju navedemo rezultate, ki pravijo, da je konturna množica tetivnih, razdaljno hereditarnih, 3-SDH in HHD-prostih grafov geodetska množica. Obravnavamo tudi konturno množico dvodelnih grafov in dokažemo, da za vsak diameter $kgeq 8$ obstaja dvodelni graf, katerega konturna množica ni geodetska. V zadnjem razdelku obravnavamo konturne in geodetske množice delnih kock. In this master thesis we are dealing with the properties and relationships between boundary sets of a graph consisting of boundary, eccentric, peripheral, contour and extreme vertices of a graph. We study mostly the relationship between boundary sets and geodetic sets of an arbitrary graph, in particular we focus on the contour set of a graph. The first chapter introduces some basic definitions from graph theory that are needed for further understanding of the subject. In the second chapter we define different types of boundary sets and obtain some basic structural properties. We prove two realization theorems, which are referring to the existence of a graph, where cardinalities of different groups of boundary sets are given. In the third section we present results stating that the contour set of chordal, distance hereditary, 3-SDH and HHD-free graphs is the geodetic set. We also focus on the contour set of bipartite graphs and prove that for every diameter $kgeq 8$ there exists a bipartite graph, whose contour set is not a geodetic set. In the last section we study contour and geodetic sets of partial cubes.

Mostovni grafi so zelo dobro raziskana družina grafov. Pojavljajo se na različnih področjih, ne samo diskretne matematike, na primer v geometrični teoriji grup. V disertaciji se ukvarjamo z različnimi problemi, povezanimi z mostovnimi grafi in njihovimi posplošitvami. Pokažemo, do so ti grafi uporabni tudi zunaj same teorije grafov, saj jih povežemo s teorijo kompleksov. Med drugim se ukvarjamo s povezavo teh grafov in določenih tipov konveksnosti v grafih in z uporabo mostovnih grafov v grafih, prirejenih delno urejenim množicam. Disertacija je sestavljena iz treh delov, pri čemer v vsakem delu prikažemo uporabnost mostovnih grafov na izbranem področju. V prvem delu vpeljemo in proučujemo bukolične komplekse, skupno posplošitev sistoličnih in CAT(0) kubičnih kompleksov. Bukolične komplekse proučujemo z vidika teorije grafov, topološkega vidika in iz perspektive geometrijske teorije grup. Okarakteriziramo jih preko določenih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več že znanih rezultatov. Prav tako dokažemo, da so bukolični kompleksi skrčljivi in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti. V drugem delu posplošene mostovne grafe obravnavamo vzporedno s 3-Steinerjevo konveksnostjo. In sicer dokažemo, da so grafi $G$, v katerih so j-krogle g_3-konveksne za vsak j ≥ 1, natanko grafi, ki ne vsebujejo hiše niti grafov K_{2,3} in W_4^- kot induciranih podgrafov, in je vsak cikel v G, dolžine vsaj šest, dobro premostljiv. Okarakteriziramo torej grafe z g_3-konveksnimi kroglami. V tretjem delu disertacije usmerimo pozornost na grafe pokritij-neprimerljivosti delno urejenih množic (C-I grafe) in iščemo njihovo povezavo z mostovnimi grafi. Pokažemo, da v razredu C-I grafov sovpada kar nekaj različnih grafovskih družin. In sicer, v razredu C-I grafov ni razlike med mostovnimi grafi, tetivnimi grafi in grafi intervalov. Ker je problem prepoznavanja grafov pokritij-neprimerljivosti v splošnem NP-poln, se osredotočimo na določene razrede mostovnih grafov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf oziroma razcepljeni graf. Med drugim okarakteriziramo grafe pokritij-neprimerljivosti tako med bločnimi oziroma razcepljenimi grafi kot med tetivnimi kografi. Slednje karakterizacije dajo tudi linearen algoritem za prepoznavanje bločnih oziroma razcepljenih grafov, oziroma tetivnih kografov, ki so grafi pokritij-neprimerljivosti. Bridged graphs are one of the very well investigated graf classes. They do not appear just in discrete mathematics but also in geometric group theory. In this dissertation thesis, different problems connected with bridged graphs and their generalizations are presented. They are used in the study of certain complexes, thus being applicable also outside graph theory. In particular, we present the relation between bridged graphs and some types of convexities in graphs and also the relation of these class of graphs with graphs obtained from posets. The dissertation is composed from three parts where in each part the use of bridged graphs on a chosen area is presented. In the first part we introduce and investigate bucolic complexes, a common generalization of systolic complexes and of CAT(0) cubical complexes. We study bucolic complexes from graph-theoretic and topological perspective, as well as from the point of view of geometric group theory. In particular, we characterize bucolic complexes by some properties of their 2-skeleta and 1-skeleta (that we call bucolic graphs), by which several known results are generalized. We also show that bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties. In the second part we investigate generalized bridged graphs parallel with 3-Steiner convexity. We prove that the graphs with g_3-convex j-balls for every j ≥ 1, are exactly the graphs without house, K_{2,3} and W_4^- as induced subgraphs in which all cycles of length at least six are well-bridged. Thus we characterize graphs with g_3-convex balls. In the last part of the thesis we focus on cover-incomparability graphs of posets (C-I graphs), studying the connection of these graphs with bridged graphs. We show that in the class of C-I graphs some different graph classes coincide. In particular, in the class of C-I graphs there is no difference among the bridged graphs, the chordal graphs and the interval graphs. Since the problem of recognizing cover-incomparability graphs of posets was shown to be NP-complete in general, we concentrate on (classes of) bridged graphs. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block graphs, split graphs and chordal cographs, respectively. The latter characterizations yield polynomial algorithms for recognition of block graphs, split graphs and chordal cographs, respectively, that are cover-incomparability graphs.

V magistrskem delu obravnavamo posplošitve problema iskanja največjega prirejanja v dvodelnem grafu. Dan je dvodelen graf G=(A+B,E) in funkcija potreb, ki vsakemu vozlišču v množici B priredi t.i. potrebo vozlišča. V problemu kvaziprirejanja v dvodelnem grafu G iščemo takšno podmnožico F množice povezav E, da ima vsako vozlišče iz B vsaj toliko F-incidenčnih povezav kot ima potrebo, vozlišča iz množice A pa imajo kar se da uravnoteženo število pripadajočih F-incidenčnih povezav. Problem lahko variiramo tako, da vozliščem iz množice A omejimo število F-incidenčnih povezav s kapacitetno funkcijo in tedaj govorimo o f,g-kvaziprirejanju. V tem primeru nas zanima ali obstaja množica F, ki zadošča kapacitetni funkciji in funkciji potreb v danem dvodelnem grafu. V prvem poglavju so opisani osnovni pojmi in definicije, ki jih potrebujemo v nadaljevanju. V drugem poglavju posplošimo definicijo prirejanja in nekaterih pripadajočih pojmov, ki nam pomagajo dokazati lastnosti kvaziprirejanj. V tretjem poglavju poiščemo učinkovit algoritem za iskanje g-kvaziprirejanja, ki mu dokažemo pravilnost delovanja ter linearno časovno in prostorsko zahtevnost. Algoritem v nadaljevanju dopolnimo tako, da učinkovito poišče optimalno g-kvaziprirejanje ob dodajanju ali odvzemanju vozlišča. V zadnjem poglavju predstavimo odločitveni problem obstoja f,g-kvaziprirejanja. Kot rezultat navedemo široko posplošitev Hallovega poročnega izreka. In master thesis we discuss generalizations of the problem of determining maximum matching in bipartite graphs. A bipartite graph G=(A+B,E), and a need function that assigns the so-called need of every vertex in B, are given. In the quasi-matching problem in a bipartite graph G we seek a subset of edges F, where every vertex from B has at least as many F-incident edges as its need, and vertices in A have the number of F-incident edges as balanced as possible. We can vary the problem by limiting the number of F-incident edges with a capacity function to vertices from A, and we talk about f,g-quasi-matching. In that case we are interested in, whether a set F that fulfils the capacity and need function in the bipartite graph, actually exists. The first chapter introduces basic concepts and definitions that are needed for further understanding of the thesis. In the second chapter we generalize the definition of matching and some concepts that help us to prove some quasi-matching properties. In third chapter we present an efficient algorithm for finding g-quasi-matching in a bipartite graph, for which we prove correctness and linear time and space complexity. In the last part of the chapter we improve the algorithm so that it efficiently finds g-quasi-matching if a vertex is added or taken. In the last chapter we present decision problem of existence of f,g-quasi-matching. As a result generalization of Hall's marriage theorem is given.

Dominacija na grafih je intenzivno raziskovana veja v teoriji grafov. Leta 1963 je Vizing postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov kvečjemu večje od produkta njunih dominantih števil. Mnogo delnih rezultatov je bilo dokazanih, vendar pa je le-ta še vedno eden izmed največjih odprtih problemov v študiju dominacije na grafih. V tem diplomskem delu so v ospredju obravnavani najbolj znani izreki Vizingovega tipa za različne dominacijske invariante. Na začetku predstavimo nekaj dejstev o dominaciji na kartezičnem produktu. Opišemo znan Clark-Suenov rezultat Vizingovega tipa in t.i. razstavljive grafe, za katere Vizingova domneva drži. Drugi del se nanaša na pet dominacijskih invariant totalno, celoštevilsko, zgornjo, deljeno dominantno število in dominacijo po parih. Predstavljeni so izreki Vizingovega tipa za posamezne dominacijske parametre, kot na primer izrek za deljeno-dominantno število, Ho-jev izrek o totalnem dominantnem številu in izrek Vizingovega tipa za zgornje dominantno število. Domination in graphs is an extensively studied branch of graph theory. In 1963 Vizing conjectured that the domination number of the Cartesian product of two graphs is at least the product of their domination numbers. Several partial results have been proven, but the conjecture still remains one of the biggest open problems in the study of domination in graphs. In the thesis our main focus are some of the most important variations of Vizing's conjecture for various domination-type invariants. At the beginning we explain some facts about domination in Cartesian products. We present famous Clark-Suen Vizing-type result and the so-called decomposable graphs, for which Vizing's conjecture is true. In the last part we survey versions for five main domination invariants total, integer, upper, fractional and paired. Further on we describe Vizing-type theorems for several domination parameters, for instance theorem for fractional domination number, conjecture for total domination number solved by Ho and Vizing-type theorem for upper domination number.

Obstoja hamiltonske prizme v grafu leži med problemoma obstoja Hamiltonove poti in obstoja 2-sprehoda v grafu, kar v diplomskem delu podrobneje osvetlimo. Pri dokazovanju obstoja hamiltonskih prizem nad grafi si pomagamo s posebnim barvanjem povezav grafa. V prvem poglavju so opisane osnovne definicije in rezultati, povezani z grafi, prizmami in hamiltonskostjo. V drugem poglavju podrobneje obravnavamo prizme nad dvodelnimi grafi, kubičnimi grafi, posplošenimi Halinovimi grafi in grafi povezav ter predstavimo nekatere rezultate, ki se nanašajo na iskanje njihovih Hamiltonovih prizem. The diploma thesis examines the existence of Hamiltonian prisms over graphs. The problem of the existence of a Hamiltonian prism in a graph is directly related to the problems of the existence of a Hamiltonian path and of a 2-walk in a graph, which is analyzed in more detail in this work. In proving the existence of a Hamiltonian prism over a graph we use a special colouring of its edges. In the first chapter basic definitions and results related to graphs, prisms and hamiltonicity are described. In the second chapter we study in more detail the prisms over bipartite graphs, cubic graphs, generalized Halin graphs and line graphs, and present some results concerning the search for their Hamiltonian prisms.

Diplomsko delo obravnava geodetsko in ovojniško število standardnih produktov grafov s poudarkom na kartezičnem in krepkem produktu. V prvem delu so zapisane osnovne definicije s področja teorije grafov, ki se uporabljajo v nadaljevanju. V naslednjem poglavju si pogledamo grafe, za katere je geodetsko število enako ali za ena manjše od števila vozlišč ter enako za ovojniško število. Sledi poglavje v katerem se osredotočimo na geodetsko in ovojniško število v kartezičnem produktu grafov in si pogledamo robne množice. Zadnji del diplomske naloge je namenjen geodetskemu in ovojniškemu številu v krepkem produktu grafov, kjer so podane meje za obe števili in natančne vrednosti za določene tipe grafov. The geodetic and hull number in standard products of graphs is studied in this diploma thesis with special emphasis on the Cartesian and Strong product of graphs. The fifirst chapter contains basic defifinitions from the area of graph theory that are needed later. In the next chapter we take a look at graphs for which the geodetic number is equal or one less than the order of a graph and similar for the hull number. In Chapter 3 the focus is on the geodetic and hull number in the Cartesian product graphs and on their boundary sets. The last part of diploma is devoted to geodetic and hull number in Strong product of graphs, where the bounds and exact values for different types of graphs are given.

Naj bo Y podmnožica množice celih števil in G = (V,,E) graf. Funkcija, ki vsakemu vozlišču priredi neko vrednost iz množice Y, tako da je seštevek vrednosti v soseščini vsakega vozlišča vsaj 1, se imenuje celoštevilska dominacijska funkcija grafa G. Vrednost celoštevilske dominacijske funkcije v poljubni podmnožici S množice V definiramo kot seštevek vrednosti v vsakem vozlišču iz S. Teža celoštevilske dominacijske funkcije je vrednost funkcije v množici vozlišč V. Poiskati želimo po teži najmanjšo celoštevilsko dominacijsko funkcijo grafa G. V tem delu so predstavljene variacije različnih celoštevilskih dominacij, kot so {k}-dominacija, k-kratna dominacija, predznačena dominacija in minus dominacija, ki jih obravnavamo na razredih grafov kot so poti, cikli, pahljače, kolesa, ponve in trampolini. Podan je algoritem, ki v linearnem času reši problem L-dominacije na strogo tetivnih grafih. Prav tako je podana časovna zahtevnost izračuna naštetih celoštevilskih dominacijskih invariant za razrede dualno tetivnih, dvojno tetivnih in ravninskih grafov. Na koncu je na podoben način predstavljena 2-mavrična dominacija. Let Y be a set of integers. An integer dominating function of graph G = (V,,E) is a function that sets a value from Y to every vertex from V in such way that sum of values from neighbourhood of every vertex is at least 1. Let S be a subset of V. The value of an integer dominating function in S is defined as the sum of its values over vertices from S. The weight of integer dominating function is its value in V. The goal is to find a minimum weight integer dominating function of graph G. In this work we present the variation of integer domination such as {k}-domination, k-tuple domination, signed domination, and minus domination numbers which we study on classes of graphs such as paths, cycles, fans, wheels, pans and suns. We give the algorithm that solves L-domination in linear time on strongly chordal graphs. We also give complexity results for the mentioned integer domination invariants on dually chordal, doubly chordal, and planar graphs. At the end a 2-rainbow domination is presented in a similar way.