Luận văn Thạc sĩ Toán học: Chu kỳ của chip-firing game song song trên đồ thị

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:43

Thêm vào BST

Báo xấu

16
lượt xem 5
download

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

Trong những năm gần đây, mô hình Chip-firing game (CFG) đã thu hút rất nhiều nhà nghiên cứu, nhiều công trình đã được công bố. CFG đã trở thành một phần quan trọng trong cấu trúc tổ hợp (structural combinatoric). Trong khuôn khổ của luận văn chỉ trình bày các kết quả trên đồ thị hữu hạn, liên thông, đơn và vô hướng.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Chu kỳ của chip-firing game song song trên đồ thị

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Mai Thu Huyền CHU KỲ CỦA CHIP-FIRING GAME SONG SONG TRÊN ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2019
BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Mai Thu Huyền CHU KỲ CỦA CHIP-FIRING GAME SONG SONG TRÊN ĐỒ THỊ Chuyên ngành: Toán ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Nguyễn Hoàng Thạch Hà Nội - 2019
i Lời cam đoan Tôi xin cam đoan mọi kết quả của đề tài: "Chu kỳ của chip-firing game song song trên đồ thị" được trình bày lại từ hai bài báo [3] và [4]. Các ví dụ và số liệu trong luận văn là trung thực và chưa được công bố trong các công trình khác. Nếu không đúng như đã nêu trên, tôi xin hoàn toàn chịu trách nhiệm về đề tài của mình. Hà Nội, ngày 25 tháng 11 năm 2019 Mai Thu Huyền
Lời cảm ơn Tôi xin bày tỏ lòng biết ơn tới TS. Nguyễn Hoàng Thạch, thầy đã hướng dẫn, tạo mọi điều kiện thuận lợi và giúp đỡ tôi rất nhiều trong quá trình học tập và làm luận văn. Thầy đã truyền cảm hứng và giúp tôi hoàn thiện bản thân rất nhiều sau quá trình làm việc cùng thầy. Tôi xin gửi lòng cảm ơn tới tất cả thầy cô của Viện Toán Học đã truyền đạt các kiến thức chuyên sâu và ý nghĩa của việc học Toán trong hai năm học. Tôi xin cảm ơn tới tất cả thầy cô và các anh chị của Học viện Khoa học và Công nghệ đã giúp đỡ và quan tâm tôi rất nhiều trong quá trình học tập. Cuối cùng, tôi xin gửi lời tri ân tới bố mẹ, những người thân trong gia đình và bạn bè đã luôn ủng hộ, khích lệ và động viên tinh thần trong suốt quá trình học tập để hoàn thành tốt luận văn thạc sĩ của mình. Hà Nội, ngày 25 tháng 11 năm 2019 Mai Thu Huyền
Danh mục kí hiệu CF G Mô hình chip-firing game Cn Chu trình n đỉnh Kn Đồ thị đầy đủ n đỉnh Wn Đồ thị bánh xe n đỉnh C(t) Cấu hình chip tại thời điểm t Cv (t) Cấu hình chip của đỉnh v tại thời điểm t L Ma trận Laplace fvi (t) Vết của đỉnh vi tại thời điểm t trong chu kỳ T Ski Tập lớn nhất của các kí tự 1 Dki Tập lớn nhất của các kí tự 0
Danh sách hình vẽ 1.1 Một ví dụ về đồ thị đơn . . . . . . . . . . . . . . . . . . . . . 4 1.2 Một ví dụ về đa đồ thị . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Một ví dụ về đồ thị có khuyên . . . . . . . . . . . . . . . . . 5 1.4 Một ví dụ về đồ thị có hướng . . . . . . . . . . . . . . . . . . 5 1.5 Một ví dụ về đồ thị đơn có hướng (a), đa đồ thị có hướng (b) . 6 1.6 Một ví dụ về chu trình: (a) C3 , (b)C4 , (c) C5 . . . . . . . . . . 8 1.7 Một ví dụ về đồ thi đầy đủ: (a) K4 , (b) K5 . . . . . . . . . . . 8 1.8 Đồ thị hai phía đầy đủ: (a) K2,3 , (b) K3,3 . . . . . . . . . . . . 9 1.9 Đồ thị bánh xe: (a) W3 , (b) W4 , (c) W5 . . . . . . . . . . . . . 9 1.10 Đồ thi liên thông . . . . . . . . . . . . . . . . . . . . . . . . 10 1.11 Đồ thị không liên thông . . . . . . . . . . . . . . . . . . . . . 10 1.12 Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1 Cấu hình ban đầu của chip trên đồ thị . . . . . . . . . . . . . 14 2.2 Bắn chip trên chu trình C3 . . . . . . . . . . . . . . . . . . . 14 2.3 Bắn chip trên đồ thị . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Đồ thị cho ma trận Laplace . . . . . . . . . . . . . . . . . . . 18 2.5 Cấu hình chip ban đầu trên chu trình C6 . . . . . . . . . . . . 20 3.1 Cấu hình ban đầu của chip trên đường đi . . . . . . . . . . . . 22 3.2 Cấu hình ban đầu của chip trên đồ thị . . . . . . . . . . . . . 23 3.3 Cấu hình ban đầu của chip trên chu trình . . . . . . . . . . . . 25 3.4 Cây có chu kỳ T = 2 . . . . . . . . . . . . . . . . . . . . . . 30 3.5 Chu trình có chu kỳ T = 5 . . . . . . . . . . . . . . . . . . . 31
Danh sách bảng 2.1 Bắn chip trên chu trình C6 . . . . . . . . . . . . . . . . . . . 20 3.1 Bắn chip song song trên đường đi . . . . . . . . . . . . . . . . 22 3.2 CFG song song trên chu trình . . . . . . . . . . . . . . . . . . 25 3.3 CFG song song trên chu trình 5 đỉnh . . . . . . . . . . . . . . 31
1 Mục lục 1 KIẾN THỨC CHUẨN BỊ VỀ ĐỒ THỊ 3 1.1 CÁC KHÁI NIỆM CƠ BẢN . . . . . . . . . . . . . . . . . . 3 1.2 MỘT SỐ DẠNG ĐỒ THỊ VÀ VÍ DỤ . . . . . . . . . . . . . 7 1.3 ĐƯỜNG ĐI, CHU TRÌNH VÀ TÍNH LIÊN THÔNG . . . . . 8 1.4 CÂY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 CHIP-FIRING GAME TRÊN ĐỒ THỊ 12 2.1 MÔ HÌNH CFG TRÊN ĐỒ THỊ . . . . . . . . . . . . . . . . 12 2.2 TÍNH HỮU HẠN CỦA CFG . . . . . . . . . . . . . . . . . . 14 2.3 CFG VÀ MA TRẬN LAPLACE . . . . . . . . . . . . . . . . 17 3 CFG SONG SONG TRÊN ĐỒ THỊ 21 3.1 MÔ HÌNH CFG SONG SONG TRÊN ĐỒ THỊ . . . . . . . . 21 3.2 CHU KỲ CỦA CHIPS TRÊN CÂY . . . . . . . . . . . . . . 24 A Mã nguồn CFG 33 B Mã nguồn CFG song song 35
2 MỞ ĐẦU Trong những năm gần đây, mô hình Chip-firing game (CFG) đã thu hút rất nhiều nhà nghiên cứu, nhiều công trình đã được công bố. CFG đã trở thành một phần quan trọng trong cấu trúc tổ hợp (structural combinatoric). Năm 1986, CFG được mở đầu bởi bài báo của J. Spencer khi viết về "balancing game". Năm 1991, A. Bjorner, L. Lovasz, và P. W. Shor đã xây dựng mô hình CFG cho đồ thị đơn, vô hướng và liên thông, được trình bày trong [3]. Họ đã chỉ ra tính hữu hạn của CFG, mối liên hệ giữa CFG và ma trận Laplace. Năm 1992, J. Bitar và E. Goles đã xây dựng mô hình CFG song song và chu kỳ của cây,được trình bày trong [4]. Trong khuôn khổ của luận văn chỉ trình bày các kết quả trên đồ thị hữu hạn, liên thông, đơn và vô hướng. Luận văn bao gồm ba chương. Chương 1 trình bày một số định nghĩa và kết quả được sử dụng trong chương 2 và chương 3. Đó là một số khái niệm và tính chất cơ bản của đồ thị. Chương 2 trình bày mô hình CFG, tính hữu hạn của CFG, mối liên hệ giữa CFG và ma trận Laplace. Chương 3 trình bày mô hình CFG song song và chu kỳ của chip trên một dạng đồ thị là cây. Phụ lục A trình bày mã nguồn tìm cấu hình kết thúc của CFG, phụ lục B trình bày mã nguồn tìm cấu hình tại một thời điểm của CFG song song trên đồ thị. Mã nguồn được trình bày bằng ngôn ngữ Python 3 với thư viện được xây dựng cho đồ thị networkx.
3 Chương 1 KIẾN THỨC CHUẨN BỊ VỀ ĐỒ THỊ Phần này trình bày một số kiến thức cơ bản về đồ thị được tham khảo từ [1], [2]. Đó là các kiến thức cơ 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 : ( 1 nếu có một cạnh nối vi và vj , E(vi , vj ) = E(vj , vi ) = 0 nếu không.
4 Hì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.
5 Hì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
6 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 : ( 1 nếu có một cạnh từ vi tới vj , E(vi , 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ận N (v) của một đỉnh v là tập hợp tất cả Scác đỉnh kề với nó. Lân cận của một tập hợp các đỉnh W ⊂ V là N (W ) = N (v). v∈W 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ì: X deg(v) = 2|E| . (1.1) v∈V Nếu G có ` khuyên thì: X deg(v) = 2|E| − ` . (1.2) v∈V Đị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 S đỉnh kế tiếp của nó. Lân cận của một tập hợp các đỉnh W ⊂ V là N (W ) = N (v). v∈W 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ên G = (V, E). Ta có: X X d+ (v) = d− (v) = |E| . (1.3) v∈V v∈V 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.
8 Hì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, đồ thi W3 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).
9 Hì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: v1 v3 v5 v7 v6 v5 v4 v2 . b) Một chu trình: v1 v2 v4 v6 v5 v3 v1 . c) Một đường đi đơn: v1 v2 v4 v6 v5 . Đị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 ,P ..., vn }. Ta đặt Cvi chip vào đỉnh vi với vi ∈ V , cấu hình ban đầu n C ∈ N 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:   deg(vi ), nếu i = j  (wi )j = −1, nếu vi vj ∈ 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}.