Search

The ▫$Theta$▫-graph ▫$Theta(G)$▫ of a partial cube ▫$G$▫ is the intersection graph of the equivalence classes of the Djokovic-Winkler relation. ▫$Theta$▫-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, ▫$Theta(G)$▫ is complete if and only if ▫$G$▫ can be obtained from ▫$K_1$▫ by a sequence of (newly introduced) dense expansions. ▫$Theta$▫-graphs are also compared with familiar concepts of crossing graphs and ▫$tau$▫-graphs. ▫$Theta$▫-graf, ▫$Theta(G)$▫, delne kocke ▫$G$▫, je presečni graf ekvivalenčnih razredov Djokovic-Winklerjeve relacije. Karakterizirani so ▫$Theta$▫-grafi, ki so 2-povezani, drevesa, ali polni grafi. V posebnem, ▫$Theta(G)$▫ je polni graf natanko tedaj, ko lahko ▫$G$▫ dobimo iz ▫$K_1$▫ z zaporedjem (na novo vpeljanih) gostih ekspanzij. ▫$Theta$▫-grafi so tudi primerjani s sorodnima konceptoma križnih grafov in ▫$tau$▫-grafov.

V magistrskem delu obravnavamo načine sklepanja in utemeljevanja pri pouku matematike z različnih zornih kotov ter poudarjamo pomembnost aktivnih metod poučevanja – preiskovalnih metod. Preiskovalna metoda je aktivna metoda pouka, kjer učenci samostojno preiskujejo, uporabljajo različne metode, učitelji pa učence usmerjamo, jih vodimo do zastavljenega cilja. Cilj preiskovalne metode je, da učenec pravilno reši nalogo in bodisi z uporabo uveljavljene metode ali z uporabo lastne metode. Na začetku predstavimo teoretična izhodišča teorij učenja ter prednosti in pomanjkljivosti konstruktivizma v preiskovalni situaciji v razredu. Osrednji del nadaljujemo z obravnavo osnovnih znanstvenih metod, primeri uporabe preiskovalnih metod ter uvajanju preiskovalnih metod v pouk matematike. Teoretična spoznanja ves čas prepletamo s primeri iz neposredne učne prakse, kjer skozi posamezne primere poudarimo pomembnost usmerjanja k lastnemu razmišljanju in oblikovanju lastnih ugotovitev. Opišemo tudi primere uporabe preiskovalnih metod pri samem pouku matematike v osnovni in srednji šoli. V osrednjem delu predstavimo tudi pomembne razlike med preiskovalno in običajno situacijo v razredu ter vlogo učitelja pri preiskovalni situaciji in pasti, ki se jih je potrebno zavedati pri organizaciji takega pouka. V empiričnem delu magistrskega dela predstavimo izvedbo in analizo preiskovalne situacije v razredu ter ugotovitvami praktičnega dela. V tem poglavju predstavimo tudi rezultate ankete o uporabi preiskovalnih metod med učenci, ki so sodelovali pri izvedbi preiskovalne situacije ter ankete med učitelji matematike o uporabi preiskovalnih metod pri pouku. Med raziskovalnimi problemi nas posebej zanimajo prednosti in pomanjkljivosti uporabe preiskovalnih metod v primerjavi z običajnim poukom ter analiza različnih dejavnikov, ki lahko vplivajo na kvaliteto izobraževanja v današnji šoli. Pri tem poskusimo odgovoriti tudi na večkrat aktualne teme o smiselnosti in nujnosti uporabe preiskovalnih metod v izobraževanju. V sklepu na kratko povzamemo glavne ugotovitve v nalogi ter nakažemo možne preiskovalne izzive za učence pri pouku matematike. In this master's thesis various ways of inferring and substantiating during mathematics classes are discussed from different perspectives. The importance of active teaching methods, namely the research methods, is also emphasized. A research method is an active teaching method where students research and use different methods independently and teachers give them guidance to lead them to the goal. The goal of a research method is for the student to correctly solve a task, either with an established method or her/his own method. In the first part of the master's thesis theoretical basis of teaching theories are described, as well as advantages and disadvantages of constructionism in the researched situation in class. In the second part of the thesis basic scientific methods, examples of using research methods and introduction of these methods in mathematics class are discussed. Theoretical cognitions are supported with examples of direct teaching practice where the importance of directing students towards independent thinking and formation of their own conclusions is emphasized. Examples of research methods being used in mathematics class in primary schools and high schools are also described. In the central part the important differences between the research and ordinary situation in class are described, as well as teacher's role in the research situation and traps they have to be aware of while organizing these classes. In the empirical part of the master's thesis the realization and the analysis of the research situation in class are presented together with conclusions from practical work. In this section the results of a questionnaire on using research methods, carried out among students who participated in the research situation, as well as results of a questionnaire on using research methods in class, carried out among mathematics teachers, are presented . The master's thesis focuses on advantages and disadvantages of using research methods in comparison with ordinary classes as well as on the analysis of various factors that can affect the quality of education in contemporary schools. Current topics on significance and necessity of research methods in education are also dealt with. In the conclusion main findings of the thesis are summarized and possible research challenges for children in mathematics classes are indicated.

