Št. zadetkov: 21
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:
Repozitorij Univerze v Ljubljani (RUL)
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)
Doktorska disertacija
Oznake:
mathematics;graph theory;domination in graphs;domination game;total domination game;Z-domination game;connected domination game;
V zadnjem desetletju so dominacijske igre deležne vedno večje pozornosti. V osnovni različici igre dva igralca, Dominator in Zavlačevalka, izmenično dominirata vozlišča grafa. Dominatorjev cilj je doseči čim manjše skupno število potez, Zavlačevalka pa se trudi igro podaljšati. Če oba igralca igrata ...
Leto:
2021
Vir:
Fakulteta za matematiko in fiziko (UL FMF)