Množice točk in vozlišč v splošni legiGašparič, Barbara (Avtor) Klavžar, Sandi (Mentor) problem “no-three-in-line”splošna legaceloštevilska mreža3D-slika grafaizometrično pokritjeizometrični podgrafMagistrsko 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.[B. Gašparič]20192019-01-24 16:32:55Magistrsko delo/naloga73039UDK: 519.17(043.2)COBISS_ID: 24435720NUK URN: URN:SI:UM:DK:QY4HQVJOsl