| Title: | Odprto pakiranje povezav grafa : na študijskem programu 2. stopnje Izobraževalna matematika |
|---|
| Authors: | ID Keše, Aleksandra (Author)
ID Dravec, Tanja (Mentor) More about this mentor...  |
|---|
| Files: |  MAG_Kese_Aleksandra_2025.pdf (1,62 MB)
MD5: 93126F933B5ADF11F682BD9D02779D71
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Master's thesis/paper |
|---|
| Typology: | 2.09 - Master's Thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | V magistrskem delu preučujemo lastnosti odprtega pakiranja povezav grafa. Za lažje razumevanje obravnavanega pojma najprej predstavimo osnovne pojme in rezultate iz teorije grafov ter opišemo osnovne družine grafov. V drugem delu magistrske naloge opišemo pojma odprto pakiranje povezav in povezavno odprto pakirno število ter ju predstavimo na osnovnih družinah grafov. Tretji del magistrske naloge je namenjen preučevanju mej za povezavno odprto pakirno število poljubnega grafa in identificiranju družin grafov, ki te meje dosežejo. V zadnjem delu magistrske naloge obravnavamo problem odprtega pakiranja povezav grafa kot NP-poln problem za grafe z univerzalnim vozliščem, Eulerjeve dvodelne grafe in ravninske grafe z maksimalno stopnjo največ 4. Opišemo postopek za izračun povezavnega odprtega pakirnega števila dreves in zapišemo, da obstaja algoritem, ki to število poišče v linearnem času. |
|---|
| Keywords: | odprto pakiranje povezav, povezavno odprto pakirno število, drevo, časovna zahtevnost algoritma, NP-poln problem |
|---|
| Place of publishing: | Maribor |
|---|
| Place of performance: | Maribor |
|---|
| Publisher: | [A. Keše] |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | VIII, 60 f. |
|---|
| PID: | 20.500.12556/DKUM-92869 |
|---|
| UDC: | 519.17(043.2) |
|---|
| COBISS.SI-ID: | 241649923 |
|---|
| Publication date in DKUM: | 07.07.2025 |
|---|
| Views: | 217 |
|---|
| Downloads: | 77 |
|---|
| 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. |
