Viện Khoa học và Công Nghệ Việt Nam
Viện Toán Học
|||||||||||||-
Lê Mạnh Hà
Cấu trúc không gian trạng thái và tính
đạt đợc của một số hệ động lực rời rạc
luận án tiến sĩ toán học
Hà Nội - 2010
Viện Khoa học và Công Nghệ Việt Nam
Viện Toán Học
||||||||||||||
Lê Mạnh Hà
Cấu trúc không gian trạng thái và tính
đạt đợc của một số hệ động lực rời rạc
Chuyên ngành: Đảm bảo toán học cho
máy tính và hệ thống tính toán
Mã số: 62 46 35 01
luận án tiến sĩ toán học
Tập thể hớng dẫn khoa học:
1. TS. Phan Thị Hà Dơng
2. PGS. TS. Phan Trung Huy
Hà Nội - 2010
Lời cam đoan
Tôi xin cam đoan đây là công trình nghiên cứu của tôi. Các kết quả của luận án là
mới và cha từng đợc ai công bố trong bất kì công trình nào khác.
Tác giả
Lê Mạnh Hà
Lời cảm ơn
Tôi không thể diễn tả hết bằng lời lòng biết ơn sâu sắc của tôi đối với cô giáo TS.
Phan Thị Hà Dơng và cũng không lời nào có thể kể hết công lao của Cô đối với
tôi. Hơn cả một ngời hớng dẫn khoa học, Cô rèn rũa tôi từng ngày trong suốt

thể hoàn thành luận án này.
Tôi xin cảm ơn các bạn trong xêmina "Tính toán tổ hợp và các hệ động lực rời
rạc" về những thảo luận và góp ý trong các buổi xêmina. Đặc biệt, tôi xin cám ơn
bạn Phạm Văn Trung và bạn Trần Thị Thu Hơng đã cùng tôi học tập và trao đổi
kiến thức dới sự hớng dẫn của Cô giáo Phan Thị Hà Dơng trong suốt hai năm
qua. Bạn Trần Thị Thu Hơng đã đọc kỹ bản thảo của luận án và chỉ ra các lỗi
trong luận án. Nhân dịp này tôi trân trọng cảm ơn những ý kiến trao đổi của các
bạn cũng nh những tình cảm của các bạn đã dành cho tôi trong những lúc khó
khăn trong cuộc sống.
Tôi xin cảm ơn khoa Toán trờng Đại học S phạm - Đại học Huế đã trang bị
cho tôi những kiến thức cơ bản về toán học. Tôi xin cảm ơn Ban giám hiệu trờng
Đại học S phạm - Đại học Huế đã cho tôi cơ hội đợc đi học tập và nghiên cứu.
Tôi xin cảm ơn Ban chủ nhiệm khoa Giáo dục Tiểu học đã tạo điều kiện thu xếp
công việc thuận lợi cho tôi trong suốt thời gian tôi làm nghiên cứu sinh.
Cuối cùng tôi muốn bày tỏ lòng biết ơn sâu sắc tới bố, mẹ, và em gái, những
ngời đã cảm thông và chia sẻ mọi khó khăn cùng tôi suốt những năm tháng qua
để tôi có thể hoàn thành luận án này.
i
Mục lục
Mở đầu 1
Chơng 1. Kiến thức chuẩn bị 5
1.1 Tập thứ tự - Dàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Tập thứ tự . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Dàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Một số kiến thức cơ bản về lý thuyết đồ thị . . . . . . . . . . . . . 12
1.3 Hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4 Hệ động lực rời rạc . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Chơng 2. Mô hình cột cát và phân hoạch của số tự nhiên 20
2.1 Phân hoạch số tự nhiên và hệ động lực rời rạc . . . . . . . . . . . . 21
2.1.1 Các định nghĩa và ký hiệu . . . . . . . . . . . . . . . . . . . 21

