| Title: | Razpon grafa : magistrsko delo |
|---|
| Authors: | ID Drožđek, Lara (Author)
ID Taranenko, Andrej (Mentor) More about this mentor...  |
|---|
| Files: |  MAG_Drozdek_Lara_2022.pdf (1,55 MB)
MD5: 13F5B2EA573748E2D78DDBD2328ED638
|
|---|
| 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 predstavimo osnove teorije grafov, razpone grafa, z njimi povezane pojme in rezultate. Pojem razpona grafa povežemo z določanjem največje varnostne razdalje, ki jo lahko v grafu ohranjata dva igralca, ki želita obiskati vsa vozlišča (ali vse povezave) grafa. Predstavimo tudi tri pravila premikanja, ki jih morata igralca med premikanjem po grafu upoštevati, in jih povežemo s produkti grafov.
V delu je podana tudi karakterizacija grafov, v katerih ni mogoče ohranjati pozitivne varnostne razdalje med igralcema, glede na podano pravilo premikanja po grafu.
Na koncu predstavimo polinomski algoritem za določanje razpona grafa. Katero različico razpona grafa nam algoritem izračuna, je odvisno od podanega pravila premikanja po grafu. |
|---|
| Keywords: | krepki razpon grafa, direktni razpon grafa, kartezični razpon grafa, produkti grafov, karakterizacija, algoritem, varnostna razdalja |
|---|
| Place of publishing: | Maribor |
|---|
| Place of performance: | Maribor |
|---|
| Publisher: | [L. Drožđek] |
|---|
| Year of publishing: | 2022 |
|---|
| Number of pages: | VIII, 45 f. |
|---|
| PID: | 20.500.12556/DKUM-82149 |
|---|
| UDC: | 519.17(043.2) |
|---|
| COBISS.SI-ID: | 127295235 |
|---|
| Publication date in DKUM: | 28.10.2022 |
|---|
| Views: | 941 |
|---|
| Downloads: | 105 |
|---|
| 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. |