Veliko naprav v elektromehaniki uporablja sistem prikazovanja pozicij z odpiranjem in zapiranjem stikal. Če ta naprava uporablja binarno kodo, so možnosti za napačno branje pozicije bitov in posledično napačen izhod podatka, velike. Ker se binarne besede med seboj razlikujejo za več kot en bit in ker se stikala v napravah ne premikajo sinhrono, bi morale biti spremembe bitov med besedami čim manjše. Tukaj nastopi uporaba Grayeve kode, katere značilnost je sprememba samo enega bita med bitnimi besedami. V prvem delu te naloge je predstavljen binarni številčni sistem, ki je osnova za razvoj in gradnjo Grayevih kod. Nadalje je opisana povezava in pretvarjanje med binarno in Grayevo kodo. V drugem delu je predstavljena definicija Grayevih kod in generiranje le-teh z rekurzivnim algoritmom, poznanim pod imenom binarna reflektirana Grayeva koda. Opisani sta tudi uravnotežena in monotona Grayeva koda, ki predstavljata posebni različici Grayevih kod. Nadalje so predstavljene kombinatorične Grayeve kode za permutacije, kombinacije in particije celih števil. Opisana je tudi bijekcija med nizom particij in funkcijo omejene rasti. V zadnjem delu so predstavljeni praktični primeri, ki so lahko rešeni s pomočjo uporabe različnih Grayevih kod. Many devices in electromechanics use a system of indicating position by closing and opening switches. If those devices use binary codes, the chance for reading spurious positions is increased. Because binary strings differ in more than one bit and switches do not change states exactly in synchrony, the bit changes should be reduced in order for device to give us the right result. At this point Gray code is a perfect solution, considering that Gray code is a binary numeral system, where two successive values differ in only one bit. In this thesis the first part is dedicated to describe binary numeral system which is the base for generating Gray codes. Further on in this work is the description of relation between binary and Gray codes. In the second part is presented the definition of Gray code and generating of the code with recursive algorithm, known as binary reflected Gray code. Further in this part of work there are presented combinatorial Gray codes for permutations, combinations and integer partitions. Also in this part are described balanced Gray codes and their construction. In the last part are presented practical problems, that can be solved using Gray codes.

Diplomsko delo obravnava Vennove diagrame. Osrednja tema so splošni Vennovi diagrami in grafi, ki so povezani z Vennovimi diagrami. V uvodnem poglavju predstavimo osnovne definicije iz teorije grafov, ki jih potrebujemo v nadaljevanju, definiramo Vennove diagrame ter povemo nekaj o njihovi uporabi in o primerjavi z Eulerjevimi diagrami. V drugem poglavju prikažemo obstoj Vennovih diagramov za n≥3 na primerih dveh konstrukcij in pokažemo, kdaj se jih lahko nariše z uporabo skladnih krogov. V zadnjem poglavju podrobno obravnavamo grafe, ki so povezani z Vennovimi diagrami. Najprej predstavimo Vennove duale, definiramo kdaj so Vennovi diagrami izomorfni in obravnavamo Vennove diagrame in Vennove razrede. Nato raziščemo razširitev Vennovega diagrama in podamo Winklerjevo domnevo, ki pa ostaja nepotrjena. Z odpravo omejitve enostavnosti v nadaljevanju dokažemo Grünbaumov izrek. Na koncu poglavja obravnavamo tudi minimalne in monotone Vennove diagrame. The diploma thesis focuses on Venn diagrams. The main themes are the general Venn diagrams and graphs associated with Venn diagrams. The first part examines basic definitions from the graph theory and introduces the use of Venn diagrams, which are further compared to Euler diagrams. It focuses on the definition of Venn diagrams. In the next part Venn diagrams existence for n≥3 is shown using two different constructions. It also presents how these constructions can be drawn by the use of congruent circles. In the last part graphs associated to Venn diagrams are discussed in details. First it presents Venn dual graphs, defines when they are isomorphic and deals with Venn diagrams and classes. Then it explores extension of Venn diagram and gives Winkler's conjecture, which remains unproven. By eliminating restrictions of simplicity it further proves Grünbaum's theorem. In the end it also focuses on minimal and monotone Venn diagram.

