Luận án Tiến sĩ Toán học: Đặc trưng không gian trạng thái và tính ổn định của một số hệ Sandpile Model mở rộng

Chia sẻ: Quỳnh Quỳnh | Ngày: | Loại File: PDF | Số trang:122

Thêm vào BST

Báo xấu

121
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án Tiến sĩ Toán học: Đặc trưng không gian trạng thái và tính ổn định của một số hệ Sandpile Model mở rộng nhằm đề xuất các hệ mở rộng trên các hệ SPM và CFG để mô tả tốt hơn hoặc cho phù hợp với các mục đích khác nhau của các hệ trong thực tế. Mời bạn đọc cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: Đặc trưng không gian trạng thái và tính ổn định của một số hệ Sandpile Model mở rộng

VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC ---------- Trần Thị Thu Hương ĐẶC TRƯNG KHÔNG GIAN TRẠNG THÁI VÀ TÍNH ỔN ĐỊNH CỦA MỘT SỐ HỆ SANDPILE MODEL MỞ RỘNG Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 62 46 01 10 Cán bộ hướng dẫn: PGS.TS. Phan Thị Hà Dương, Viện Toán học LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội, 2014
Đ c trưng không gian tr ng thái và tính n đ nh c a m t s h Sandpile Model m r ng Tr n Th Thu Hương Chuyên ngành: Cơ s Toán h c c a Tin h c Mã s : 62 46 01 10 Cán b hư ng d n: PGS.TS. Phan Th Hà Dương, Vi n Toán h c Ngày 27 tháng 3 năm 2014
L i cam đoan Tôi xin cam đoan đây là công trình nghiên c u c a tôi dư i s hư ng d n c a PGS. TS. Phan Th Hà Dương. Các k t qu vi t chung v i các tác gi khác đã đư c s nh t trí c a đ ng tác gi khi đưa vào lu n án. Các k t qu nghiên c u trong lu n án là m i và chưa t ng đư c ai công b trong b t kì công trình nào khác. Tác gi Tr n Th Thu Hương 1
L i c m ơn Tôi xin g i l i c m ơn chân thành và sâu s c nh t t i cô giáo tôi, PGS. TS. Phan Th Hà Dương - ngư i th y, ngư i đ ng nghi p mà tôi r t m c kính tr ng, yêu quý và đ y lòng bi t ơn. Chính s say mê, ni m nhi t huy t trong công tác nghiên c u Toán c a cô đã truy n c m h ng cho tôi ngay t khi m i bư c chân vào Vi n Toán. Dư i s hư ng d n c a cô, theo th i gian, tôi đã trư ng thành và v ng tin hơn r t nhi u trên con đư ng nghiên c u c a mình. V i tôi, cô còn là ngư i b n l n có th chia s nh ng khó khăn không nh ng trong công vi c mà trong c cu c s ng. Tôi xin g i l i c m ơn t i các th y, các đ ng nghi p, nh ng ngư i đã giúp tôi trong trao đ i khoa h c, th o lu n, đóng góp ý ki n, đ ng viên tinh th n,...: GS. Lê Tu n Hoa, GS. Ngô Vi t Trung, GS. Nguy n Vi t Dũng, Ths. Ph m Văn Trung, GS. Robert Cori, PGS. Ph m Trà Ân, GS. Ngô Đ c Tân, TS. Lê Công Thành, TS. Lê M nh Hà, TS. Đ Phan Thu n, GS. Dominique Rossin, PGS. Trương Xuân Đ c Hà, ThS. Hoàng Phi Dũng, CN. Phùng Văn Doanh. Tôi xin c m ơn b n tôi, TS. Ph m Th Anh Lê, ngư i đã đ c k b n th o và s a r t nhi u l i di n đ t, chính t và đánh máy. Tôi xin g i l i c m ơn t i các cơ quan, t ch c: Trung tâm đào t o sau đ i h c, Vi n Toán h c, Vi n Khoa h c và công ngh Vi t Nam, Qu Nafosted, VIASM (Vi n nghiên c u cao c p v Toán), LIA Formath Vietnam, đã tài tr và t o đi u ki n thu n l i cho công tác nghiên c u, trao đ i khoa h c c a tôi trong th i gian làm lu n án. Đ c bi t, tôi xin c m ơn Vi n Toán h c đã cho tôi làm vi c trong m t môi trư ng bình đ ng, thân thi n, hòa nhã, vui v và lành m nh. Lu n án dành t ng ba m tôi và hai cháu (Bin và T c): nh ng ngư i có th không hi u n i dung lu n án nhưng ch c n nhìn th y h , tôi đã th y c b u tr i và 2
là ngu n đ ng viên l n nh t giúp tôi hoàn thành lu n án đúng kỳ h n. Lu n án còn t ng cho nh ng ai yêu Toán. 3
M cl c M cl c 1 Danh m c hình v 3 Danh m c ký hi u 6 Tóm t t 7 Abstract 8 M đ u 9 1 H đ ng l c r i r c 13 1.1 Các ki n th c chu n b . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.1 Đ th . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.2 Phân ho ch c a s t nhiên, t p th t b ph n và dàn . . . 18 1.1.3 Ngôn ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2 M t s h đ ng l c r i r c . . . . . . . . . . . . . . . . . . . . . . . . 25 1.2.1 Các ki n th c chung v h đ ng l c r i r c . . . . . . . . . . . 25 1.2.2 H CFG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.2.3 H SPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2 H SPM: Tính n đ nh 40 2.1 H E-SPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2 C u trúc không gian tr ng thái c a các phân ho ch trơn . . . . . . . 43 2.3 Đ dài đư ng đi gi a hai phân ho ch trơn trong h E-SPM . . . . . . 46 1
2.4 K t lu n chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3 H SPM đ i x ng song song 58 3.1 M t s m r ng c a h SPM . . . . . . . . . . . . . . . . . . . . . . . 59 3.1.1 H SPM song song (P-SPM) . . . . . . . . . . . . . . . . . . . 59 3.1.2 H SPM đ i x ng (S-SPM) . . . . . . . . . . . . . . . . . . . 60 3.2 H SPM đ i x ng song song (PS-SPM): Tr ng thái n đ nh . . . . . . 64 3.3 K t lu n chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4 Các h m r ng CFG có d u và SPM đ i x ng 82 4.1 H m r ng CFG có d u (S-CFG) . . . . . . . . . . . . . . . . . . . . 83 4.2 Các m r ng S-SPM và S-CFG trên đư ng th ng . . . . . . . . . . . 84 4.2.1 S đ ng c u . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.2.2 Tr ng thái n đ nh . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3 Các m r ng trên đ th vòng: SPM(Cn ), CFG(Cn ), S-SPM(Cn ) và S-CFG(Cn ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.3.1 Các h SPM(Cn ) và CFG(Cn ); S-SPM(Cn ) và S-CFG(Cn ): S đ ng c u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.3.2 C u trúc không gian và đ c trưng tr ng thái . . . . . . . . . . 98 4.3.3 Tr ng thái n đ nh c a h S-CFG(Cn ) . . . . . . . . . . . . . 103 4.4 K t lu n chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 K t lu n 110 Danh m c các công trình 113 Tài li u tham kh o 113 2
Danh sách hình v 1.1 Đ th đ y đ K4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.2 Bi u đ Ferrer c a phân ho ch (4, 3, 2, 2, 2, 1) . . . . . . . . . . . . . 18 1.3 Bi u đ Hasse c a m t s t p th t . . . . . . . . . . . . . . . . . . 21 1.4 Dàn và không ph i dàn . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.5 Dàn phân ph i đ a phương trên nhưng không phân ph i đ a phương dư i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.6 Đ th qu đ o c a CFG . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.7 Lu t rơi ph i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.8 Không gian tr ng thái c a SPM(6) và SPM(30) . . . . . . . . . . . . 36 2.1 Không gian tr ng thái c a h E-SPM . . . . . . . . . . . . . . . . . . 43 2.2 Không gian tr ng thái c a h E-SPM . . . . . . . . . . . . . . . . . . 45 2.3 Bi u đ Ferrer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.4 C t trơn và đư ng chéo . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.5 Bi u đ năng lư ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.6 Đư ng đi dài nh t . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.7 Đư ng đi dài nh t gi a hai phân ho ch trơn . . . . . . . . . . . . . . 55 2.8 Ph n ví d cho ea (i, j) = eb (i, j) . . . . . . . . . . . . . . . . . . . . . 56 3.1 Không gian tr ng thái c a: (a): SPM(6); (b): PS-SPM(6) . . . . . . . 60 3.2 Dãy đơn đ nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.3 Không gian tr ng thái c a h S-SPM(5) . . . . . . . . . . . . . . . . 63 3.4 Khai tri n SPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.5 Không gian tr ng thái c a h PS-SPM(5) . . . . . . . . . . . . . . . . 65 3
3.6 Th t c Atom trên (4, 3, 2, 1) . . . . . . . . . . . . . . . . . . . . . . 68 3.7 Th t c đan xen trên (9) . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.8 Th t c gi đan xen trên (13) . . . . . . . . . . . . . . . . . . . . . . 74 3.9 C t đ i x ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.10 Đư ng đi t (20) t i tr ng thái n đ nh (1123(4)3321) . . . . . . . . . 80 4.1 CFG có d u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.2 Tr ng s c a các ký t 0 c a m t t trong LS . . . . . . . . . . . . . 91 4.3 Không gian tr ng thái c a S-SPM(C4 , 4) . . . . . . . . . . . . . . . . 96 4.4 Dàn con SPM(C3 , 10) c a dàn SPM(10) . . . . . . . . . . . . . . . . 101 4
Danh m c ký hi u Altt (a) Áp d ng th t c đan xen t bư c trên a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Atomt (a) Áp d ng th t c Atom t bư c trên a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 CFG Chip Firing Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 CFG(G) H CFG trên đ th G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 CFG(G, O) H CFG trên G xu t phát t tr ng thái O . . . . . . . . . . . . . . . . . . . . . . . . 29 CFG(G, k) H CFG trên G xu t phát t các tr ng thái có tr ng s k . . . . . . . . . . 29 δ Ánh x l y hi u đ ng c u gi a h SPM và CFG . . . . . . . . . . . . . . . . . . . . . . . . . 38 E-SPM H SPM m r ng v i lu t thêm h t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 LS Ngôn ng n đ nh trên {1,0,} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 PAltt (a) Áp d ng th t c gi đan xen t bư c trên a . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 P-SPM(N ) H SPM song song xu t phát t (N ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 PS-SPM(N ) H SPM đ i x ng song song xu t phát t (N ) . . . . . . . . . . . . . . . . . . . 65 SE-SPM T p các phân ho ch trơn c m sinh t h E-SPM. . . . . . . . . . . . . . . . . . . . .44 SPM Sandpile Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34 SPM(N ) H SPM xu t phát t (N ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 S-SPM(N ) H SPM đ i x ng xu t phát t (N ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5
a↓i Dãy thu đư c t a b ng thêm m t h t vào c t i . . . . . . . . . . . . . . . . . . . . . . . . . 42 ai ) Dãy bên trái (ph i) th c s c a a t i i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 d Ánh x l y hi u đ ng c u gi a h S-SPM và S-CFG trên đư ng th ng . . . 85 dn Ánh x l y hi u trên đ th vòng Cn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 E(a) Năng lư ng c a a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 ea (i, j) Năng lư ng c a h t (i, j) trong a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 F P (S-CFG(Cn , k) T p tr ng thái n đ nh c a S-CFG(Cn , k) . . . . . . . . . . . . . . . . . 105 6
Tóm t t Lu n án trình bày m t s m r ng c a hai h đ ng l c r i r c Sandpile model (SPM) và Chip firing game (CFG). Hai h này đã đư c nghiên c u r t nhi u trong nh ng năm g n đây b ng nhi u cách ti p c n khác nhau. Chúng tôi nghiên c u bài toán đ t đư c, c u trúc không gian và th i gian đ t đư c trên các h m r ng này. M r ng thêm h t trên h SPM: Nghiên c u s n đ nh c a h dư i tác đ ng t bên ngoài b ng vi c b sung lu t thêm h t vào các c t h p lý m i khi h đ t t i tr ng thái n đ nh duy nh t. Chúng tôi ch ra r ng có th thu đư c t t c các phân ho ch trơn b ng cách này. T đó ch ng minh c u trúc dàn c a các phân ho ch trơn trong m i liên quan v i dàn Young. Hơn n a, nh gi i thi u khái ni m năng lư ng chúng tôi mô t đư c s bi n thiên c a h thông qua các đ i lư ng đư c tính toán tư ng minh là đư ng đi ng n nh t và dài nh t. M r ng h SPM thành h đ i x ng song song (PS-SPM): Các c t có th rơi sang c hai phía (tính đ i x ng) và các c t có th rơi thì rơi đ ng th i (tính song song), chúng tôi đã ch ra h SPM đ i x ng song song và h SPM đ i x ng có t p tr ng thái n đ nh có cùng hình d ng. Ch ng minh này mang tính xây d ng nh ch ra tư ng minh con đư ng áp d ng lu t PS-SPM k t h p gi a các th t c đan xen, gi đan xen và t t đ nh m t cách h p lý. M r ng h CFG thành h CFG có d u: Các đ nh trong h CFG có th ch a m t s âm các chip và các đ nh ch a chip đ âm cũng có th b n. Chúng tôi ch ra các đ ng c u gi a h SPM đ i x ng và h CFG có d u trong hai trư ng h p khi đ th n n là đư ng th ng vô h n và đ th vòng. Nh vi c k t h p nghiên c u gi a hai h này, chúng tôi đ c trưng cho các tr ng thái c a các h và đưa ra m t s tính toán t h p liên quan đ n s tr ng thái n đ nh c a chúng. 7
Abstract The manuscript presents some generalizations of two discrete dynamical systems: Sandpile model (SPM) and Chip firing game (CFG), which have recently received great attentions in mathematics, physics and theoretical computer science. We focus on the reachabilities, the time to reach stable configurations and the configuration spaces on these systems. We study the stability of the SPM where grains can be added from outside on random columns. We prove that the infinite set of all stable configurations have a lattice structure which is a sublattice of Young lattice. Moreover, by using the con- cept of "energy" for each stable configuration, we give the formulae for the smallest and the greatest time to reach stable configurations. We investigate a generalization of the SPM, called the parallel symmetric sand- pile model, where columns can fall on either the left or the right (symmetric model) and at each step, all fallable columns will fall (parallel model). We prove that al- though the parallel model produces really less number of fixed points than that by the sequential model, the forms of fixed points of the two models coincide. Moreover, our proof is a constructive one which gives a nearly shortest way to reach a given fixed point form. We present an extension of the CFG, called signed chip firing game, by allowing a negative number of chips at some vertices and negative vertices can fire. We show the isomorphism between symmetric sandpile model and signed chip firing game when the supported graph is either cycles or the infinite graph. Therefore, we give a characterization of reachable configurations and of fixed points of each model. At the end, we give explicit formulae for the number of their fixed points. 8
M đ u Lý thuy t h đ ng l c đã đư c nghiên c u nhi u trong các lĩnh v c khác nhau như Toán h c, V t lý, Sinh h c, Hóa h c. H đ ng l c là m t quá trình ti n hóa theo th i gian và đư c mô t b ng các tr ng thái và các lu t v n đ ng. M t h đ ng l c là r i r c n u th i gian là trong Z. Trên h đ ng l c r i r c ngư i ta quan tâm đ n m t s v n đ sau: s h i t c a h , c u trúc (th t , dàn, nhóm) c a không gian các tr ng thái c a h , tính đ t đư c c a h (khi nào m t tr ng thái đ t đư c t m t tr ng thái khác b ng cách áp d ng m t s l n lu t v n đ ng), s n đ nh c a h dư i các tác đ ng, ... Trong lu n án này, chúng tôi nghiên c u các v n đ trên cho m t s m r ng c a hai h đ ng l c CFG (Chip firing game) và h SPM (Sandpile model). H CFG đư c gi i thi u b i Bak, Tang và Wiesenfield khi nghiên c u các h đ t bi n có t ch c trong t nhiên vào năm 1987 [3]. Năm 1991, Bjorner, Lovász và Shor [7] đã mô hình hóa h b ng Toán h c và s d ng lý thuy t ngôn ng đ nghiên c u s h i t c a h . Theo đó, h CFG đư c đ nh nghĩa trên m t đa đ th có hư ng G = (V, E), đư c g i là đ th n n. M i tr ng thái c a h là m t s phân b chip trên V . Lu t v n đ ng là lu t b n: m t đ nh có th b n n u ch a s chip ít nh t b ng s b c đi ra c a nó, và khi b n nó s cho t t c các đ nh d c theo các c nh đi ra này m t chip. Năm 1997, Biggs nghiên c u s h i t c a h CFG dư i tên g i khác là "dollar game" và đã ch ra các đi u ki n h i t c a h ph thu c vào t ng s chip c a tr ng thái ban đ u [5]. Ti p theo, Phan và các đ ng nghi p nghiên c u c u trúc không gian các tr ng thái c a h CFG trên đ th n n không có thành ph n đóng không t m thư ng. Các tác gi ch ng minh h có c u trúc dàn phân ph i đ a phương dư i [27, 32]. Sau đó, Dhar et. al. [17] và Cori và Rossin [11] nghiên c u c u 9
trúc nhóm trên m t l p các tr ng thái n đ nh đ c bi t (đư c g i là các tr ng thái đ t bi n) c a h CFG trên đ th vô hư ng có đ nh chìm, và th c hi n nhi u tính toán t h p liên quan đ n lý thuy t đ th như s cây bao trùm, ma tr n Laplace. Đi u này cũng đư c nghiên c u sâu hơn và m r ng cho đ th có hư ng nh s d ng các công c c a đ i s [28]. Hơn n a, g n đây h CFG còn đư c s d ng như là m t công c trong nghiên c u m t s v n đ v đ i s liên quan đ n các đ nh lý Riemann-Roch, đa th c Tutte, gi thuy t v h-vector c a Stanley [4, 36, 38]. H SPM và m t s h khác liên quan đã đư c gi i thi u và nghiên c u trong các lĩnh v c khác nhau: trong b i c nh v dàn các phân ho ch c a các s t nhiên b i Brylawsky [8]; t góc nhìn c a V t lý đ nghiên c u hi n tư ng t đ t bi n có t ch c (SOC) b i Bak, Tang và Wiesenfeld [3]; t cách ti p c n c a T h p b i Anderson et. al., Spencer, Goles và Kiwi [1, 23, 43]. H SPM là h đ ng l c r i r c, trong đó m i tr ng thái (thư ng đư c g i là các c t cát) là m t dãy gi m d n. Lu t v n đ ng là lu t rơi, t c là khi m t c t cát có đ cao l n hơn c t bên ph i c a nó ít nh t là 2 đơn v (thư ng đư c g i là h t) thì nó s cho hàng xóm đó m t h t. Năm 1993, Goles và Kiwi đã ch ng minh r ng h SPM có th đư c mã hóa như m t h CFG trên đ th n n là n a đư ng th ng vô h n. Nh v y, h SPM k th a m t s tính ch t t ng quát c a h CFG như s h i t , c u trúc dàn. Ngoài ra, do là m t CFG trên đ th đ c bi t nên nó cũng có m t s tính ch t đ c trưng như các tr ng thái đ t đư c t m t c t duy nh t đ u đư c đ c t và do v y tr ng thái n đ nh duy nh t cũng đư c xác đ nh tư ng minh. Hơn n a, chúng ta cũng có th tính đư c th i gian đ h h i t đ n tr ng thái n đ nh duy nh t [23, 26, 27, 31]. Bên c nh đó, h SPM và m t s bi n th c a nó còn đư c s d ng đ tính toán ho c sinh t h p các l p con c a các phân ho ch như phân ho ch trơn, phân ho ch ch t và có th dùng đ ch ng minh m t s đ ng th c t h p [8, 33, 34, 35]. M c đích c a lu n án: 1. Nghiên c u quá trình t n đ nh c a h SPM dư i tác đ ng t bên ngoài. Nh c l i r ng các h trong t nhiên ngoài s v n đ ng n i t i bên trong còn b tác đ ng b i các y u t t bên ngoài. M i khi h n đ nh, m t tác đ ng nh t bên ngoài s phá v s n đ nh c a h và làm cho h ti p t c v n đ ng v i lu t n i t i. Đ đo s bi n thiên c a h dư i tác đ ng bên ngoài này, chúng tôi quan tâm t i s 10
chuy n đ i gi a các tr ng thái n đ nh và th i gian chuy n đ i gi a chúng. 2. Đ xu t các h m r ng trên các h SPM và CFG đ mô t t t hơn ho c cho phù h p v i các m c đích khác nhau c a các h trong th c t . V i các h m r ng này, chúng tôi quan tâm đ n đ c trưng các tr ng thái, tr ng thái n đ nh; c u trúc không gian; s h i t ; th i gian h i t và các tính toán t h p trên các tr ng thái c ah . V i m c tiêu này, lu n án trình bày b n chương chính. Trư c đó, m t s ki n th c chu n b và các k t qu đã đư c nghiên c u liên quan đ n lu n án trên hai h SPM và CFG đư c trình bày trong Chương 1. Chương 2: Nghiên c u tính n đ nh c a h SPM dư i tác đ ng t bên ngoài. Chúng tôi xét h SPM có b sung lu t thêm: m i khi h đ t đ n m t tr ng thái n đ nh duy nh t, thì m t h t s đư c thêm vào m t c t, và h l i ti p t c v n đ ng v i lu t rơi n i t i đ đ t đ n m t tr ng thái n đ nh khác, và ti p t c quá trình này. Chúng tôi quan tâm đ n t p t t c các tr ng thái n đ nh thu đư c b ng cách như v y. Các k t qu trong ph n này là: sinh ra t p t t c các phân ho ch trơn b ng h đ ng l c; ch ng minh r ng t p các phân ho ch trơn có c u trúc dàn và là dàn con c a dàn Young (dàn các phân ho ch v i quan h th t bao hàm). Thêm vào đó, b ng vi c đưa ra khái ni m "năng lư ng", chúng tôi cũng tính th i gian đ h đ t đ n m t tr ng thái n đ nh cho trư c. Trong h này vì th i gian c a m i con đư ng đ n m t tr ng thái n đ nh là khác nhau nên vi c đánh giá th i gian s thông qua th i gian ng n nh t và dài nh t. Đây cũng là cơ s đ kh o sát s bi n thiên c a h dư i tác đ ng t bên ngoài. Chương 3: Nghiên c u m t m r ng c a h SPM thành h SPM đ i x ng song song. Trong đó m t c t có th rơi sang bên ph i ho c bên trái n u hi u đ cao tương ng ít nh t là 2 (h m r ng SPM đ i x ng) và các c t có th rơi (trái ho c ph i) s rơi đ ng th i (h m r ng SPM song song). H SPM đ i x ng đư c nghiên c u b i Formenti et. al [22] và b i Phan [40]. Trong khi Formeti el. al xem xét hình d ng c a các tr ng thái mà không quan tâm t i v trí c a c t kh i đ u (t c là, các tr ng thái sai khác nhau m t phép t nh ti n trên đư ng th ng s đư c đ ng nh t v i nhau), Phan xét các tr ng thái c a nó cùng v i v trí c a c t kh i đ u. C hai đ u đưa ra đ c trưng cho các hình d ng c a các tr ng thái và tính toán t h p các 11
d ng n đ nh (hình d ng c a tr ng thái n đ nh) c a h . H SPM đ i x ng h i t t i nhi u tr ng thái n đ nh. Bên c nh đó, các nghiên c u v các h song song cũng r t đư c quan tâm, ví d h SPM song song đã đư c nghiên c u b i Durand-Lose [20]. Trong h này, tr ng thái n đ nh chính là tr ng thái n đ nh c a h SPM và th i gian đ h h i t đ n tr ng thái n đ nh đó là tuy n tính. Trong chương này, chúng tôi ch ng minh m c dù tr ng thái n đ nh c a h SPM đ i x ng song song là m t t p con c a t p tr ng thái n đ nh c a h SPM đ i x ng, nhưng d ng n đ nh c a chúng l i trùng nhau (Đ nh lý 3.2.1). Ch ng minh c a chúng tôi mang tính ki n thi t. Hơn n a, chúng tôi cũng đưa ra m t đánh giá g n chính xác cho th i gian ng n nh t đ h SPM đ i x ng song song h i t t i m t tr ng thái n đ nh. Chương 4: Nghiên c u m t m r ng c a h SPM và h CFG thành các h SPM đ i x ng và CFG có d u tương ng và m i liên h gi a chúng. M c 4.2 đưa ra các m r ng trên đư ng th ng và m c 4.3 là trên đ th vòng. Chúng tôi m r ng b ng cách thêm lu t cho các h như sau. V i h SPM, m t c t có th rơi sang bên ph i ho c bên trái nó n u hi u đ cao tương ng ít nh t là 2. V i h CFG, các đ nh có th ch a m t s âm các chip và các đ nh đ âm chip cũng có th b n như các đ nh đ dương chip. B ng cách m r ng như trên, vi c mô t các h trong th c t s t t hơn. Hơn n a, h CFG có d u có th đư c s d ng đ mã hóa h SPM đ i x ng. V i m i đ i tư ng nghiên c u khác nhau chúng tôi s ho c là làm trên h SPM r i chuy n các k t qu sang h CFG ho c ngư c l i. Ch ng h n, bài toán đ c trưng các tr ng thái s đư c th c hi n trên h SPM và bài toán tính toán t h p s các tr ng thái n đ nh s đư c th c hi n trên h CFG. Các k t qu đ t đư c khi đ th n n là đư ng th ng và đ th vòng là: mã hóa h SPM đ i x ng b i h CFG có d u; đ c trưng tr ng thái; đưa ra các tính toán t h p cho s tr ng thái đ nh theo đ dài và theo tr ng s . T đây chúng tôi cũng ch ra r ng m r ng h CFG theo cách này là m t m r ng t nhiên, và có th đư c áp d ng cho nh ng nghiên c u khác. 12
Chương 1 H đ ng l c r i r c Chương này nh c l i các ki n th c chu n b , m t s hư ng nghiên c u và các k t qu đã bi t v hai h đư c nghiên c u chính trong lu n án: H SPM (Sandpile model) và h CFG (Chip firing game). 1.1 Các ki n th c chu n b Lu n án t p trung nghiên c u hai h đ ng l c r i r c đư c quan tâm r t nhi u: h SPM (Sand pile model) và h CFG (Chip firing game). Hai h này đư c đ nh nghĩa trên m t đ th n n. Các k t qu trên hai h có liên quan nhi u đ n m t s tính toán t h p trên các phân ho ch c a s t nhiên, c u trúc th t , c u trúc dàn trên không gian các tr ng thái c a các h . B i v y, trong ph n này chúng tôi s trình bày các ki n th c cơ s v đ th , t p th t , dàn, ngôn ng ,... đư c tham kh o ch y u trong [2, 13, 18, 37, 44, 45]. 1.1.1 Đ th Trư c h t, chúng tôi trình bày các khái ni m cho đ th vô hư ng sau đó s đ c p tương t cho đ th có hư ng. Đ nh nghĩa 1.1.1 (Đa đ th vô hư ng). M t đa đ th vô hư ng là m t c p có th th G = (V, E), trong đó V là m t t p h p khác r ng, đư c g i là t p đ nh 13
c a G, và E là m t đa t p trong t p các c p không phân bi t th t {u, v}, v i u, v ∈ V , đư c g i là t p c nh c a G. Cho G là m t đa đ th vô hư ng. N u e = {u, v} ∈ E thì các đ nh u, v đư c g i là các đ u mút c a e và u liên thu c v i e, hơn n a, hai đ nh u, v đư c g i là li n k , hay hàng xóm c a nhau. N u e = {u, u} thì e đư c g i là m t khuyên. B c c a m t đ nh u ∈ V , ký hi u là deg(u), là s các c nh c a G liên thu c v i u, trong đó các khuyên t i u đư c tính hai l n. Ta cũng thư ng ký hi u c nh {u, v} ng n g n là uv. Trong trư ng h p t p c nh E là m t đa t p trong t p các c p có phân bi t th t V × V , thì G = (V, E) đư c g i là m t đa đ th có hư ng và các ph n t thu c E đôi khi còn g i là các cung. V i e = (u, v) ∈ E thì u đư c g i là đ nh đ u và v đư c g i là đ nh cu i c a e và ta nói c nh e đi t u đ n v. B c đi ra và b c đi vào c a đ nh u ∈ V là s các c nh đi ra t u và đi vào u tương ng, đư c ký hi u l n lư t là deg+ (u) và deg− (u). N u gi a hai đ nh u, v ∈ V c a đ th G = (V, E) (có hư ng ho c vô hư ng) có nhi u nh t m t c nh thì đ th G đư c g i là đơn đ th (có hư ng ho c vô hư ng tương ng). M t đ th con c a G là m t đ th thu đư c t G b ng cách xóa b t đi m t s đ nh (và các c nh liên thu c v i các đ nh đó) và m t s c nh c a G. M t đ th con bao trùm c a G n u nó có t p đ nh trùng v i t p đ nh c a G. Đ th con c m sinh b i t p đ nh V ⊆ V c a G, ký hi u là G[V ], là m t đ th con c a G v i t p đ nh là V và t p các c nh là t t c các c nh c a G mà có hai đ u mút thu c V . M t đư ng đi có hư ng đ dài k t đ nh u đ n đ nh v trong G là dãy v0 , . . . , vk sao cho v0 = u, vk = v, vi ∈ V và (vi , vi+1 ) ∈ E v i m i i = 0, . . . , k − 1. Khi đó, đ nh u đư c g i là đ nh đ u và đ nh v đư c g i là đ nh cu i c a đư ng đi. Đư ng đi đơn là m t đư ng đi mà không có hai c nh nào đư c l p l i. M t chu trình c a G là m t đư ng đi sao cho đ nh đ u và đ nh cu i c a nó là trùng nhau. Các khái ni m đư ng đi và chu trình trong trư ng h p vô hư ng đư c đ nh nghĩa m t cách tương t . Đ th G (có hư ng ho c vô hư ng) đư c g i là liên thông n u gi a hai đ nh tùy ý c a G đ u có m t đư ng đi vô hư ng (n u là đ th có hư ng thì không xét đ n 14
hư ng c a các c nh). Đ th có hư ng đư c g i là liên thông m nh n u gi a hai đ nh tùy ý c a nó có m t đư ng đi có hư ng. T p S ⊆ V đư c g i là m t thành ph n liên thông c a đ th vô hư ng G = (V, E) n u G[S] là liên thông và v i m i S S thì G[S ] không liên thông. T p S ⊆ V đư c g i là m t thành ph n liên thông m nh c a đ th có hư ng G = (V, E) n u G[S] là liên thông m nh và v i m i S S thì G[S ] không liên thông m nh. T p S ⊆ V đư c g i là m t thành ph n đóng (closed component) c a đ th có hư ng G n u S là m t thành ph n liên thông m nh và không t n t i c nh nào c a G đi ra t m t đ nh trong S. Ti p theo, chúng tôi nh c l i khái ni m c a m t d ng đ th đ c bi t đư c nghiên c u và ng d ng r t nhi u trong tin h c b i c u trúc đơn gi n c a nó, đư c g i là cây. Đ nh nghĩa 1.1.2 (Cây). M t đ th vô hư ng, liên thông, không có chu trình đư c g i là m t cây. D th y r ng trong m t cây thì s đ nh nhi u hơn s c nh đúng là 1. Hơn n a, ta có các đi u ki n tương đương thư ng đư c s d ng đ ch ng minh tính ch t cây như sau: Đ nh lý 1.1.1. Cho G = (V, E) là m t đ th vô hư ng và |V | = n. Các m nh đ sau là tương đương: i) G là m t cây. ii) G là liên thông và |E| = |V | − 1. iii) G không có chu trình và |E| = |V | − 1. iv) Gi a hai đ nh c a G t n t i duy nh t m t đư ng đi đơn. v) G không có chu trình và n u thêm b t kỳ c nh nào vào G thì đ th nh n đư c s có m t chu trình đơn. 15