4.2 Cấu trúc thứ tự của CCFG trên DAG . . . . . . . . . . . . . . . . . 71
4.3 Thuật toán xác định thứ tự của hệ CCFG trên DAG . . . . . . . . . 75
4.3.1 Thuật toán sinh ra các lọc . . . . . . . . . . . . . . . . . . . 77
4.3.2 Thuật toán so sánh hai trạng thái . . . . . . . . . . . . . . . 82
iii
4.4 Mạng vận tải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.5 Tính đạt đợc của hệ CCFG trên đồ thị có hớng . . . . . . . . . . 86
4.6 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.7 Kết luận chơng 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Kết luận của luận án 94
Các công trình liên quan đến luận án 96
Tài liệu tham khảo 98
iv
Danh sách các hình vẽ
1.1 Một số ví dụ về tập thứ tự. . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Một số ví dụ về các dàn. . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Ví dụ về đa đồ thị vô hớng (trái) và đa đồ thị có hớng (phải). . . 14
1.4 Ví dụ về đồ thị vô hớng (trái) và đồ thị có hớng (phải). . . . . . . 14
1.5 Ví dụ về đồ thị có hớng. . . . . . . . . . . . . . . . . . . . . . . . 16
2.1 Luật rơi (V) và luật trợt (H) trong hệ Brylawsky. . . . . . . . . . . 22
2.2 Luật dọc (V) và luật ngang (H) trong trờng hợp d = 2. . . . . . . . 24
2.3 Các phần tử đầu tiên của dàn vô hạn 2-P(). . . . . . . . . . . . 28
2.4 Cây các phân hoạch 2-chặt . . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Cấu trúc đệ quy của các cây con X
k
. . . . . . . . . . . . . . . . . 35
2.6 Biểu diễn cây T
d-P
nh một dây chuyền. . . . . . . . . . . . . . . . 35
2.7 Biểu diễn cây T

1
trong trờng hợp
c
1
(i) > 0, c
1
(j) > 0. . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.12 Luồng cực đại f đợc xây dựng dựa trên luồng f
1
trong trờng hợp
c
1
(i) < 0, c
1
(j) > 0. . . . . . . . . . . . . . . . . . . . . . . . . . . 91
vi
Danh mục các ký hiệu
Ký hiệu Giải thích Trang
, Quan hệ thứ tự bộ phận 5
, Quan hệ phủ 6
: P Q Phép nhúng thứ tự 7
x ideal thứ tự sinh bởi phần tử x 7
Q ideal thứ tự sinh bởi tập con Q 7
x Lọc thứ tự sinh bởi phần tử x 7
Q Lọc thứ tự sinh bởi tập con Q 7
Cận trên bé nhất 8, 9
Cận dới lớn nhất 8, 9
Đẳng cấu dàn 10
P(X), 2
X

d-P ()
, T
d-P
Cây các phân hoạch d-chặt của số tự nhiên 30
T
SP
Cây các phân hoạch chặt của số tự nhiên 35
T
P
Cây các phân hoạch của số tự nhiên 36
sp(k) Số các phân hoạch chặt của số tự nhiên k 40
CFG Chip Firing Game 43
CF G(G) Hệ động lực CFG trên đồ thị G 44
CF G(G, O) Hệ động lực CFG trên đồ thị G, với trạng thái ban đầu O 45

CF G
Quan hệ thứ tự trên CF G(G, O) 46
inf(a, b) Cận dới bé nhất của a và b trong CFG(G, O) 47
a b b nhận đợc từ a trong CF G(G, O) 47
L(CF G) Lớp dàn sinh bởi các CFG hội tụ 48
D Lớp các dàn phân phối 48
ColCF G(G) CFG tô màu trên đồ thị G 50
CCFG CFG tơng tranh (Conflicting Chip Firing Game) 52
CCF G(G, n) Hệ động lực CCFG trên đồ thị G, tổng số chip n 52

CCFG
Quan hệ thứ tự trên CCFG(G, n) 52
F(V ) Tập tất cả các lọc thứ tự của V 72
1
Mở đầu

