Kamenčkanje na grafu () je , ki se igra na grafu z nič ali več kamenčki na vsaki od njegovih točk. 'Igranje' je sestavljeno iz niza potez s kamenčki. Poteza s kamenčki na grafu je sestavljena iz izbire točke z vsaj dvema kamenčkoma, odstranitve dveh kamenčkov z nje in dodajanja enega sosednji točki (drugi odstranjeni kamenček se zavrže iz igre). , število kamenčkov grafa , je najmanjše naravno število , ki izpolnjuje naslednji pogoj:
Na primer, na grafu z dvema točkama in 1 robom, ki ju povezuje, je število kamenčkov 2. Ne glede na to, kako sta dva kamenčka postavljena v točke grafa, je vedno mogoče priti do želenega rezultata, da ima izbrana točka kamenček če je začetna konfiguracija konfiguracija z enim kamenčkom na točko, potem je cilj trivialno dosežen z ničelnimi potezami kamenčkov. Eno osrednjih vprašanj kamenčkov grafov je vrednost za dani graf .
thumb|right|350px|Dva grafa s ciljnima točkama prikazanima z rdečo barvo.
Levo: Igra s 3 kamenčki, ki jo je mogoče dobiti v 2 potezah.
Desno: Igra, ki je ni mogoče dobiti, kljub temu da ima več kamenčkov kot leva, ker s točkami z enim kamenčkom ni mogoče narediti nobenih potez. To pomeni, da mora biti , število kamenčkov tega grafa, vsaj 6.
Druge teme v kamenčkanju vključujejo pokrivno kamenčkanje, optimalno kamenčkanje, dominantno pokrivno kamenčanje, meje in pragove za kamenčkanje števila, pa tudi globoke grafe.
Ena od uporab iger kamenčkanja v varnostni analizi pomnilniško zahtevnih funkcij () v kriptografiji.
Glej tudi
Opombe
Sklici
Viri
Kategorija:Invariante grafov Kategorija:Matematične igre