Št. zadetkov: 32
Izvirni znanstveni članek
Oznake:
povezana dominacijska igra;zahtevnost;PSPACE-polno;connected domination game;complexity;PSPACE-complete;
Povezana dominacijska igra je različica dominacijske igre, v kateri morajo igrana vozlišča vedno tvoriti povezan podgraf. V članku dokažemo, da je preverjanje, ali je igralno povezano dominantno število omejeno z danim celim številom, log-polno v razredu PSPACE, ne glede na to, kateri igralec naredi ...
Leto:
2025
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Diplomsko delo
Oznake:
matematika;filtri;ultrafiltri;Banachova limita;limita ultrafiltra;izrek Tihonova;Stone-Čechova kompaktifikacija;
Ultrafiltri
Leto:
2015
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Magistrsko delo
Oznake:
teorija grafov;najkrajše poti;izometrična pot;geodetsko število;število izometričnih poti;
Pokrivanja vozlišč grafov z najkrajšimi potmi
Leto:
2017
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Diplomsko delo
Oznake:
igra policaja in roparja;poteza;premik;zmagovalna strategija;policijski graf;roparski graf;retrakt;senčna strategija;past;razgradljiv graf;policijska urejenost;čas lovljenja;2-razgradljiv graf;
Obravnavamo igro med dvema igralcema na povezanem grafu. Prvi igralec je policaj in poskuša ujeti drugega igralca, ki predstavlja roparja. Med vsako potezo se igralca lahko premakneta v sosednje vozlišče. Če sta v neki potezi igralca v istem vozlišču, je policaj roparja ujel in zmagal, če pa roparja ...
Leto:
2024
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Diplomsko delo
Oznake:
problem leva in moža;pot pregona;pravilo polmera;Besicovitcheva strategija;
Problem moža in leva je klasični problem pregona in izmikanja, ki ga je leta 1930 predstavil nemško-britanski matematik Richard Rado. Postavlja vprašanje, ali lahko lev ujame moža v krožni areni, če se oba premikata z enako največjo hitrostjo. Kljub navidezni enostavnosti se je izkazalo, da je probl ...
Leto:
2024
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Diplomsko delo
Oznake:
teorija grafov;grafi;drevesa;drevesna širina;drevesna dekompozicija;robidnica;robidno število;problem maksimalne neodvisne utežene množice;
Diplomsko delo obravnava drevesno širino, to je lastnost grafa, ki meri njegovo podobnost drevesu in je zelo uporabna z algoritmičnega vidika. Kanonična definicija drevesne širine sloni na konceptu drevesne dekompozicije grafa, to je način razdelitve grafa v podmnožice vozlišč, ki so strukturirane v ...
Leto:
2024
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Magistrsko delo
Oznake:
Fibonaccijeve kocke;k-Fibonaccijeve kocke;Fibonaccijevi bločni grafi;
Delo predstavi grafe Fibonaccijevih kock, $k$-Fibonaccijevih kock in Fibonaccijevih-bločnih grafov. Analizirana je struktura teh grafov, pri čemer so prešteta vozlišča in povezave, izračunane so stopnje vozlišč, polmer in premer. Opisane so tudi lastnosti, kot so hamiltonskost, dominacija, število i ...
Leto:
2024
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Diplomsko delo
Oznake:
gasilec;rešitveno število;stopnja preživetja;
Delo diplomskega seminarja obravnava igro Gasilec na grafih, kjer gasilec v vsakem koraku zaščiti eno vozlišče, medtem ko se ogenj širi po nezaščitenih vozliščih. Analiziramo dve strategiji, optimalno in požrešno, ter njuno učinkovitost na različnih družinah grafov. Vpeljemo rešitveno število in sto ...
Leto:
2025
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Diplomsko delo
Oznake:
gorenje grafa;število gorenja;zaporedje gorenja;izrek o redukciji na drevesa;dobro gorljivi grafi;domneva o številu gorenja;drevesa;
Preučujemo proces gorenja na povezanih neusmerjenih grafih. V procesu zagorijo viri gorenja in sosednja vozlišča že zgorelih vozlišč. Zanima nas, v koliko korakih bo zagorel cel graf in to količino definiramo kot število gorenja. Izbrani viri v procesu gorenja tvorijo zaporedje gorenja. Število gore ...
Leto:
2025
Vir:
Fakulteta za matematiko in fiziko (UL FMF)
Diplomsko delo
Oznake:
teorija grafov;igra policajev in roparja;ničelna vidljivost;policijsko število z ničelno vidljivostjo;policajeva zmagovalna strategija;potna širina;potna dekompozicija;monotona strategija;
Igra policajev in roparja z ničelno vidljivostjo je igra dveh igralcev na povezanem grafu, v kateri policaji nimajo popolnih informacij, ropar pa je vseveden in pozna nasprotnikov položaj in strategijo. V diplomskem delu obravnavamo optimizacijski problem določanja policijskega števila z ničelno vid ...
Leto:
2026
Vir:
Fakulteta za matematiko in fiziko (UL FMF)