điểm dừng hay điểm đột biến của hệ. Ngoài ra, cấu trúc dàn cho phép xác định tính
đạt đợc: những trạng thái đạt đợc từ hai trạng thái a và b cho trớc có thể đạt
đợc từ trạng thái c = a b, c là cận dới lớn nhất của a và b. Phơng pháp ECO
là phơng pháp mới [9], [10] rất hữu hiệu trong việc tính toán lực lợng của các hệ
nhờ vào cấu trúc đệ quy của cây ECO, và có mối liên hệ chặt chẽ với hàm sinh.
Tiếp theo, chúng tôi tìm hiểu mối quan hệ giữa các hệ CFG và mở rộng của nó
với các hệ tin học nổi tiếng (mạng Petri). Mạng Petri đã đợc định nghĩa từ những
năm 1962 [67], và đã đợc nghiên cứu trong nhiều công trình [13], [39], [42], [43],
[45], [63], [65], [66], [68], [77]. Việc chứng minh mối liên hệ giữa các hệ CFG
và mạng Petri cho phép sử dụng các phơng pháp nghiên cứu cũng nh các thuật
toán của mạng Petri vào nghiên cứu các hệ CFG. Cuối cùng, chúng tôi sử dụng lý
thuyết tập sắp thứ tự (order theory) để nghiên cứu cấu trúc thứ tự của không gian
trạng thái của các hệ CFG mở rộng. Đặc biệt, chúng tôi còn tìm hiểu mối liên hệ
giữa các hệ CFG mở rộng và lý thuyết luồng trong mạng để giải bài toán đạt đợc
(reachability problem) của hệ CFG mở rộng. Bài toán đạt đợc là một bài toán
quan trọng trong việc nghiên cứu các hệ. Một mặt nó cho biết các trạng thái nào
có thể xảy ra, các trạng thái nào không bao giờ xảy ra. Mặt khác, nó cho ta biết
mối quan hệ giữa các trạng thái, từ trạng thái nào đợc đến trạng thái nào. Trong
trờng hợp mạng Petri tổng quát, đây là bài toán mở. Chỉ có một số ít trờng hợp
giải đợc trong thời gian đa thức, còn nhiều trờng hợp đã đợc chứng minh là NP
đầy đủ. Trong luận án, chúng tôi đã xây dựng thuật toán giải bài toán đạt đợc của
3
hệ CCFG trong thời gian O(|V |
3
), trong đó |V | là số đỉnh của đồ thị nền.
Luận án đợc chia làm 4 chơng. Trong Chơng 1, chúng tôi nhắc lại một số
kiến thức cơ bản đã biết sẽ đợc sử dụng trong luận án nh: lý thuyết tập sắp thứ
tự, lý thuyết dàn, một số khái niệm liên quan đến lý thuyết đồ thị, phơng pháp
đếm bằng hàm sinh. Phần cuối chơng này sẽ trình bày các khái niệm về hệ động
rời rạc và một số bài toán liên quan.

các trạng thái của hệ để đặc trng cho thứ tự của không gian trạng thái và chúng
tôi xây dựng thuật toán để xác định thứ tự này. Phần cuối chơng này, chúng tôi
nghiên cứu bài toán đạt đợc của hệ CCFG trên đồ thị có hớng tổng quát. Chúng
tôi đa ra khái niệm mạng vận tải tơng ứng với trạng thái của hệ để đặc trng cho
tính đạt đợc của hệ CCFG. Chúng tôi sử dụng thuật toán Push-Relabel, một biến
thể của thuật toán Ford-Fulkerson để giải bài toán đạt đợc của hệ CCFG trong thời
gian O(m
3
) với m là số đỉnh của đồ thị nền của hệ CCFG.
Trong phần kết luận của luận án, chúng tôi tóm tắt lại các kết quả đã đạt đợc
và nêu một số hớng nghiên cứu tiếp theo.
5
Chơng 1
Kiến thức chuẩn bị
Trong chơng này chúng tôi trình bày một số kiến thức cơ sở và một số kết quả
đã biết về tập sắp thứ tự, dàn, hàm sinh, đồ thị và một số khái niệm và bài toán
trong lý thuyết hệ động lực rời rạc nhằm giúp cho việc trình bày các kết quả trong
các chơng sau. Các kiến thức trong chơng này đợc tham khảo trong các tài liệu
[1, 11, 23, 73, 75, 76, 80].
1.1 Tập thứ tự - Dàn
1.1.1 Tập thứ tự
Định nghĩa 1.1.1. Cho P là một tập hợp. Một thứ tự (hay thứ tự bộ phận) trên P
là một quan hệ hai ngôi trên P thỏa mãn 3 tính chất sau với mọi x, y, z P,
+ Tính phản xạ: x x,
+ Tính phản đối xứng: nếu x y và y x thì x = y,
+ Tính bắc cầu: nếu x y và y z thì x z.
Một tập P đợc trang bị quan hệ thứ tự đợc gọi là một tập thứ tự (ordered
set) hay là tập thứ tự bộ phận (partially ordered set) và ký hiệu là (P, ) khi cần
nhắc đến quan hệ thứ tự .
Cho P là một tập thứ tự và Q là một tập con của P . Khi đó trên Q cảm sinh