V prvem poglavju diplomskega dela predstavimo osnovne pojme iz teorije grafov, podamo definicije in preproste primere grafov. V drugem poglavju definiramo metrično dimenzijo grafa. V tretjem poglavju se posvetimo grafom z majhno metrično dimenzijo. Poti so edini grafi z metrično dimenzijo ena. Ogledamo si lastnosti, ki so značilne za grafe z metrično dimenzijo dva. Ob koncu tega poglavja se seznanimo še z metrično dimenzijo ciklov, ki so predstavniki grafov z metrično dimenzijo dva. V četrtem poglavju obravnavamo metrično dimenzijo različnih primerov grafov. Najprej spoznamo metrično dimenzijo polnih grafov, nato dreves in na koncu še mrež pri katerih kot poseben primer pogledamo hiperkocke. Za drevesa podamo tudi enostaven algoritem za postavitev baznih vozlišč. V zadnjem poglavju se ukvarjamo z uporabo metrične dimenzije. Podamo primere uporabe metrične dimenzije v miselnih problemih in igrah, navigaciji, računalništvu in kemiji. In first chapter of this thesis we present the basic concepts from theory of graphs, we give definitions and simple examples of graphs. In second chapter we define metric dimension of a graph. In third chapter we focus on graphs with small metric dimension. Paths are the only graphs with metric dimension one. We take a closer look at properties, typical for graphs with metric dimension two. At the end of this chapter we get to know metric dimension of cycles, which represent graphs with metric dimension two. In fourth chapter we look at metric dimension of different examples of graphs. At first we learn metric dimension of complete graphs, than trees and in the end grid graph where we deal with a special example of hypercubes. For trees we give a simple algorithm for setting up vertices from a basis. In the last chapter we deal with applications of metric dimension. We give examples how to use metric dimension in mind games, combinatorial games, navigation, computer science and in chemistry.

