| Title: | Množice točk in vozlišč v splošni legi |
|---|
| Authors: | ID Gašparič, Barbara (Author)
ID Klavžar, Sandi (Mentor) More about this mentor...  |
|---|
| Files: |  MAG_Gasparic_Barbara_2019.pdf (1,06 MB)
MD5: 202BC3CFF474C0865ABF0C1C0DD3D45E
PID: 20.500.12556/dkum/c5cf9710-1c34-4752-bdec-8d210ae816ef
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Master's thesis/paper |
|---|
| Typology: | 2.09 - Master's Thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| 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 |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [B. Gašparič] |
|---|
| Year of publishing: | 2019 |
|---|
| PID: | 20.500.12556/DKUM-73039 |
|---|
| UDC: | 519.17(043.2) |
|---|
| COBISS.SI-ID: | 24435720 |
|---|
| NUK URN: | URN:SI:UM:DK:QY4HQVJO |
|---|
| Publication date in DKUM: | 15.03.2019 |
|---|
| Views: | 1439 |
|---|
| Downloads: | 133 |
|---|
| Metadata: |    |
|---|
| Categories: | FNM
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