2
Hình 1.1: Một số ví dụ về tập thứ tự.
7
Mối quan hệ giữa các tập thứ tự đợc nhắc lại trong định nghĩa sau
Định nghĩa 1.1.4. Cho P và Q là các tập thứ tự. Khi đó, ánh xạ : P Q đợc
gọi là
(i) bảo toàn thứ tự (order-preserving) nếu với mọi x, y P mà x y thì
(x) (y) trong Q,
(ii) một phép nhúng thứ tự (order embedding) nếu với mọi x, y P , x y khi
và chỉ khi (x) (y) trong Q,
(iii) một đẳng cấu thứ tự (order isomorphism) nếu là một phép nhúng thứ tự
và là một song ánh.
Nếu là một phép nhúng thứ tự thì ta ký hiệu : P Q. Nếu tồn tại một
đẳng cấu thứ tự giữa P và Q thì ta nói P đẳng cấu với Q và ký hiệu là P Q.
Một trong những họ tập thứ tự quan trọng là ideal thứ tự (order ideal) và lọc thứ
tự (order filter) đợc nhắc lại trong định nghĩa sau:
Định nghĩa 1.1.5. Cho P là một tập thứ tự và Q là một tập con của P . Khi đó:
(i) Q đợc gọi là một ideal thứ tự (order ideal) nếu với mọi x Q, y P mà
y x thì y Q,
(ii) Q đợc gọi là một lọc thứ tự (order filter) nếu với mọi x Q, y P mà
y x thì y Q.
Từ định nghĩa trên ta thấy rằng Q là ideal thứ tự khi và chỉ khi P \Q là lọc thứ
tự. Sau này, để cho gọn, đôi khi ta nói ideal (tơng ứng, lọc) thay cho ideal thứ tự
(tơng ứng, lọc thứ tự). Bây giờ, với Q P, x P ta có các ký hiệu sau:
Q := {y P |x Q : y x}, Q := {y P |x Q : y x},
x := {y P |y x}, x := {y P |y x}.
Từ các định nghĩa này, ta dễ dàng kiểm tra đợc Q là ideal bé nhất chứa Q và
Q là lọc bé nhất chứa Q. Q (tơng ứng, Q) còn đợc gọi là ideal (tơng ứng,
8
lọc) thứ tự sinh bởi Q. Họ tất cả các ideal (tơng ứng, lọc) của P đợc ký hiệu là

đều tồn tại cận trên nhỏ nhất và cận dới lớn nhất.
Định nghĩa 1.1.8. Cho L là một tập thứ tự khác rỗng. Khi đó
(i) Nếu x y và xy tồn tại với mọi x, y L thì L đợc gọi là một dàn (lattice).
(ii) Nếu

S và

S tồn tại với mọi S L thì L đợc gọi là một dàn đầy đủ
(complete lattice).
N
5
M
2
M
3
Hình 1.2: Một số ví dụ về các dàn.
Nếu L là một dàn thì các toán tử và là các phép toán hai ngôi trên L. Khi
đó ta có cấu trúc đại số L, , . Cấu trúc dàn con đợc định nghĩa nh sau:
Định nghĩa 1.1.9. Cho L là một dàn, M là một tập con của L. Khi đó M đợc gọi
là một dàn con của dàn L nếu với mọi a, b M, ta có a b M và a b M.
Nh vậy, một tập con của L là dàn con của dàn L nếu nó đóng đối với các phép
toán , .
Dàn L đợc gọi là có phần tử đơn vị nếu tồn tại 1 L sao cho với mọi
a L, a = a 1. Đối ngẫu lại, dàn L đợc gọi là có phần tử không nếu tồn tại
0 L sao cho với mọi a L, a = a 0.
Một dàn hữu hạn luôn bị chặn bởi 0 =

L và 1 =

L.

(i) dàn phân phối nếu L thỏa mãn luật phân phối:
(a, b, c L) a (b c) = (a b) (a c).
(ii) dàn modula nếu L thỏa mãn luật modula:
(a, b, c L) a c a (b c) = (a b) c.
Nh vậy, nếu một dàn là phân phối thì modula. Ngợc lại thì không đúng. Tồn
tại những dàn modula nhng không phân phối.
Ví dụ 1.1.13. Dàn M
3
(diamond) là dàn modula nhng không phân phối. Dàn N
5
(pentagon) không phải là dàn modula và do đó cùng không là dàn phân phối.
Đặc trng của dàn modula và dàn phân phối đợc trình bày trong Định lý sau
đây. Định lý này có tên gọi là Định lý M
3
N
5
vì các dàn M
3
và N
5
đặc trng
cho tính chất modula và tính chất phân phối.
Định lý 1.1.14. Cho L là một dàn. Khi đó:
(i) Dàn L không phải là dàn modula khi và chỉ khi L chứa dàn N
5
nh là một
dàn con.
(ii) Dàn L không phải là dàn phân phối khi và chỉ khi L chứa dàn M
3
hoặc dàn

