| Naslov: | Igra policajev in roparjev na grafih |
|---|
| Avtorji: | ID Bastašić, Tina (Avtor)
ID Dravec, Tanja (Mentor) Več o mentorju...  |
|---|
| Datoteke: |  MAG_Bastasic_Tina_2019.pdf (318,60 KB)
MD5: 627FFE8487F2D6A8325E87B3BEA11873
PID: 20.500.12556/dkum/131741a0-026f-4c0d-bf2c-a080067ab3db
|
|---|
| Jezik: | Slovenski jezik |
|---|
| Vrsta gradiva: | Magistrsko delo/naloga |
|---|
| Tipologija: | 2.09 - Magistrsko delo |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | V magistrskem delu bomo predstavli igro policajev in roparjev na grafih, kjer se policaji in ropar premikajo po vozliščih grafa. Cilj policajev je, da eden izmed njih uspe priti na enako vozlišče kot ropar. Grafom, na katerih ima v igri z enim policajem policaj zmagovalno strategijo, pravimo policaj-zmaga grafi. Najmanjše število policajev, ki je potrebnih, da imajo zmagovalno strategijo na grafu G, imenujemo varnostno število grafa G.
Poleg igre policajev in roparjev bomo predstavili še druge različice te igre. Varnostno število grafa bomo izračunali za nekatere preproste družine grafov in predstavili spodnje in zgornje meje varnostnega števila grafa. Nato bomo pokazali, kako varnostno število retraktov grafa vpliva na varnostno število originalnega grafa. Kot bomo videli, retrakti grafov igrajo pomembno vlogo pri karakterizaciji policaj-zmaga grafov. Dokažemo, da so policaj-zmaga grafi natanko odstranljivi grafi. Predstavimo tudi policaj-zmaga urejenost in policaj-zmaga strategijo. Na koncu še dokažemo, da so tudi mostovni grafi policaj-zmaga grafi. |
|---|
| Ključne besede: | igra policajev in roparjev, varnostno število grafa, policaj-zmaga grafi, odstranljivi grafi, mostovni grafi |
|---|
| Kraj izida: | Maribor |
|---|
| Založnik: | [T. Bastašić] |
|---|
| Leto izida: | 2019 |
|---|
| PID: | 20.500.12556/DKUM-74902 |
|---|
| UDK: | 519.17(043.2) |
|---|
| COBISS.SI-ID: | 24865288 |
|---|
| NUK URN: | URN:SI:UM:DK:ANTDMAOV |
|---|
| Datum objave v DKUM: | 05.11.2019 |
|---|
| Število ogledov: | 1589 |
|---|
| Število prenosov: | 130 |
|---|
| Metapodatki: |    |
|---|
| Področja: | FNM
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