Diplomsko delo v prvem poglavju obravnava Sylvester-Gallaijev izrek: predstavitev, formulacijo, možne posplošitve in dokaze ter zgodovino. Začetek slednje sega v konec 19. stoletja, ko je James Joseph Sylvester ustvaril temelje, ki so se kasneje razvili v oblikovanje Sylvester-Gallaijevega izreka. Sam je namreč pri raziskovanju raznih konfiguracij sestavljenih iz mrež ugotovil, da ni možno določiti končnega števila točk tako, da bo vsaka premica, ki poteka skozi dve točki šla še skozi tretjo iz iste množice, razen, če vse točke ležijo na isti premici. Njegovo ugotovitev je kasneje v afini realni ravnini dokazal Tibor Gallai, katerega dokaz pa ni ostal osamljen. V diplomskem delu sta podana še dokaza L. M. Kellya in R. Ste inberga. Poleg vsega naštetega pa so v prvem poglavju, predvsem zaradi lažjega razumevanja dokazov Sylvester-Gallaijevega izreka, predstavljene osnovne značilnosti evklidske, afine in projektivne geometrije in Motzkinov izrek kot ena izmed mnogih posplošitev Sylvester-Gallaijevega izreka. Drugo poglavje v uvodnem delu zajema definicije pojmov kot so: metrični prostor, premica v poljubnem metričnem prostoru, trojna relacija, vmesnost. Sicer pa je v celoti namenjeno posplošitvi Sylvester-Gallaijevega izreka za metrične prostore, tako imenovanemu Sylvester-Chvátalovemu izreku. Vašek Chvátal je namreč razširil pojem premic v poljubnih metričnih prostorih in podal domnevo, ki posplošuje Sylvester-Gallaijev izrek. Chvátalova domneva je bila potrjena kot izrek, ki smo ga, zaradi lažjega dokazovanja, tudi s pomočjo primerov, razdelili na dva dela: Če za vsake 3 točke iz M velja, da ležijo na neki skupni premici, potem ta premica vsebuje vse točke iz M. Oziroma, če obstajajo 3 točke iz M, ki ne ležijo na skupni premici, potem obstaja premica, ki vsebuje natanko 2 točki. This diploma thesis in first chapter beginns with Sylvester-Gallai theorem: its presentation, formulation, generalizations, proofs and history. James Joseph Sylvester has been investigated a figure which is a discrete set of points having the property that the line joining any two of them contains not only these two but infinitely many. It was probably the investigation of such configurations that led Sylvester to propose his problem of 1893: Prove that it is not possible to arrange any finite number of real points so that a right line through every two of them shall pass through a third, unless they all lie in the same right line. A Sylvester question was solved by Gallai, who gave an affine proof, proves has been followed by a Steinberg’s proof in the projective plane and Kelly’s Euclidean proof. First chapter also describes features of Euclidean, affine, projective plane and Motzkin generalization as one of many generalizations of Sylvester-Gallai theorem. The second chapter begins with definitions of concepts like metric space, a line in arbitrary metric space, a ternary relation, betwenness. The main purpose of the chapter is to present and prove Sylvester-Chvátal theorem. Vašek Chvátal extended the notion of lines to arbitrary metric spaces and made a conjecture that generalizes the Sylvester-Gallai theorem. Proof splits into two parts: If every three points of M are contained in some line, then some line consists of all points of M and if some three points of M are contained in no line, then some line consists of precisely two points.

V diplomskem delu bomo podrobneje obravnavali konveksni politop imenovan permutaeder. V prvem poglavju bomo spoznali matematične definicije nekaterih pojmov, ki jih bomo potrebovali v nadaljevanju. V drugem poglavju si bomo pogledali dokaz, da je graf permutaedra hamiltonski graf. V tretjem poglavju bomo dokazali, da razdalje med oglišči v n-dimenzionalnem permutaedru zavzemajo vsa soda števila. V četrtem poglavju si bomo pogledali asociaeder, ki posplošuje permutaeder. In the thesis we discuss in more detail the convex polytope called permutohedron. In the first chapter we present mathematical definitions of certain concepts which we need later on. In the second chapter we show that the graph of permutohedron is a Hamiltonian graph. In the third chapter we prove that the distances between the vertices in n-dimensional permutohedron take all even numbers. In the fourth chapter we look at another polytope associahedron, which generalizes permutohedron.

Diplomsko delo obravnava hamiltonsko dopolnitev grafa. Število hamiltonske dopolnitve grafa G je najmanjše število povezav, ki jih moramo dodati grafu, da ta postane hamiltonski graf. V prvem poglavju predstavimo osnovne definicije iz teorije grafov in algoritmov, ki jih potrebujemo v nadaljevanju. Nato definiramo problem hamiltonske dopolnitve grafa ter soroden problem pokrivanja vozlišč s potmi. V tretjem poglavju predstavimo algoritma za hamiltonsko dopolnitev dreves. V četrtem poglavju opišemo reševanje hamiltonske dopolnitve grafa za poljuben graf. Na koncu diplomskega dela opišemo sorodne probleme. The thesis is about the Hamiltonian completion of a graph G. We define the Hamiltonian completion number of a graph G, to be the minimum number of edges to be added to G in order to make it Hamiltonian. In the first chapter the basic defnitions from graph theory and algorithms, necessary for our purpose, are presented. Then the Hamiltonian completion problem and the similar problem of a path cover are defned. The third chapter is about the algorithms for the Hamiltonian completion for trees. In the fourth chapter the Hamiltonian completion problem for an arbitrary graph is considered. The thesis ends with a description of the problems, similar to the Hamiltonian completion problem.