ULD [62], nếu mỗi đoạn giữa một phần tử và cận trên bé nhất của các phủ trên
(upper cover) của nó là một siêu khối. Dàn nửa phân phối dới (lower locally
distributive - LLD) đợc định nghĩa đối ngẫu. Một trong những đặc trng của tính
chất phân phối là [74]: dàn L là dàn phân phối khi và chỉ khi L vừa là dàn LLD
vừa là dàn ULD.
1.2 Một số kiến thức cơ bản về lý thuyết đồ thị
Trong phần này chúng tôi nhắc lại một số khái niệm liên quan đến lý thuyết đồ thị
sẽ sử dụng trong các chơng sau.
Định nghĩa 1.2.1. Một đồ thị vô hớng là một cặp có thứ tự G = (V, E), ở đây V
là một tập, E là tập với các phần tử là các đa tập 2 phần tử trên V .
13
Các phần tử của V gọi là các đỉnh, còn các phần tử của E đợc gọi là các cạnh
của đồ thị vô hớng G. Nếu e = {a, b} là một cạnh của G thì a và b đợc gọi là
các đỉnh đầu mút của của cạnh e hay các đỉnh liên thuộc với e. Ta thờng ký hiệu
cạnh {a, b} ngắn gọn là ab.
Định nghĩa 1.2.2. Một đồ thị có hớng là một cặp có thứ tự G = (V, E), ở đây V
là một tập, E là một tập con của tập tích Đề-các V ìV, tức là E là một quan hệ
hai ngôi trên V .
Các phần tử của V gọi là các đỉnh, còn các phần tử của E đợc gọi là các cung
của đồ thị có hớng G. Cụ thể hơn, nếu (a, b) E thì (a, b) đợc gọi là cung của
G với đỉnh đầu là a, đỉnh cuối là b và có hớng đi từ a đến b.
Đồ thị có hớng đợc định nghĩa nh trên cũng thờng đợc gọi là đơn đồ thị
có hớng. Lý do là vì với hai đỉnh a và b bất kỳ tồn tại nhiều nhất một cung với
đỉnh đầu là a và đỉnh cuối là b. Tơng tự, đồ thị vô hớng đợc định nghĩa nh
trên cũng đợc gọi là đơn đồ thị vô hớng.
Trong trờng hợp giữa các cặp đỉnh có thể có nhiều cung (đồ thị có hớng) hay
nhiều cạnh (đồ thị vô hớng), thì ta có khái niệm đa đồ thị đợc định nghĩa nh
sau:
Định nghĩa 1.2.3. Một đa đồ thị vô hớng G là một cặp có thứ tự G = (V, E), ở
đây V là một tập còn E là một đa tập với các phần tử đều là đa tập 2 phần tử trên

= (V

, E

) đợc gọi là đẳng cấu với nhau nếu tồn tại
song ánh : V V

sao cho (a, b) E (tơng ứng, {a, b} E) khi và chỉ khi
((a), (b)) E

(tơng ứng, {(a), (b)} E

). Song ánh nh trên đợc gọi
là đẳng cấu của G và G

. Hai đồ thị đẳng cấu với nhau G và G

đợc ký hiệu là
G

=
G

.
Định nghĩa 1.2.4. Đồ thị G

= (V

, E


cũng đợc
ký hiệu là G

= G[V

].
Định nghĩa 1.2.5. Giả sử G = (V, E) là một đồ thị có hớng. Một đờng đi có
hớng trong G là một dãy v
0
v
1
v
2
. . . v
n
sao cho v
i
V với mọi i = 0, 1, . . . , n và
(v
i1
, v
i
) E với mọi i = 0, 1, . . . , n.
Trong định nghĩa trên, đỉnh v
0
đợc gọi là đỉnh đầu, còn v
n
đợc gọi là đỉnh