Discrete Dynamical Systems On Graphs And Digraphs In Computer Simulations

A discrete dynamical system is a system in which the evolution of the variables is measured in discrete time steps. The behavior of the system is governed by a difference equation, or a return map, that gives the (n + 1)th value of variables as a function of the preceding nth value of the variables. That is to say, the dynamical system can be characterized as an iterated function.We study a class of discrete dynamical systems, whose initial form consists of the following data: (1) a finite labelled graph G with vertex set {1,2, ··· , n}, where each vertex has a state in some domain ED, (2)a vertex labelled multi-set of functions (F_i,G : Dⁿ → Dⁿ)_i, and (3) a permutation Ï€ ∈ S_n. The function F_i,G updates the state of vertex i as a function of the states of vertex i and its G-neighbors and leaves the states of all other vertices fixed. The permutation Ï€ represents a G-vertex order according to which the functions F_i,G are applied. By composing the functions F_i,G in the order given by Ï€ we obtain the sequential dynamical system (SDS):[F,G,Ï€]=F_Ï€1,GF_Ï€2,G···F_Ï€n,G:Dⁿ→Dⁿ.Here we always assume that the function F_Ï€1,G is applied first, F_Ï€2,G is applied next, and so on.There are altogether five chapters in the thesis. The first one is the introduction part, in which the background and some definitions are introduced. Moreover, some known important results and our main content in the thesis are listed. Chapter 2 to Chapter 5 are the main body part of the thesis, in which we illustrate our results in details. In Chapter 2, the properties of some special classes of discrete dynamical systems on graphs are specially studied. Chapter 3 contributes to the linear discrete dynamical systems on digraphs, which is a generalization of Chapter 2. Random parallel dynamical system are freshly introduced in Chapter 4 and the Markov property of the states sequence induced by it is discovered and studied. In the end of the thesis, we discuss another generalization of SDS. That is, we replace the permutation Ï€ by a word ξ on...