TAILIEUCHUNG - Báo cáo " Conflicting chip firing games on graphs and on trees "

Chip Firing Games on (directed) graph are widely used in theoretical computer science and many other sciences. In this model, chips are ﬁred 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 Conﬂicting Chip Firing Game, by considering that chips can be ﬁred 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

TÀI LIỆU LIÊN QUAN
43    17    1
7    28    0
TÀI LIỆU XEM NHIỀU
8    459380    18
3    7525    96
14    7061    329
8    6279    1896
13    4873    260
7    4362    1
2    3760    44
3    3580    50
9    3416    9
21    3363    224
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
16    46    0    29-11-2021
93    47    0    29-11-2021
26    11    1    29-11-2021
21    38    0    29-11-2021
2    145    9    29-11-2021
6    12    2    29-11-2021
12    71    0    29-11-2021
8    45    0    29-11-2021
4    88    1    29-11-2021
111    4    1    29-11-2021
TÀI LIỆU HOT
8    6279    1896
112    2264    977
122    2294    440
561    1176    407
14    7061    329
35    2103    311
20    2670    301
131    1534    273
13    4873    260
292    1684    253
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.