Cycle bases of reduced powers of graphs

angleški

2017

letnik 12, številka 1

grafi   markovske verige   produkti grafov   prostori ciklov

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Definiramo konstrukcijo, za katero menimo, da je nova. Če je dan graf ?$G$? in pozitivno celo število ?$k$?, potem je reducirana ?$k$?-ta potenca grafa ?$G$?, ki jo označimo ?$G^{(k)}$?, konfiguracijski prostor, v katerem postavimo ?$k$? enakih žetonov na vozlišča grafa ?$G$?, tako da je na vsakem vozlišču največ ?$k$? žetonov. Dve konfiguraciji sta sosedni, če lahko eno transformiramo v drugo tako, da premaknemo en žeton vzdolž povezave v neko sosedno vozlišče. Predstavimo trditve, ki se nanašajo na strukturne lastnosti reduciranih potenc grafa in, kar je najbolj pomembno, zagotavljajo konstrukcijo minimalne baze ciklov potenc ?$G^{(k)}$?. Konstruiranje minimalne baze ciklov je zanimiv kombinatoričen problem, ki je koristen tudi v uporabah, ki vključujejo konfiguracijske prostore. Na primer, če je ?$G$? graf prehodnih stanj modela markovskih verig stohastičnega avtomata, potem je reducirana potenca ?$G^{(k)}$? graf prehodnih stanj za ?$k$? identičnih (a ne nujno neodvisnih) avtomatov. Pokažemo, kako se da konstrukcijo minimalne baze ciklov grafa of ?$G^{(k)}$? uporabiti za dokaz, da od stanj odvisno parjenje avtomatov ne krši načela mikroskopske reverzibilnosti, kot se zahteva pri fizikalnih in kemičnih aplikacijah.

29.05.2020