V diplomskem delu so predstavljena X-drevesa, binarna X-drevesa, X-drevesa s korenom in filogenetska X-drevesa. Predstavljena sta primera uporabe logenetskih dreves v biologiji. Predstavljeni so tudi X-razcepi in Bunemanov izrek o X-razcepih. Obravnavana je tudi delna urejenost X-dreves. In this thesis we consider X-trees, binary X-trees, rooted X-trees and phylogenetic X-trees. Applications of phylogenetic trees in biology are presented. We consider also X-splits and we show Buneman's theorem about X-splits. Partial order of X-trees is also considered.

Diplomsko delo obravnava adaptivne identifikacijske kode v grafih, ki so povezane z identi- fikacijskimi kodami. Pri tem obravnavamo problem, kjer fizelimo odkriti okvarjeno vozlišče v grafu tako, da postavljamo vprašanja ali neka krogla vsebuje okvarjeno vozlišče. Cilj adaptivnih identifikacijskih kod je minimizirati število vprašanj, ki so potrebna za odkritje okvarjenega vozlišča, če slednje obstaja. To število označimo z ar(G). V uvodnem poglavju definiramo osnovne pojme iz teorije grafov in kod v grafih, ki jih uporabljamo v nadaljevanju. V drugem poglavju določimo zgornjo in spodnjo mejo za število ar(G) v regularnih grafih. V podpoglavjih omejimo število ar(G) v kvadratni, kral- jevi in trikotni mreži. Ob tem obravnavamo tudi primere, ko je okvarjenih več vozlišč. V tretjem poglavju predstavimo igro Renyijevega tipa, kjer iščemo neznano točko (x y) v pravokotni mreži s postavljanjem vprašanj glede na podpravokotnike. Pri tem je cilj minimizirati število vprašanj. Pri tem uporabimo drevesno in linearno iskanje. In this thesis, we consider adaptive identification, which is closely connected with identifying codes in graphs. We are able to ask if there is a faulty vertex in the ball Br(x). The goal in adaptive identification is to minimize the maximum number of queries, which are necessary to discover the faulty vertex, if it exists. We denote by ar(G) this optimum number. In the initial section we give necessary definitions from graph theory and codes in graphs that we need later. In second section we show the lower and upper bound for the parameter ar(G) in regular graphs. In the subsections we limit the number ar(G) in square, king and triangular lattice. We also consider the cases, where there can be l faulty vertices, for l>1. In third section we present Renyi type of game, where we are looking for unknown point (x y) in rectangle lattice by posing questions to subrectangles. Our goal here is also to minimize the number of queries. For this we use tree and linear search.

V uvodnem poglavju predstavimo osnovne definicije iz teorije grafov, ki jih potrebujemo v nadaljevanju in povemo še nekaj o kodah v grafih. V naslednjem poglavju definiramo diskriminatorne kode, podamo nekaj primerov in dokažemo spodnjo in zgornjo mejo za moč minimalne diskriminatorne kode izražene glede na število atributov. V tretjem poglavju pokažemo povezavo med diskriminatornimi in identifikacijskimi kodami v hiperkockah. V četrtem poglavju obravnavamo diskriminatorne kode v drevesih in opišemo algoritem linearne časovne zahtevnosti glede na število vozlišč drevesa, ki za dano drevo poišče minimalno diskriminatorno kodo v drevesu in njegovo delovanje prikažemo na primeru. V zadnjem poglavju podamo za vnaprej podano število atributov konstrukcijo dvodelnih ravninskih grafov brez dvojčkov, ki imajo največje število posameznikov in pokažemo povezavo z ravninskimi triangulacijami. In the preliminaries we give necessary definitions from graph theory and codes in graphs that we need later. In the next chapter we define discriminating codes, give some examples and show lower and upper bounds for the size of minimal discriminating codes, expressed in terms of the number of atributes of a given graph. In the third chapter we show the relation between discriminating and identifying codes in hypercubes. In the fourth chapter discriminating codes in trees are treated and linear time algorithm for finding a minimal discriminating code in a tree is given and ilustrated with an example. In the last chapter we describe all bipartite planar graphs without twins with a property, that for a given number of atributes they have the maximal number of individuals, and we show their relation with planar triangulations.