Luận văn Chu kỳ của chip - Firing game song song trên đồ thị

sở trong phần tiếp theo của luận văn. 1.1 CÁC KHÁI NIỆM CƠ BẢN Trong phần này trình bày một số khái niệm cơ sở về đồ thị hữu hạn. Định nghĩa 1.1. Một đồ thị (vô hướng) G = (V,E) được xác định bởi: • một tập hợp V khác rỗng gồm các đỉnh, • một tập hợp E gồm các cạnh, mỗi cạnh có hai đầu là hai đỉnh. Định nghĩa 1.2. Nếu giữa hai đỉnh bất kỳ có không quá một cạnh thì G được gọi là một đồ thị đơn. Khi đó E có thể được đồng nhất với một tập hợp các cặp đỉnh không sắp thứ tự. Một cách tương đương, E có thể được đồng nhất với một ánh xạ từ V × V vào {0, 1} sao cho với mọi vi, vj ∈ V : E(vi, vj) = E(vj, vi) = { 1 nếu có một cạnh nối vi và vj , 0 nếu không. 4Hình 1.1: Một ví dụ về đồ thị đơn Ví dụ 1.3. Trong Hình 1.1, G = (V,E) là đồ thị đơn có: • Tập hợp đỉnh V = {a, b, c, d}. • Tập hợp cạnh E = {ab, ac, ad, bc, cd}. Định nghĩa 1.4. Nếu giữa hai đỉnh có thể có nhiều hơn một cạnh thì G được gọi là một đa đồ thị. Khi đó E có thể được đồng nhất với một ánh xạ từ V ×V vào N sao cho với mọi vi, vj ∈ V : E(vi, vj) = E(vj, vi) = số cạnh nối vi và vj . Hình 1.2: Một ví dụ về đa đồ thị Ví dụ 1.5. Trong Hình 1.2, G = (V,E) là đa đồ thị: E(a, b) = E(b, a) = 2; E(a, d) = E(d, a) = 2. 5Hình 1.3: Một ví dụ về đồ thị có khuyên Định nghĩa 1.6. Một cạnh của đồ thị có hai đầu trùng nhau được gọi là một khuyên. Ví dụ 1.7. Cho đồ thị G = (V,E) như Hình 1.3, đỉnh a là đỉnh có khuyên. Định nghĩa 1.8. Một đồ thị có hướng G = (V,E) được xác định bởi: • một tập hợp V khác rỗng gồm các đỉnh, • một tập hợp E gồm các cạnh có hướng (hay cung), mỗi cạnh đi từ một đỉnh đầu tới một đỉnh cuối. Hình 1.4: Một ví dụ về đồ thị có hướng Định nghĩa 1.9. Nếu với hai đỉnh vi, vj bất kỳ, có nhiều nhất một cạnh đi từ vi tới vj thì G được gọi là một đồ thị đơn có hướng. Khi đó E có thể được coi là một tập hợp các cặp có tính thứ tự của các đỉnh. Một cách tương đương, E 6có thể được đồng nhất với một ánh xạ từ V × V vào {0, 1} sao cho với mọi vi, vj ∈ V : E(vi, vj) = { 1 nếu có một cạnh từ vi tới vj , 0 nếu không. Hình 1.5: Một ví dụ về đồ thị đơn có hướng (a), đa đồ thị có hướng (b) Định nghĩa 1.10. Nếu từ một đỉnh tới một đỉnh khác có thể có nhiều hơn một cạnh thì G được gọi là một đa đồ thị có hướng. Khi đó E có thể được đồng nhất với một ánh xạ từ V × V vào N sao cho với mọi vi, vj ∈ V : E(vi, vj) = số cạnh từ vi tới vj . Định nghĩa 1.11. Xét một đồ thị đơn vô hướng G = (V,E). Nếu hai đỉnh vi, vj được nối bởi một cạnh e thì ta nói vi, vj là hai đỉnh kề nhau và cạnh e kề với các đỉnh vi, vj. Lân cậnN (v) của một đỉnh v là tập hợp tất cả các đỉnh kề với nó. Lân cận của một tập hợp các đỉnhW ⊂ V là N (W ) = ⋃ v∈W N (v). Bậc của một đỉnh v, ký hiệu là deg(v) là số cạnh kề với nó. Ví dụ 1.12. Cho đồ thị G = (V,E) là một đồ thị đơn vô hướng với V = {a, b, c, d}; E = {ab, ac, ad, bc, cd} như Hình 1.1, lân cận của đỉnh a : N (a) = {b, c, d} và bậc của đỉnh a : deg(a) = 3. Lân cận của đỉnh b là: N (b) = {a, c} và bậc của đỉnh b: deg(b) = 2 7Định lý 1.13 (Bổ đề bắt tay). Cho (đa) đồ thị vô hướng G = (V,E). Nếu G không có khuyên thì: ∑ v∈V deg(v) = 2|E| . (1.1) Nếu G có ` khuyên thì: ∑ v∈V deg(v) = 2|E| − ` . (1.2) Định nghĩa 1.14. Xét một đa đồ thị có hướng G = (V,E). Nếu có một cạnh a đi từ đỉnh vi tới đỉnh vj thì ta nói vj là một đỉnh kế tiếp của vi, vi là một đỉnh liền trước của vj, a là một cạnh đi ra của vi và là một cạnh đi vào của vj. Lân cận N (v) của một đỉnh v là tập hợp tất cả các đỉnh kế tiếp của nó. Lân cận của một tập hợp các đỉnhW ⊂ V là N (W ) = ⋃ v∈W N (v). Bậc đi ra của một đỉnh v, ký hiệu là d+(v), là số cạnh đi ra từ v. Bậc đi vào của một đỉnh v, ký hiệu là d−(v), là số cạnh đi vào v. Ví dụ 1.15. Trong Hình 1.5(a), lân cận của đỉnh a : N (a) = {b, c, d}, bậc đi ra d+(a) = 2 và bậc đi vào d−(a) = 1. Định lý 1.16. Cho đa đồ thị có hướng và có thể có khuyênG = (V,E). Ta có:∑ v∈V d+(v) = ∑ v∈V d−(v) = |E| . (1.3) 1.2 MỘT SỐ DẠNG ĐỒ THỊ VÀ VÍ DỤ Định nghĩa 1.17. Chu trình (Cn) là đồ thị đơn có n đỉnh và tất cả các đỉnh đều có bậc là 2. Trong Hình 1.6 là các chu trình C3, C4, C5. Định nghĩa 1.18. Đồ thị đầy đủ Kn là đồ thị đơn, liên thông, vô hướng gồm n đỉnh sao cho hai đỉnh bất kỳ đều được nối với nhau và ∀v ∈ V : deg(v) = n− 1. 8Hình 1.6: Một ví dụ về chu trình: (a) C3, (b)C4, (c) C5 Hình 1.7: Một ví dụ về đồ thi đầy đủ: (a) K4, (b) K5 Ví dụ 1.19. Trong Hình 1.7, đồ thị K4 các đỉnh đều có bậc là 3, và đồ thị K5 các đỉnh đều có bậc là 4. Định nghĩa 1.20. Đồ thị G = (V,E) được gọi là đồ thị hai phía đầy đủ nếu ∃V1 ⊂ V sao cho tất cả các cạnh của G chỉ nối một đỉnh thuộc V1, |V1| = m với một đỉnh thuộc V2 = V \ V1, |V2| = n. Trong Hình 1.8, minh họa cho đồ thị hai phía đầy đủ K2,3 và K3,3 Định nghĩa 1.21 (Wn). Đồ thị G = (V,E) có n đỉnh {v1, ..., vn} được gọi là đồ thị bánh xe nếu ∀i ≤ n− 1 : deg(vi) = 3, deg(vn) = n− 1. Ví dụ 1.22. Trong Hình 1.9, đồ thiW3 có các đỉnh đều có bậc 3. Đồ thịW4, các đỉnh a, b, c, d có bậc 3 và đỉnh e có bậc là 4. Đồ thịW5, các đỉnh a, b, c, d, e có bậc 3 và đỉnh f có bậc 5. 1.3 ĐƯỜNG ĐI, CHU TRÌNH VÀ TÍNH LIÊN THÔNG Định nghĩa 1.23. Xét một (đa) đồ thị vô hướng G = (V,E). 9Hình 1.8: Đồ thị hai phía đầy đủ: (a) K2,3, (b) K3,3 Hình 1.9: Đồ thị bánh xe: (a)W3, (b)W4, (c)W5 Một đường đi độ dài ` từ đỉnh u tới đỉnh v là một dãy ` cạnh e1, e2, . . . , e` sao cho tồn tại các đỉnh u = x0, x1, . . . , x`−1, x` = v sao cho ei kề với xi−1 và xi với mọi i = 1, 2, . . . , `− 1. Ta nói u là điểm đầu, v là điểm cuối của đường đi. Một chu trình là một đường đi có điểm đầu và điểm cuối trùng nhau. Một đường đi đơn (tương tự, chu trình đơn) là một đường đi (chu trình) không đi qua cạnh nào quá một lần. Ví dụ 1.24. Trong Hình 1.10 có: a) Một đường đi độ dài 7: v1v3v5v7v6v5v4v2. b) Một chu trình: v1v2v4v6v5v3v1. c) Một đường đi đơn: v1v2v4v6v5. Định nghĩa 1.25. Đồ thị G là liên thông nếu giữa hai đỉnh bất kỳ có một đường đi. 10 Hình 1.10: Đồ thi liên thông Ví dụ 1.26. Đồ thị G trong Hình 1.11 là đồ thị không liên thông do đỉnh v6 không được nối với đỉnh nào. Hình 1.11: Đồ thị không liên thông 1.4 CÂY Định nghĩa 1.27. Một cây là một đồ thị vô hướng liên thông và không có chu trình. Từ định nghĩa trên, có thể suy ra một cây là một đồ thị không có khuyên và không có cạnh bội. Chúng ta thường xét các cây có gốc, tức là một cây trong đó chúng ta chọn ra một đỉnh gốc và quy ước rằng tất cả các cạnh “hướng ra khỏi gốc”. Với mỗi cạnh, đỉnh gần gốc hơn được gọi là đỉnh cha (hoặc mẹ), đỉnh xa gốc hơn được gọi là đỉnh con. Các đỉnh cùng cha (mẹ) được gọi là các đỉnh anh (chị) em. 11 Đỉnh u là một tổ tiên của đỉnh v, đỉnh v là một hậu duệ của u nếu u nằm trên đường đi từ gốc tới v. Một đỉnh không có con được gọi là một lá. Một đỉnh không phải là lá được gọi là một đỉnh trong. Tầng của một đỉnh là khoảng cách từ đỉnh đó tới gốc. Tầng lớn nhất của một đỉnh được gọi là chiều cao của cây. Hình 1.12: Cây Ví dụ 1.28. Trong Hình 1.12, đỉnh v1 là đỉnh gốc, đỉnh v4 là đỉnh cha của v5, v6, v7, các đỉnh v5, v7, v8, v10, v12, v13, v14 là đỉnh lá. Kết quả sau cho ta một số tính chất quan trọng, và cũng có thể được coi là các định nghĩa tương đương của cây. Định lý 1.29. Xét một đồ thịG vô hướng và không có khuyên. Gọi n là số đỉnh của G. Các khẳng định sau là tương đương: 1. G là một cây. 2. G liên thông và có n− 1 cạnh. 3. G có n− 1 cạnh và không có chu trình. 4. Giữa hai đỉnh khác nhau bất kỳ của G có đúng một đường đi. 5. G không có chu trình nhưng thêm một cạnh nối hai đỉnh không kề nhau bất kỳ tạo ra một đồ thị có đúng một chu trình đơn. 12 Chương 2 CHIP-FIRING GAME TRÊN ĐỒ THỊ Chương này trình bày một số khái niệm, kết quả về tính hữu hạn và tính chất của ma trận Laplace của chip-firing game trên đồ thị đơn, liên thông và vô hướng. Kết quả đã được trình bày lại trong [3] của A. Bjorner, L. Lovasz, và P. W. Shor. Chip-firing game được giới thiệu sơ lược như sau: mỗi đỉnh của đồ thị chứa một số chip, một lần di chuyển chip bao gồm chọn một đỉnh sao cho số chip của nó luôn lớn hơn hoặc bằng số bậc của nó và gửi một chip tới mỗi đỉnh kề của nó. Trò chơi kết thúc nếu không có đỉnh nào di chuyển được. Trong chương này ta sẽ chỉ ra rằng tính hữu hạn của trò chơi và cấu hình kết thúc độc lập với cách chọn các bước di chuyển. 2.1 MÔ HÌNH CFG TRÊN ĐỒ THỊ Trong phần này định nghĩa mô hình chip-firing game và luật bắn trên đồ thị hữu hạn bất kỳ. Bắt đầu với N chip trên đồ thị sao cho trên mỗi đỉnh có một số chip. Mỗi bước bao gồm chọn một đỉnh v sao cho số chip lớn hơn hoặc bằng số bậc của nó và di chuyển một chip từ v tới mỗi đỉnh kề của nó. Ta gọi bước này là bắn đỉnh v. Trò chơi kết thúc khi mỗi đỉnh đều có số chip ít hơn số bậc của nó. Các khái niệm được định nghĩa cụ thể dưới đây. Định nghĩa 2.1. Một mô hình "chip-firing game" (CFG) là một hệ động lực rời rạc, được cho bởi: 13 • Một đồ thị G = (V,E) đơn, liên thông và vô hướng có n đỉnh. • Một cấu hình ban đầu C(0) = (Cv1(0), ..., Cvn(0)) ∈ N|V |, trong đó Cvi(0) là số chip ban đầu tại đỉnh vi. Định nghĩa 2.2. Một trạng thái hay một cấu hình của CFG là một phân phối chip trên các đỉnh của đồ thị tại thời điểm t. Một cấu hình của hệ tại thời điểm t ≥ 0 được định nghĩa bởi vector C(t) = (Cv1(t), ...Cvn(t)) ∈ N|V |, ở đó Cvi(t) là số chip của đỉnh vi tại thời điểm t. Xét đồ thị G = (V,E) là một đồ thị đơn, liên thông, vô hướng có n đỉnh V = {v1, v2, ..., vn}. Ta đặt Cvi chip vào đỉnh vi với vi ∈ V , cấu hình ban đầu C ∈ Nn và ∑vi Cvi = N . Luật bắn của CFG trên đồ thị với cấu hình chip được mô tả như sau: • Đỉnh vi bắn được nếu Cvi ≥ deg(vi). • Bắn đỉnh vi tức là ta giảm Cvi bởi số bậc deg(vi) của vi, và tăng Cvj bởi 1 cho mỗi đỉnh kề vj của vi. • Ta có thể định nghĩa wi như sau: (wi)j =  deg(vi), nếu i = j −1, nếu vivj ∈ E(G) 0, ngược lại Khi đó, bắn đỉnh vi tại thời điểm t nghĩa là trừ đi wi từ C = C(t); bước này là hợp lệ nếu C − wi ≥ 0. Một trò chơi hợp lệ là một dãy các cấu hình bất kỳ bắt đầu từ C sao cho mỗi vị trí thu được từ bước hợp lệ trước đó. Ví dụ 2.3. Cho đồ thị có cấu hình chip ban đầu như Hình 2.1, áp dụng luật bắn ta có nhận xét: trong phần (a) các đỉnh bắn được là v1, v2, v4; trong phần (b) các đỉnh bắn được là v1, v3. Ví dụ 2.4. Cho đồ thị với cấu hình chip ban đầu t = 0 (Hình 2.2) là C(0) = {3, 1, 0}. Thực hiện luật bắn chip ta thu được cấu hình tại thời điểm t = 1 là C(1) = {1, 2, 1} và cấu hình chip tại thời điểm t = 2 là C(2) = {2, 0, 2}. 14 Hình 2.1: Cấu hình ban đầu của chip trên đồ thị Hình 2.2: Bắn chip trên chu trình C3 2.2 TÍNH HỮU HẠN CỦA CFG Trong phần này, ta tìm hiểu các điều kiện khi nào trò chơi kết thúc sau hữu hạn bước và khi nào trò chơi vô hạn. Giả sử G = (V,E) là đồ thị đơn, liên thông, vô hướng với n đỉnh, m cạnh và C là cấu hình ban đầu với N chip. Ta bắt đầu bằng bổ đề đơn giản sau đây. Bổ đề 2.5. Nếu một CFG là vô hạn thì mọi đỉnh đều được bắn vô hạn lần. Chứng minh. Vì đồ thị đang xét có hữu hạn đỉnh và CFG là vô hạn nên tồn tại một đỉnh bắn được vô hạn lần. Giả sử v là đỉnh được bắn vô hạn lần. Theo luật bắn, mỗi một lần bắn đỉnh v đều gửi một chip tới mỗi đỉnh kề của nó. Do mỗi đỉnh kề của v không thể có nhiều hơn N chip nên mỗi đỉnh kề của v được bắn vô hạn lần. Lập luận như trên và do đồ thị liên thông nên mọi đỉnh đều được bắn vô hạn lần. 15 Bổ đề 2.6. Nếu một CFG kết thúc thì tồn tại một đỉnh không được bắn lần nào. Chứng minh. Giả sử trò chơi dừng lại sau t bước và tất cả các đỉnh đều được bắn ít nhất một lần. Ta xét đỉnh v với tv là bước bắn cuối cùng của v sao cho |t− tv| là lớn nhất. Suy ra, tất cả các đỉnh kề với v đều được bắn ít nhất một lần giữa thời điểm tv và t. Do đó, giữa thời điểm tv và t thì v nhận được ít nhất deg(v) chip. Suy ra v bắn được tại thời điểm t, mâu thuẫn với giả thiết trò chơi dừng lại sau t bước. Kết quả chính của phần này chỉ ra mối liên hệ giữa tính hữu hạn của trò chơi và cấu hình chip trên đồ thị. Ta có định lý sau đây. Định lý 2.7. Cho G = (V,E) là đồ thị đơn, liên thông, vô hướng với n đỉnh, m cạnh với C là cấu hình ban đầu N chip. (i) Nếu N > 2m− n thì trò chơi là vô hạn. (ii) Nếu m ≤ N ≤ 2m − n thì tồn tại một cấu hình ban đầu C để trò chơi hữu hạn và một cấu hình ban đầu khác C ′ để trò chơi vô hạn. (iii) Nếu N < m thì trò chơi hữu hạn. Chứng minh. (i) Theo giả thiết N > 2m− n ta có: 1 + ∑ vi∈V (deg(vi)− 1) = 1 + (2m− n) ≤ N Theo nguyên lý Diriclet, tại mỗi thời điểm t, tồn tại đỉnh vi sao cho Cvi(t) ≥ deg(vi). Tức là mỗi thời điểm t có ít nhất một đỉnh bắn được. Do đó, trò chơi là vô hạn. (ii) Giả sửm ≤ N ≤ 2m− n • Nếu N ≤ 2m− n, ta đặt số chip Cvi tại mỗi đỉnh vi ∈ V sao cho Cvi ≤ deg(vi) − 1. Suy ra, không có đỉnh nào bắn được. Vậy trò chơi là hữu hạn. • Nếu N ≥ m, ta xây dựng một cấu hình ban đầu của chip như sau: 16 + Định hướng các cạnh củaG sao cho đồ thị không có chu trình. + Đặt d+(vi) chip vào đỉnh vi với mỗi vi ∈ V . + Tồn tại vi sao cho d+(vi) = deg(vi). Sau đó bắn đỉnh vi và đổi chiều tất cả các cạnh kề với vi. + Xét định hướng mới không có chu trình và tại mỗi đỉnh vj ∈ V có d+(vj) chip. Nhận thấy rằng luôn tìm được một đỉnh bắn được. Vậy trò chơi là vô hạn. (iii) Giả sử N < m, ta có: • Định hướng các cạnh của đồ thị G sao cho G không chứa chu trình. • Đặt T (t) = ∑ vi∈V max {Cvi(t)− d+(vi)(t), 0}, do đó T (t) ≥ 0. • Gọi tập hợp các đỉnh không bắn được tại thời điểm t là S(t) = {vi|Cvi(t) < d+(vi)(t)}. • Xét tại thời điểm t, mỗi lần bắn vi ∈ V , đổi chiều tất cả các cạnh kề với vi và cập nhật T (t). + T (t) không tăng vì mỗi lần bắn đỉnh vi ∈ V , thì T (t) = T (t− 1)− (Cvi(t)− d+(vi)(t)). + Nếu tập S(t) thay đổi thì T (t) giảm. • Do T (t) ≥ 0 nên T (t) không thể giảm vô hạn. Vậy trò chơi là hữu hạn. Ví dụ 2.8. Cho đồ thị có cấu hình ban đầu C(0) = {1, 2, 2, 1, 0} như hình 2.3. Xây dựng CFG như phần Mã nguồn CFG trong phần phụ lục A, ta thu được đầu ra như dưới đây. Sau hai lần bắn ta tìm được cấu hình kết thúc C(0) = {1, 3, 0, 2, 0}. The start configure: {'v1':1,'v2':2,'v3':2,'v4':1,'v5':0} At time t = 1 ***The set of firing vertice: ['v3'] ***Firing node: v3 ***The configure: {'v1':1,'v2':3,'v3':0,'v4':2,'v5':0} 17 Hình 2.3: Bắn chip trên đồ thị At time t = 2 ***The set of firing vertice: [] The configure terminate: {'v1':1,'v2':3,'v3':0,'v4':2,'v5':0}. 2.3 CFG VÀ MA TRẬN LAPLACE Trong phần trước ta đã trả lời được câu hỏi khi nào trò chơi hữu hạn và khi nào trò chơi vô hạn. Trong phần này, ta chỉ ra mối liên hệ giữa CFG và ma trận Laplace của đồ thị và số lần bắn nhiều nhất của mỗi đỉnh trong cùng một chu kỳ có tính chất như thế nào. Bổ đề được trình bày lại từ bài báo Chip-firing game on directed graphs [5].Ta định nghĩa ma trận Laplace của đồ thị dưới đây. Định nghĩa 2.9. Ma trận Laplace L = LG = (lij) của đồ thị G với n đỉnh {v1, v2, . . . , vn} là một ma trận có cỡ n× n được định nghĩa như sau: lij =  deg(vi), nếu i = j −1, nếu vivj ∈ E(G) 0, ngược lại 18 Hình 2.4: Đồ thị cho ma trận Laplace Ví dụ 2.10. Trong Hình 2.4, ma trận Laplace của đồ thị: L =  2 −1 0 −1 0 −1 3 −1 −1 0 0 −1 2 −1 0 −1 −1 −1 4 −1 0 0 0 −1 1  Nhận xét. Từ định nghĩa của ma trận Laplace ta có nhận xét như sau: • L là ma trận đối xứng. • 0 là một giá trị riêng củaL tương ứng với vector riêng 1 = (1, 1, ..., 1)T . • L là ma trận nửa xác định dương. • NếuG là đồ thị liên thông thì tất cả các giá trị riêng khác không của ma trận Laplace đều dương. Định nghĩa 2.11. Chu kỳ T của CFG vô hạn được định nghĩa bởi: T = min {k > 0|∃t0,∀t ≥ t0 : C(t+ k) = C(t)} Ta quy ước chu kỳ của CFG hữu hạn là T = 1. Từ tính chất của ma trận Laplace ta chỉ ra mối liên hệ giữa số lần bắn của mỗi đỉnh và ma trận Laplace [5]. 19 Bổ đề 2.12. Cho CFG vô hạn trên đồ thị G với n đỉnh {v1, v2, . . . , vn} có chu kỳ T . Khi đó, tổng số lần bắn của mỗi đỉnh trong chu kỳ T là như nhau. Chứng minh. Giả sử C là cấu hình chip của đồ thị tại thời điểm bất kỳ. Cấu hình C ′ nhận được từ C bằng cách bắn đỉnh vi. Gọi Li là hàng thứ i của ma trận Laplace L. Khi đó, C ′ = C − Li = C − eiL, trong đó ei = (ei1, . . . , ein) với eij = { 1, nếu j = i 0, nếu j 6= i . Bằng phương pháp quy nạp, ta có thể tổng quát như sau: Gọi C ′ là cấu hình nhận được từ C bằng cách bắn mỗi đỉnh vi ∈ V là ki (ki ∈ N) lần thì C ′ = C − (k1 k2 . . . kn)L = C − ~kL, với ~k = (k1 k2 . . . kn). Giả sử trong một chu kỳ T , mỗi đỉnh vi được bắn ki lần ta có: C ′ = C và C ′ = C − ~kL nên ~kL = 0. Đặt D = max{deg(i)}+ 1 và xét L′ = DIn − L thấy rằng • L′ là ma trận không âm. • ~kL′ = ~k (DIn − L) = ~kDIn ⇒ ~kL′ = D~k vì vậy ~k là vector riêng bên trái của L′ ứng với giá trị riêng D. Áp dụng định lý Perron-Frobenius cho ma trận không âmL′, vector ~k là vector riêng duy nhất có tất cả các thành phần đều dương. Mặt khác, 1L′ = 1 (DIn − L) = 1DIn ⇒ 1L′ = D1 (Do 1 là vector riêng tương ứng với giá trị riêng 0). Kết hợp lại ta có:{ ~kL′ = D~k 1L′ = D1 Vậy k1 = k2 = · · · = kn = k, nói cách khác trong một chu kỳ các đỉnh được bắn số lần như nhau. Ví dụ 2.13. Cho chu trình C6 có 6 đỉnh và cấu hình chip ban đầu như hình 2.5. Theo định lý 2.7, CFG là vô hạn. Thực hiện bắn chip như bảng 2.1 thấy rằng trong chu kỳ T = 6 mỗi đỉnh đều được bắn đúng một lần. 20 Hình 2.5: Cấu hình chip ban đầu trên chu trình C6 chips Cv1 Cv2 Cv3 Cv4 Cv5 Cv6 t = 0 1 1 0 2 1 1 t = 1 1 1 1 0 2 1 t = 2 1 1 1 1 0 2 t = 3 2 1 1 1 1 0 t = 4 0 2 1 1 1 1 t = 5 1 0 2 1 1 1 t = 6 1 1 0 2 1 1 Bảng 2.1: Bắn chip trên chu trình C6 21 Chương 3 CFG SONG SONG TRÊN ĐỒ THỊ Chip-firing game (CFG) giới thiệu trong chương 2 được bắt đầu bởi một phân bố chip ban đầu, tại mỗi một thời gian ta chỉ chọn một đỉnh để bắn. Trong chương này trình bày về CFG song song, tại mỗi thời gian ta di chuyển số chip tất cả các đỉnh bắn được và cập nhật số chip trên tất cả các đỉnh. Kết quả chính của chương này là định lý 2.10, chu kỳ của chip trên cây chỉ có thể là một hoặc hai. Trong chương này chỉ xét G = (V,E) là đồ thị hữu hạn, liên thông và vô hướng. Tất cả các kết quả trong chương này được trình bày lại từ bài báo Parallel chip firing game on graphs[4]. 3.1 MÔHÌNHCFGSONGSONGTRÊNĐỒTHỊ Cho G = (V,E) là một đồ thị liên thông, vô hướng, hữu hạn với n đỉnh, m cạnh và N chip. V = {v1, v2, ..., vn} là tập đỉnh. E là tập cạnh. Cấu hình chips ban đầu trên G là vector:C(0) = (Cv1(0), Cv2(0), ..., Cvn(0)) ∈ Nn. Định nghĩa 3.1. Luật bắn song song được định nghĩa bởi: với mỗi vi ∈ V Cvi (t+ 1) = Cvi(t)− deg(vi).fvi(t) + ∑ vj∈N (vi) fvj(t) (3.1) trong đó, Cvi (t) ∈ N là số chip trên mỗi đỉnh vi tại bước t. N (vi) = {vj ∈ V | (vi, vj) ∈ E} là tập đỉnh kề của vi, deg(vi) là bậc của 22 đỉnh vi. Hàm ngưỡng: fvi(t) = 1 (Cvi(t)− deg(vi)) = { 1, Cvi(t) ≥ deg(vi) 0, ngược lại. Nhận xét. Từ (3.1) luôn tìm được số chip trên mỗi đỉnh vi ∈ V tại thời điểm t và được hiểu như sau: • Nếu Cvi ≥ deg(vi) thì đỉnh vi mất đi deg(vi) chip. • Đỉnh vi nhận được một chip từ mỗi đỉnh kề của nó. Hình 3.1: Cấu hình ban đầu của chip trên đường đi Ví dụ 3.2. Cho G = {v1, v2, v3, v4, v5} là một đường đi gồm 5 đỉnh với cấu hình chip ban đầu C(0) = (0, 2, 1, 1, 1) (Hình 3.1). Thực hiện bắn chip song song như bảng 3.1 sau. chips Cv1 Cv2 Cv3 Cv4 Cv5 t = 0 0 2 1 1 1 t = 1 1 0 2 2 0 t = 2 0 2 1 1 1 t = 3 1 0 2 2 0 t = 4 0 2 1 1 1 Bảng 3.1: Bắn chip song song trên đường đi Ví dụ 3.3. Cho đồ thị có cấu hình ban đầu như Hình 3.2 với cấu hình ban đầu C(0) = (3, 4, 2, 1, 2) Thực hiện quá trình bắn chip song song trên đồ thị, với 8 lần bắn cho mỗi đỉnh ta thu được đầu ra như sau: 23 Hình 3.2: Cấu hình ban đầu của chip trên đồ thị The start configure: {'v1':3,'v2':4,'v3':2,'v4':1,'v5':2}↪→ At time t = 1 ***The configure: {'v1':2,'v2':2,'v3':1,'v4':3,'v5':4}↪→ At time t = 2 ***The configure: {'v1':1,'v2':5,'v3':2,'v4':1,'v5':3}↪→ At time t = 3 ***The configure: {'v1':3,'v2':3,'v3':1,'v4':4,'v5':1}↪→ At time t = 4 ***The configure: {'v1':1,'v2':5,'v3':2,'v4':1,'v5':3}↪→ At time t = 5 ***The configure: {'v1':3,'v2':3,'v3':1,'v4':4,'v5':1}↪→ At time t = 6 ***The configure: {'v1':1,'v2':5,'v3':2,'v4':1,'v5':3}↪→ At time t = 7 ***The configure: {'v1':3,'v2':3,'v3':1,'v4':4,'v5':1}↪→ At time t = 8 ***The configure: {'v1':1,'v2':5,'v3':2,'v4':1,'v5':3}↪→ Từ định lý 2.7, thấy rằng trò chơi là vô hạn. Theo định nghĩa của chu kỳ, chọn t0 = 2 thì chu kỳ của CFG song song là T = 2. 24 3.2 CHU KỲ CỦA CHIPS TRÊN CÂY Định nghĩa 3.4. Giả sử trạng thái ổn định là một xích giới hạn (C(0), ..., C(T− 1)) với chu kỳ T . a) Vòng lặp địa phương được định nghĩa bởi: ∀vi ∈ V : Cvi = (Cvi(0), Cvi(1), ..., Cvi(T − 1)) ∈ NT fvi = (fvi(0), fvi(1), ..., fvi(T − 1)) ∈ {0, 1}T trong đó, fvi(t) = 1 (Cvi (t)− deg(vi)) được gọi là vết của đỉnh vi trong vòng lặp địa phương. b) Giá của fvi là tập hợp tất cả các thời điểm mà đỉnh vi bắn được trong chu kỳ T , được định nghĩa bởi: supp(fvi) = {t ∈ [0, T − 1] : fvi(t) = 1} Ta có thể phân hoạch supp(fvi) thành pi các khoảng rời nhau và có thể viết lại như sau: supp(fvi) = pi⋃ k=1 Sik (3.2) trong đó, Sik là tập lớn nhất trên [0, T − 1] của các kí tự 1 và được định nghĩa như sau: Sik = [t, t+ q] sao cho fvi(t + s) = 1, s = 0, ..., q và fvi(t− 1) = fvi(t+ q + 1) = 0. Ví dụ 3.5. Cho đồ thị chu trình như Hình 3.3 có cấu hình chip ban đầuC(0) = {0, 2, 1, 1, 0, 2}. Thực hiện bắn chip song song như bảng 3.2, tìm được chu kỳ của CFG là T = 6 và fv1 = (010001) . S11 = {1}, S12 = {5}, supp(fv1) = 2⋃ k=1 S1k Bổ đề 3.6. Cho G = (V,E) là một đồ thị đơn, liên thông và vô hướng với cấu hình ban đầu của chip C(0) và thực hiện CFG song song trên G. Khi đó, 25 Hình 3.3: Cấu hình ban đầu của chip trên chu trình chips Cv1 Cv2 Cv3 Cv4 Cv5 Cv6 t = 0 0 2 1 1 0 2 t = 1 2 0 2 1 1 0 t = 2 0 2 0 2 1 1 t = 3 1 0 2 0 2 1 t = 4 1 1 0 2 0 2 t = 5 2 1 1 0 2 0 t = 6 0 2 1 1 0 2 Bảng 3.2: CFG song song trên chu trình a) Nếu fvk = ~0⇒ fvi = ~0,∀vi ∈ V fvk = ~1⇒ fvi = ~1,∀vi ∈ V và trong cả hai trường hợp này, vòng lặp địa phương là một điểm cố định, tức là chu kỳ của vết là T = 1. b) Cho [s− k, s] ⊆ supp(fvi) là một tập lớn nhất của các kí tự 1, khi đó ∃vj ∈ N (vi) sao cho [s− k − 1, s− 1] ⊆ supp(fvj). c) Cho [s− k, s] ⊆ (supp(fvi))c, khi đó ∃vj ∈ N (vi) sao cho [s− k − 1, s− 1] ⊆ (supp(fvi))c . 26 Chứng minh. a) Ta chứng minh cho trường hợp fvk = ~0, chứng minh tương tự đối với fvk = ~1. Giả sử fvk = ~0. Từ (3.1) ta có: Cvk(t+ 1) = Cvk(t)− deg(vk)fvk(t) + ∑ vi∈N (vk) fvi(t) = Cvk(t) + ∑ vi∈N (vk) fvi(t) ≥ Cvk(t) Suy ra, Cvk(T − 1) ≥ Cvk(T − 2) ≥ ... ≥ Cvk(0) = Cvk(T ) ≥ Cvk(T − 1). Vì vậy, Cvk = (ak, ..., ak) , ak ≤ deg(vk)− 1 (3.3) Giả sử phản chứng ∃vi ∈ N (vk) và thời điểm t′ ∈ [0, T − 1] sao cho fvi(t ′) = 1. Ta có: Cvk(t ′ + 1) = Cvk(t ′) + ∑ vi∈N (vk) fvi(t ′) ≥ Cvk(t′) + 1 > Cvk(t ′) Điều này mâu thuẫn với (3.3), suy ra fvi = ~0,∀vi ∈ N (vk) và T = 1. Vì G là đồ thị hữu hạn, nên khẳng định cũng đúng cho ∀vi ∈ V. b) Từ (3.1) ta có: Cvi(s) = Cvi(s− 1)− deg(vi)fvi(s− 1) + ∑ vj∈N (vi) fvj(s− 1) = Cvi(s− 2)− deg(vi) [fvi(s− 1) + fvi(s− 2)] + ∑ vj∈N (vi) [ fvj(s− 1) + fvj(s− 2) ] . . . 27 = Cvi(s− k)− k. deg(vi) + ∑ vj∈N (vi) k∑ t=1 fvj(s− t). Do [s− k, s] là tập lớn nhất của fvi, theo định nghĩa ta có: fvi(s− k − 1) = 0⇒ Cvi(s− k − 1) ≤ deg(vi)− 1. Và Cvi(s) = Cvi(s− k − 1)− k. deg(vi) + ∑ vj∈N (vi) k+1∑ t=1 fvj(s− t). Vì vậy, Cvi(s) ≤ deg(vi)− 1− k. deg(vi) + ∑ vj∈N (vi) k+1∑ t=1 fvj(s− t). Giả sử phản chứng với mọi đỉnh kề vj của vi sao cho [s−k−1, s−1] * supp(fvj), tức là ∀vj ∈ N (vi), ∃t∗j ∈ [s− k − 1, s− 1] sao cho fvj(t∗j) = 0. Ta có: ∑ vj∈N (vi) k+1∑ t=1 fvj(s− t) ≤ k. deg(vi)⇒ Cvi(s) ≤ deg(vi)− 1 Vì vậy, fvi(s) = 0, mâu thuẫn với giả thiết [s− k, s] ⊆ supp(fvi). c) Giả sử phản chứng ∀vj ∈ N (vi), ∃t∗j ∈ [s − k − 1, s − 1] sao cho fvj(t ∗ j) = 1. Suy ra, trong tập [s− k, s] đỉnh vi nhận được ít nhất deg(vi) chip. Suy ra, ∃t ∈ [s − k, s] sao cho Cvi(t) ≥ deg(vi), mâu thuẫn với giả thiết. Định nghĩa 3.7. Cho một xích giới hạn và phân hoạch giá (3.2), ta định nghĩa số lớn nhất của các kí tự 1 liên tiếp của các fvi: M = max vi∈V max 1≤k≤pi ∣∣Sik∣∣ 28 Tương tự, ta định nghĩa phân hoạch trên các tập lớn nhất của các kí tự 0. (supp(fvi)) c = qi⋃ k=1 Dik, vi ∈ V trong đóDik là các tập lớn nhất gồm các kí tự 0 liên tiếp trên vector vết fvi. Ta định nghĩa: N = max vi∈V max 1≤k≤qi ∣∣Dik∣∣ Rõ ràng, 0 ≤ M,N ≤ T . NếuM = 0 vàM = T tương ứng với các điểm cố định trong Bổ đề 3.6. Trong trường hợp đồ thị là một cây, ta có bổ đề sau: Bổ đề 3.8. Cho G = (V,E) là một cây và (C(0), C(1), ..., C(T − 1)) là một xích giới hạn của CFG song song. Khi đó, 0 < M < T =⇒M = 1 0 < N < T =⇒ N = 1 tức là, khi vòng lặp địa phương không là một điểm cố định, thì những tập lớn nhất đều có cỡ 1. Chứng minh. Giả sửM ≥ 2, v0 ∈ V sao cho tồn tại tập lớn nhất của fv0 của các kí tự 1, tức là: supp(fv0) ⊇ S0 = [t, t +M − 1], trong đó S0 là một tập