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
Cn
Kn
Wn
C(t)
Cv (t)
L
fvi (t)
Mô hình chip-firing game
Chu trình n đỉnh
Đồ thị đầy đủ n đỉnh
Đồ thị bánh xe n đỉnh
Cấu hình chip tại thời điểm t
Cấu hình chip của đỉnh v tại thời điểm t
Ma trận Laplace
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
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
1.10
1.11
1.12
Một ví dụ về đồ thị đơn . . . . . . . . . . . . . . . . . . . .
Một ví dụ về đa đồ thị . . . . . . . . . . . . . . . . . . . . .
Một ví dụ về đồ thị có khuyên . . . . . . . . . . . . . . . .
Một ví dụ về đồ thị có hướng . . . . . . . . . . . . . . . . .
Một ví dụ về đồ thị đơn có hướng (a), đa đồ thị có hướng (b)
Một ví dụ về chu trình: (a) C3 , (b)C4 , (c) C5 . . . . . . . . .
Một ví dụ về đồ thi đầy đủ: (a) K4 , (b) K5 . . . . . . . . . .
Đồ thị hai phía đầy đủ: (a) K2,3 , (b) K3,3 . . . . . . . . . . .
Đồ thị bánh xe: (a) W3 , (b) W4 , (c) W5 . . . . . . . . . . . .
Đồ thi liên thông . . . . . . . . . . . . . . . . . . . . . . .
Đồ thị không liên thông . . . . . . . . . . . . . . . . . . . .
Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 4
. 4
. 5
. 5
. 6
. 8
. 8
. 9
. 9
. 10
. 10
. 11
2.1
2.2
2.3
2.4
2.5
Cấu hình ban đầu của chip trên đồ thị .
Bắn chip trên chu trình C3 . . . . . . .
Bắn chip trên đồ thị . . . . . . . . . . .
Đồ thị cho ma trận Laplace . . . . . . .
Cấu hình chip ban đầu trên chu trình C6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
14
17
18
20
3.1
3.2
3.3
3.4
3.5
Cấu hình ban đầu của chip trên đường đi
Cấu hình ban đầu của chip trên đồ thị .
Cấu hình ban đầu của chip trên chu trình
Cây có chu kỳ T = 2 . . . . . . . . . .
Chu trình có chu kỳ T = 5 . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
23
25
30
31
Danh sách bảng
2.1
Bắn chip trên chu trình C6 . . . . . . . . . . . . . . . . . . . 20
3.1
3.2
3.3
Bắn chip song song trên đường đi . . . . . . . . . . . . . . . . 22
CFG song song trên chu trình . . . . . . . . . . . . . . . . . . 25
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Ị
1.1 CÁC KHÁI NIỆM CƠ BẢN . . . . . . . . . . . . .
1.2 MỘT SỐ DẠNG ĐỒ THỊ VÀ VÍ DỤ . . . . . . . .
1.3 ĐƯỜNG ĐI, CHU TRÌNH VÀ TÍNH LIÊN THÔNG
1.4 CÂY . . . . . . . . . . . . . . . . . . . . . . . . . .
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
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
7
8
10
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
(1.2)
deg(v) = 2|E| − ℓ .
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ó.
N (v).
Lân cận của một tập hợp các đỉnh W ⊂ V là N (W ) =
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}.
- Xem thêm -