20.500.12556/DKUM-73039 Množice točk in vozlišč v splošni legi Sets of points and vertices in general position 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. The master thesis focuses on the classical no-three-in-line problem and two of its generalizations. The classical no-three-in-line problem is to find the maximum number of points that can be placed in the n × n grid so that no three points lie on a line. Generalizations that we are going to discuss are the no-three-in-line-in-3D problem and the general position problem in graph theory. The no-three-in-line-in-3D problem is to find the maximum number of points that can be placed in the n × n × n grid so that no three points lie on a line. The general position problem in graph theory is to find a largest set of vertices, such that no three vertices from that set lie on a common shortest path. In the first chapter, we introduce some definitions and important results from discrete mathematics and number theory which are needed in the following chapters. In the second chapter, we introduce the classical no-three-in-line problem, show the estimated upper bound for a number of non-linear points in the n × n grid at large n and see that n non-linear points can always be placed in the n × n grid. In the third chapter, we introduce the no-three-in-line-in-3D problem, show how this problem is connected with a 3D drawing of a complete graph Kn and tell the estimated number of non-linear points on n × n × n grid. In the last chapter, we introduce the general position problem in graph theory and present upper and lower bounds. The upper bounds are given in terms of different isometric covers of a graph and the lower ones are obtained by connecting general position sets with graph diameter and its packing. problem “no-three-in-line” splošna lega celoštevilska mreža 3D-slika grafa izometrično pokritje izometrični podgraf no-three-in-line problem general position integer grid 3D drawing of a graph isometric cover isometric subgraph true true false [B. Gašparič] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2019-01-24 16:32:55 2019-03-15 11:42:45 2022-08-01 23:51:37 2019-07-11 19:42:23 2019 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 24435720 URN:SI:UM:DK:QY4HQVJO MAG_Gasparic_Barbara_2019.pdf MAG_Gasparic_Barbara_2019.pdf 1 202BC3CFF474C0865ABF0C1C0DD3D45E b933db649ad7095642312af7ae98c74677b2ee66bd4829c5f149271d5c881ab2 94b35c31-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/c5cf9710-1c34-4752-bdec-8d210ae816ef https://dk.um.si/Dokument.php?lang=slv&id=132307 Fakulteta za naravoslovje in matematiko 0 0 0