Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Chip Firing Games on (directed) graph are widely used in theoretical computer science and many other sciences. In this model, chips are fired from one vertex to all of its neighbors at the same time. The purpose of our paper is to study an extended version of this model, the Conflicting Chip Firing Game, by considering that chips can be fired from one vertex to one of its neighbors at each time. Our main results are obtained when the support graph of this game is a rooted tree. we show | VNU Journal of Science Natural Sciences and Technology 24 2008 103-109 Conflicting chip firing games on graphs and on trees Tra An Pham1 Thi Ha Duong Phan1 2 Thi Thu Huong Tran1 institute of Mathematics 18 Hoang Quoc Viet Cau Giay Hanoi Vietnam 2LIAFA Université Denis Diderot Paris 7-Case 7014-2 Place Jussieu-75256 Paris Cedex 05-France Received 31 October 2007 Abstract. Chip Firing Games on directed graph are widely used in theoretical computer science and many other sciences. In this model chips are fired from one vertex to all of its neighbors at the same time. The purpose of our paper is to study an extended version of this model the Conflicting Chip Firing Game by considering that chips can be fired from one vertex to one of its neighbors at each time. Our main results are obtained when the support graph of this game is a rooted tree. In this case we give the characterization of its reachable configurations and of its fixed points. Moreover we show the local lattice structure of its configuration space. Keywords Chip Firing Game conflicting game convergence discrete dynamical system evolution rule fixed point tree. 1. Introduction A Chip Firing Game CFG 1 2 is defined on a directed multi graph as follows. A configuration of the game is a distribution of chips on the vertices of the graph and the evolution rule firing a vertex is defined by a configuration can be transformed into another one by transferringa chipfrom one vertex along each of its outgoing edges if it contains at least as many chips as its outgoing degree. The set of all configurations reachable from the initial one is called configuration space and a fixed point is a configuration from which the evolution rule can not be applied. Convergence conditions involving the number of chips or the structure of the graph are given in 1-3 as well as different proofs of the fact that the configuration space of any convergent CFG is a lattice. See Figure 1 for an example. CFGs are widely used in theoretical
