VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Domination games played on graphs
    Brešar, Boštjan ...
    Ta jedrnata monografija podaja popolno zgodovino dominacijske igre in njenih različic vse do najnovejših rezultatov in bo pospešila raziskave na z njo tesno povezanih področjih ter s tem ... predstavljala ključno referenco za nadaljnji razvoj. Ključni del monografije so nove metode in ideje, ki so bile vpeljane in razvite v okviru te teorije, na čelu s strategijo namišljene igre, nadaljevalnim principom in metodo praznjenja Bujtáseve. Bralcu so tako predstavljena glavna orodja in tehnike dokazovanja, s pomočjo katerih so dobljeni številni rezultati o invariantah dominacijskih iger. Strategija namišljene igre se izkaže kot močno in pogosto uporabljeno orodje, medtem ko nadaljevalni princip predstavlja pomembno lastnost monotonosti igralnega dominantnega števila. Moč metode praznjenja Bujtáseve se kaže v izboljšavi do tedaj najboljših zgornjih mej za (običajno) dominantno število grafa, izraženih z redom grafa, in sicer za grafe z najmanjšo stopnjo od 5 do 50. Knjiga je namenjena predvsem študentom teorije grafov kot tudi uveljavljenim grafovskim teoretikom, dosegljiva pa je vsakemu bralcu z nekaj matematične zrelosti. Avtorji predstavijo točne rezultate za igralna dominantna števila nekaterih družin grafov, vključeni so glavni rezultati o obnašanju igre na podgrafih in na drevesih, podani pa so tudi rezultati o računskih zahtevnosti dominacijskih iger. Različice iger, v katerih igra le "počasni" igralec, porodijo tako imenovana Grundyjeva dominantna števila, ki povežejo tematiko knjige z nekaterimi koncepti iz linearne algebre, kot na primer množico ničelne prisile in najmanjšim rangom. V knjigi je predstavljenih več kot ducat drugih sorodnih iger na grafih in hipergrafih. V vseh teh igrah ostajajo odprti problemi, ki čakajo na rešitve, tako da to področje ponuja veliko možnosti za nadaljnje raziskave. Dominacijska igra pripada družini tekmovalnih optimizacijskih iger na grafih, ki je v porastu. Igrata jo dva igralca, ki se izmenjujeta v potezah, kjer na vsakem koraku izbereta neko novo vozlišče in ga dodata v množico izbranih vozlišč. Skupaj tako gradita posebno strukturo v danem grafu, ki ji rečemo dominantna množica. Igralca imata nasprotna cilja: eden želi minimizirati velikost izbrane množice, nasprotnica pa želi doseči, da bo ta množica kar se da velika. V igri tako ni zmagovalca in poraženca. A če oba igralca uporabita optimalni strategiji glede na svoja cilja, je kardinalnost množice izbranih vozlišč grafovska invarianta, ki ji pravimo igralno dominantno število grafa. V tej knjigi je, prvič odkar je bila igra vpeljana, predstavljeno drevo dominacijske igre, ki nazorno demonstrira korektnost definicije igralnega dominantnega števila.
    Vrsta gradiva - znanstvena monografija ; neleposlovje za odrasle
    Založništvo in izdelava - Cham : Springer Nature, cop. 2021
    Jezik - angleški
    ISBN - 978-3-030-69086-1; 978-3-030-69087-8
    COBISS.SI-ID - 60317443

    Povezava(-e):

    https://doi.org/10.1007/978-3-030-69087-8

    dostop s plačilom


    DOI

Knjižnica/institucija Kraj Akronim Za izposojo Druga zaloga
Narodna in univerzitetna knjižnica, Ljubljana Ljubljana NUK na dom 4 izv.
v čitalnico 1 izv.
ni za izposojo 1 izv.
FMF in IMFM, Matematična knjižnica, Ljubljana Ljubljana MAKLJ na dom 2 izv.
loading ...
loading ...
loading ...

Vnos na polico