TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP LỚN PHÂN TÍCH VÀ THIẾT
KẾ GIẢI THUẬT

BÀI TẬP LỚN 2

Người hướng dẫn: TS NGUYỄN MINH TUẤN
Người thực hiện: THÁI TRUNG TÍN - 51503315
Lớp : 15050301
Khóa : 19

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2017
1


TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP LỚN PHÂN TÍCH VÀ THIẾT
KẾ GIẢI THUẬT

BÀI TẬP LỚN 2

Người hướng dẫn: TS NGUYỄN MINH TUẤN
Người thực hiện: THÁI TRUNG TÍN - 51503315
Lớp : 15050301
Khóa : 19

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2017
2


LỜI CẢM ƠN
Trong suốt quá trình làm bài tập lớn, em đã gặp rất
nhiều khó khăn từ cách tiếp cận và trình bày ý tưởng nhưng
nhờ có TS Nguyễn Minh Tuấn - Khoa Công nghệ thông tin Trường đại học Tôn Đức Thắng - đã tận tình hướng dẫn đã
giúp em nhìn nhận vấn đề cụ thể, tiếp cận đề tài dễ dàng.
Em xin chân thành cảm ơn thầy vì những lời chỉ bảo vô cùng
quý báu của thầy đã giúp em có những thu hoạch quý giá để
hoàn thành quá trình làm bài tập lớn này.
Bài thu hoạch này được thực hiện trong khoảng thời gian gần
10 tuần. Do vậy, không tránh khỏi những thiếu sót là điều chắc
chắn, em rất mong nhận được những ý kiến đóng góp quý báu
của quý Thầy Cô và các bạn học cùng lớp để kiến thức của em
trong lĩnh vực này được hoàn thiện hơn.
Một lần nữa em xin chân thành cảm ơn.
TP.Hồ Chí Minh,ngày 23 tháng 11 năm 2017
Tác giả
Thái Trung Tín

3


ĐỒ ÁN ĐƯỢC HOÀN THÀNH
TẠI TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
Tôi xin cam đoan đây là sản phẩm đồ án của riêng
tôi và được sự hướng dẫn của TS Nguyễn Minh Tuấn. Các nội

dung nghiên cứu, kết quả trong đề tài này là trung thực và
chưa công bố dưới bất kỳ hình thức nào trước đây. Những số
liệu trong các bảng biểu phục vụ cho việc phân tích, nhận xét,
đánh giá được chính tác giả thu thập từ các nguồn khác nhau
có ghi rõ trong phần tài liệu tham khảo.
Ngoài ra, trong đồ án còn sử dụng một số nhận xét,
đánh giá cũng như số liệu của các tác giả khác, cơ quan tổ chức
khác đều có trích dẫn và chú thích nguồn gốc.
Nếu phát hiện có bất kỳ sự gian lận nào tôi
xin hoàn toàn chịu trách nhiệm về nội dung đồ án của
mình. Trường đại học Tôn Đức Thắng không liên quan đến
những vi phạm tác quyền, bản quyền do tôi gây ra trong quá
trình thực hiện (nếu có).
TP.Hồ Chí Minh,ngày 23 tháng 11 năm 2017
Tác giả
Thái Trung Tín

4


PHẦN XÁC NHẬN, ĐÁNH GIÁ CỦA GIẢNG
VIÊN
Phần xác nhận của giáo viên hướng dẫn

TP.Hồ Chí Minh,ngày 23 tháng 11 năm 2017
Thái Trung Tín
Phần đánh giá của giáo viên chấm bài

TP.Hồ Chí Minh,ngày 23 tháng 11 năm 2017
Thái Trung Tín


5


TÓM TẮT
Tìm hiểu và chứng minh một số vấn đề liên quan bài
toán SAT, 3SAT, k-clique, Independent Set, Vertex
Cover và một số khái niệm về NP và NPC.

6


Mục lục

1 Câu 1: Chứng minh 3-CNF-SAT thuộc
lớp NP-Đầy đủ
1.1 3-CNF-SAT là gì ? . . . . . . . . . .
1.2 3SAT thuộc lớp NP-Đầy đủ . . . . . .
1.3 3SAT thuộc lớp NP . . . . . . . . . .
1.4 3SAT thuộc lớp NP khó . . . . . . . .
1.5 Kết luận . . . . . . . . . . . . . . . .
2 Câu 2
2.1 Thu giảm Independent Set, k-Clique,
Vertex Cover cho nhau . . . . . . . .
2.2 Independent Set ≤P Vertex Cover và
Vertex Cover ≤P Independent Set . . .
2.3 Independent Set ≤P k-Clique và k-Clique
≤P Independent Set . . . . . . . . . .
2.4 Clique ≤P Vertex Cover và Vertex Cover
≤P Clique . . . . . . . . . . . . . . .

2.5 Chứng minh Independent Set, k-Clique,
Vertex Cover là NP-Đầy đủ . . . . . .
2.6 Independent Set là NP-Đầy đủ . . . .
2.7 Chứng minh k-Clique là NP-Đầy đủ . .
2.8 Chứng minh Vertex Cover là NP-Đầy đủ

9
9
9
9
10
11
11
11
11
12
12
13
13
14
17

3 Câu 3: Chứng minh k-coloring thuộc
lớp NP đầy đủ
19
4 Câu 4
24
4.1 Câu 4a: Mã giả giải thuật tô màu tham
lam . . . . . . . . . . . . . . . . . . 24


7


4.2 Câu 4b: Đề xuất giải thuật ngẫu nhiên
cho tô màu . . . . . . . . . . . . . .
5 Tài liệu tham khảo

8

24
26


1

Câu 1: Chứng minh 3-CNF-SAT thuộc lớp
NP-Đầy đủ

1.1

3-CNF-SAT là gì ?

Bài toán 3-CNF-SAT còn được gọi là bài toán về tính khả
thỏa mãn mạch dạng chuẩn CNF hoặc bài toán 3-SAT.
Mỗi mệnh đề (clause) trong công thức có 3 đơn tử (literal).
Ta còn có thể gọi 3-CNF-SAT là 3SAT hay 3-satisfiability.
Ví dụ: (x1 ∪ x2 ∪ ¬x6 ) ∩ (x3 ∪ ¬x5 ∪ ¬x7 ) ∩ (¬x1 ∪ x4 ∪
x6 ) ∩ (x2 ∪ x4 ∪ x3 )
1.2


3SAT thuộc lớp NP-Đầy đủ

Để chứng minh được 3SAT thuộc lớp NP-Đầy đủ, ta cần
chứng minh 2 điều như sau:
1. 3SAT thuộc lớp NP
2. 3SAT thuộc lớp NP khó
1.3

3SAT thuộc lớp NP

NP (nondeterministic polynomial time) là tập hợp các bài
toán quyết định mà trong trường hợp câu trả lời là ”có”,
tồn tại một chứng minh có độ dài đa thức có thể kiểm
chứng được trong thời gian đa thức bởi máy Turing tất
định.
Đối với bài toán 3SAT sau, ta tìm được lời giải để φ = 1
trong khoảng thời gian đa thức:
φ = (x1 ∪ x2 ∪ ¬x6 ) ∩ (x3 ∪ ¬x5 ∪ ¬x7 ) ∩ (¬x1 ∪ x4 ∪
x6 ) ∩ (x2 ∪ x4 ∪ x3 )
Với những giá trị từ x1 đến x7 , tồn tại được tập hợp giá
trị true false sao cho φ = 1 thì ta có thể xác định thời gian
9


đa thức của thuật toán.
Khi x1 , x2 , x5 , x4 = true , x3 , x6 , x7 = false. Ta có φ = 1,
từ đó ta có thể tìm được thời gian thực thi của φ theo
tham số độ dài của tập hợp x.
Vậy 3SAT thuộc lớp NP (∗)
1.4


3SAT thuộc lớp NP khó

Để chứng minh 3SAT thuộc lớp NP khó, ta cần thu giảm
một bài toán A nào đó về bài toán 3SAT. Ở đây, chúng ta
sẽ thu giảm từ CNF-SAT về 3SAT trong khoảng thời gian
đa thức.
Với C là biểu thức Boolean trong CNF. Ta biểu diễn sự
thay thế từng clause Ci trong C:

• if Ci = (a), ở đây, Ci có một hạng tử, hạng tử này
có thể là biến phủ định, sau khi ta thay thế Ci với
Si = (a∪b∪c)∩(a∪¬b∪c)∩(a∪b∪¬c)∩(a∪¬b∪¬c),
khi đó b và c là những biến mới không được sử dụng
ở bất kì nơi nào.
• if Ci = (a ∪ b), ở đây, Ci có hai hạng tử, sau khi ta
thay thế Ci với Si = (a ∪ b ∪ c) ∩ (a ∪ b ∪ ¬c), khi đó
c là biến mới không được sử dụng ở bất kì nơi nào.
• if Ci = (a ∪ b ∪ c), ở đây, Ci có ba hạng tử, ta đặt
Si = Ci
• if Ci = (a ∪ a2 ∪ a3 ∪ ... ∪ ak ), ở đây, Ci có k> 3 hạng
tử, sau khi ta thay thế Ci với Si = (a1 ∪ a2 ∪ b1 ) ∩
(¬b1 ∪ a3 ∪ b2 ) ∩ (¬b2 ∪ a4 ∪ b3 )...(¬bk−3 ∪ ak−1 ∪ ak ),
khi đó b1 , b2 , ..., bk là những biến mới không được sử
dụng ở bất kì nơi nào.
Để ý rằng giá trị được thừa nhận với những biến mới thêm
vào là hoàn toàn độc lập. Không vấn đề gì khi chúng ta
10



chỉ định hay thêm chúng vào, clause Ci là 1 khi và chỉ khi
các Si con cũng là 1. Do đó, clause C gốc là 1 khi và chỉ
khi S là 1. Hơn thế nữa, để ý rằng mỗi clause tăng kích
thước tối đa một cách liên tục và nhận ra rằng các toán
tử liên quan là các thay thế đơn giản.
Vì thế chúng ta có thể chỉ ra được cách thức làm sao
giảm một trường hợp của CNF-SAT thành một trường
hợp tương đương của 3SAT trong một khoảng thời gian
đa thức. (∗∗)
1.5

Kết luận

Từ (∗)(∗∗) Ta chứng minh được 3SAT thuộc lớp NP-Đầy
đủ.

2

Câu 2

2.1

Thu giảm Independent Set, k-Clique, Vertex Cover
cho nhau

2.2

Independent Set ≤P Vertex Cover và Vertex Cover ≤P
Independent Set


Trong đồ thị G = (V,E)
S là một Independent Set ⇔ (V - S) là một Vertex Cover.
1. Nếu S là một Independent Set, nếu không có cạnh e =
(u,v) nào trong G, sao cho cả u,v ∈ S. Do đó với bất kì
cạnh e = (u,v), tối thiểu chỉ có một u,v phải nằm trong
(V - S).
⇒ (V - S) là một vertex cover trong G.
2. Nếu (V - S) là một Vertex Cover, giữa bất kì cặp đỉnh
(u,v) nào thuộc S thì tồn tại một cạnh e, không phải các
điểm cuối của e sẽ tồn tại trong (V - S) vi phạm định nghĩa
của Vertex Cover. Do đó không có cặp đỉnh nào trong S
có thể kết nối một cạnh.
11


⇒ S là một Independent Set trong G.
Do đó G chứa một Independent Set kích thước k ⇔ G
chứa một Vertex Cover với kích thước |V | - k.
Vậy Independent Set ≤P Vertex Cover và Vertex Cover
≤P Independent Set.
2.3

Independent Set ≤P k-Clique và k-Clique ≤P Independent Set

1. Nếu có một Independent Set với kích thước k trong đồ
thị bù G , nó ngụ ý rằng không có hai đỉnh cùng share
nhau một cạnh trong G , nó cũng ngụ ý rằng tất cả các
đỉnh cùng share chung một cạnh với phần còn lại trong G
hình thành một clique. Đó là có sự tồn tại của một clique
với kích thước k trong G.

2. Nếu có một clique với kích thước k trong đồ thị G, nó
ngụ ý rằng tất cả các đỉnh share cùng một cạnh với phần
còn lại trong G, nó cũng ngụ ý rằng không có hai đỉnh
nào cùng share chung một cạnh trong G hình thành một
Independent Set. Đó là có sự tồn tại của Independent Set
với kích thước k trong G .
Từ đó suy ra được Independent Set ≤P k-Clique và kClique ≤P Independent Set.
2.4

Clique ≤P Vertex Cover và Vertex Cover ≤P Clique

Kết nối trường hợp clique x = (G,k) với trường hợp vertex
cover x = (¬G, |G.V | − k).

¬G là phần bù của G
C là một clique của G khi và chỉ khi G.V - C là một vertex
cover của ¬G
if C là một clique của G với kích thước size k, thì ¬G
không có cạnh trong C x C. vì thế G.V - C là một vertex
12


cover of ¬G với kích thước size |G.V| - k.
if G không có clique kích thước k, thì với bất kì tập hợp
đỉnh C với kích thước k nào, C không là một clique mà
nó ngụ ý là ¬G có một cạnh trong C x C, vì thế G.V - C
không là một vertex cover của ¬G.
Từ đó suy ra được Clique ≤P Vertex Cover và Vertex
Cover ≤P Clique.
2.5


Chứng minh Independent Set, k-Clique, Vertex Cover
là NP-Đầy đủ

2.6

Independent Set là NP-Đầy đủ

Để chứng minh Independent Set là NP-Đầy đủ cần chứng
mình 2 điều sau: Independent Set (IS) là NP và IS cũng
là NP Khó.

• NP: Để chứng minh IS ∈ NP, chúng ta phải chứng
minh rằng có một thuật toán thời gian đa thức mà
lấy một trường hợp của vấn đề và một chứng chỉ như
là các tham số, và xác minh rằng chứng chỉ là một
trường hợp có vấn đề đầu vào cụ thể. Như vậy, trường
hợp của chúng ta là một đồ thị không trọng số G, và
là một tập các đỉnh xác thực. Thuật toán của chúng
ta thực hiện 2 bước:
1. Kiểm tra rằng tất cả các đỉnh trong tập xác thực
là các đỉnh trong đồ thị.
2. Kiểm tra rằng không có cạnh giữa bất kỳ hai đỉnh
trong tập xác thực.
Thuật toán này chạy trong O(V + E), và rõ ràng nó
là khoảng thời gian đa thức. Vì thế IS ∈ NP. (*)

• NP-Khó: Để chứng minh IS ∈ NP-Khó, ta thu giảm
3SAT về IS.
13



⇒ Nếu công thức thỏa mãn, có ít nhất một đơn tử
true trong mỗi clause. S là một tập hợp của một trong
những đơn tử true từ clause.|S| =k và không có hai
nút trong S được kết nối bởi một cạnh.
⇒ Nếu đồ thị có một tập độc lập S có kích thước k,
chúng ta biết rằng nó có một nút từ mỗi "tam giác
mệnh đề". Đặt chúng là true. Điều này là có thể bởi
vì không có hai nút là sự phủ nhận của nhau.
Khi đồ thị có một independent set với kích thước k
khi và chỉ khi công thức thỏa mãn. Ta thu giảm được
3SAT về IS (**)

• Từ (*)(**) Vậy Independent Set thuộc lớp NP-Đầy
đủ.
2.7

Chứng minh k-Clique là NP-Đầy đủ

Hướng chứng minh:
1. k-Clique thuộc lớp NP
2. Cần chứng minh 3SAT ≤P k-Clique
3. k-Clique thuộc lớp NP-Đầy đủ
1. k-Clique thuộc NP.
Nghĩa là nếu tồn tại một đồ thị con đầy đủ (“giấy chứng
nhận”) thì giải thuật xác nhận hoặc bác bỏ giấy chứng
nhận phải thực hiện trong thời gian đa thức.Thật vậy, với
một đồ thị G = (V, E) cho trước và một “giấy chứng nhận“
là tập đỉnh con V’. Nếu V’ là đồ thị con đầy đủ thì V’ có

tối đa |V | đỉnh (|V |(|V2 |−1)) cạnh.
Do đó, thuật toán cần kiểm tra mỗi cặp đỉnh diễn ra tối đa
là O(|V |2 ). Thời gian này là đa thức. Vậy k-Clique thuộc
14


NP.
2. 3SAT ≤P k-Clique
Gọi công thức mệnh đề φ = C1 ∩ C2 ∩ ... ∩ Ck là công thức
dạng 3CNF-SAT có k mệnh đề (C). Mỗi mệnh đề Cr có 3
đơn tử phân biệt ở dạng l1r ∪ l2r ∪ l3r . Ta sẽ xây dựng đồ thị
G sao cho công thức mệnh đề φ khả thỏa mãn khi và chỉ
khi G có đồ thị con đầy đủ có k đỉnh. Quá trình xây dựng
đồ thị G (cần chỉ ra tập đỉnh V và tập cạnh E) như sau:
- Với mỗi mệnh đề Cr = l1r ∪ l2r ∪ l3r trong công thức mệnh
đề φ ta thêm vào V một bộ ba đỉnh tương ứng v1r ∪ v2r ∪ v3r .
Sau đó, ta thêm một cạnh giữa hai đỉnh vir ∪ vjs nếu thỏa
hai điều sau:

• vir ∪ vjs thuộc hai bộ ba khác nhau, tức là r khác s, và
• Hai đỉnh tương ứng với các đơn tử cùng tên trong hai
bộ ba phải nhất quán, nghĩa là không nối cạnh giữa
lir không là dạng phủ định của ljs
- Quá trình xây dựng G diễn ra trong thời gian đa thức
O(|V |∗|E|). Bởi vì, công thức mệnh đề φ có tối đa k mệnh
đề C nên đồ thị G có số đỉnh tối đa là V = 3k , và có tối
đa 3k(3k−1)
cạnh
2
Ví dụ: nếu


φ = (x1 ∪ ¬x2 ∪ ¬x3 ) ∩ (¬x1 ∪ x2 ∪ x3 ) ∩ (x1 ∪ x2 ∪ x3 )
thì đồ thị G là

15


Hình 1:

Ta còn cần chứng minh φ khả thỏa mãn khi và chỉ khi G
có đồ thị con đầy đủ có k đỉnh.

• Nếu φ khả thỏa mãn thì G có đồ thị con đầy
đủ có k đỉnh
Vì φ khả thỏa mãn nên tồn tại một bộ giá trị của các
đơn tử làm cho φ = 1
Nên mỗi mệnh đề Cr trong φ cũng phải bằng 1.
Suy ra Cr có ít nhất một đơn tử bằng 1, ta gọi đơn tử
đó là lir
Suy ra Do cách xây dựng các đỉnh của G, nên lir tương
ứng với vir trong G.
Với mỗi Cr trong φ chọn một đơn tử như thế
Suy ra Tập V’ có k đỉnh tương ứng
Ta thấy hai đỉnh bất kỳ vir và vjs (r khác s) trong V’ sẽ
tương ứng với các đơn tử lir và ljs (đã được gán bằng
1 trong, và hiển nhiên hai đơn tử này không trái dấu
16


nhau). Do đó, cạnh (vir , vjs ) ∈ E . Vậy G = (V ) là

một đồ thị con đầy đủ.

• Nếu G có đồ thị con đầy đủ có k đỉnh thi φ khả
thỏa mãn
Giả sử G có một đồ thị con đầy đủ G = (V , E ) có
k đỉnh.Trong một bộ ba đỉnh của G’ sẽ không tồn tại
cạnh nào.Do đó, G = (V , E ) chứa chính xác một
đỉnh trong mỗi bộ ba. Đơn tử lir ương ứng với vjs ∈ V
sẽ được gán bằng 1 (ta yên tâm là việc gán như thế
không xảy ra tình huống đơn tử lir và phủ định của
đơn tử đó ¬lir cùng bằng 1 vì G không chứa cạnh nối
giữa hai đơn tử trái dấu nhau).
Lúc này, mọi Cr trong φ đều bằng 1.
Vậy φ khả thỏa mãn.
Do đó, k-clique thuộc lớp NP-Khó.
Kết luận: k-clique thuộc NP-Đầy đủ.
2.8

Chứng minh Vertex Cover là NP-Đầy đủ

Hướng chứng minh:
1. Chúng ta đã biết 3SAT thuộc lớp NP-Đầy đủ
2. Cần chứng minh 3SAT ≤P Vertex Cover
3. Vertex Cover thuộc lớp NP-Đầy đủ
Chúng ta cần chứng minh thu giảm 3SAT về Vertex Cover
là đúng, nghĩa là một Vertex Cover kích thước k = m +
2l tồn tại khi và chỉ khi φ khả thỏa mãn. Giả sử chúng
ta có một biểu thức khả thỏa mãn φ. Với mỗi biến, thêm
nút tương ứng cho đơn tử true của Vertex Cover. Sau đó,
với mỗi clause, chọn 1 đơn tử true trong 1 clause và thêm

2 đơn tử còn lại vào Vertex Cover. Chúng ta sử dụng hai
17


đỉnh của mỗi clause tiện ích và 1 đỉnh trong mỗi biến tiện
ích để bao phủ. Mỗi cạnh trong biến tiện ích được bao phủ
bởi nút được chọn từ tiện ích đó. Tất cả ba cạnh trong
mỗi clause được bao phủ bởi 2 nút chúng ta chọn trong
clause gadget. Một đơn tử true trong mỗi clause gadget bị
bỏ ra ngoài, nhưng bởi vì nó là một đơn tử true, nó được
kết nối bởi một cạnh đến một nút tương ứng với đơn tử
true trong một biến clause. Vì thế những nút bao phủ tất
cả các cạnh của đồ thị và chúng ta có một Vertex Cover
có giá trị.
Chúng ta vẫn tiếp tục chứng minh hướng khác của ngụ
ý này. Nếu chúng ta có một Vertex Cover với kích thước
là k trong đồ thị G, nó phải chứa 1 nút trong mỗi biến
gadget và 2 nút trong mỗi clause gadget để bao phỉ các
cạnh trong gadget đó. Nó yêu cầu chính xác k = m+2l
nút. Giả sử chúng ta lấy đơn tử tương ứng cho 1 nút đã
được bao phủ trong 1 biến gadget là true. Thì sẽ làm khả
thỏa mãn φ bởi vì với mỗi clause gadget, mỗi 3 cạnh kết
nối clause gadget đến biến gadget được bao phủ, và chỉ
có 2 nút trong clause gadget là nằm trong bao phủ. Vì
thế một trong những clause-gadget cạnh phải được bao
phủ bởi 1 nút trong 1 biến gadget, và vì thế biểu thức
của đơn tử biến gadget được bao phủ đó mới true trong
φ sẽ khả thỏa mãn clause. Nó đúng với tất cả mọi clause
gadget và clause, vì thế biểu thức khả thỏa mãn φ. Dẫn
đến k-covering của đồ thị này tương ứng với sự khả thỏa

mãn của biểu thức với φ , khi một biểu thức khả thỏa mãn
trong φ tương ứng đến một k-covering của đồ thị này thì
sự thu giảm đúng.
Từ đó suy ra 3SAT ≤P Vertex Cover (**)
Mà 3SAT thuộc lớp NP-Đầy đủ (*)
Từ (*)(**) kết luận được Vertex Cover thuộc lớp NP-Đầy

18


đủ.

3

Câu 3: Chứng minh k-coloring thuộc lớp NP
đầy đủ

Cho đồ thị G và k màu, một chứng chỉ rằng câu trả lời
là có chỉ đơn giản là một k-coloring: Một có thể xác minh
trong thời gian đa thức mà hầu hết k màu sắc được sử
dụng, và rằng không có cặp nút được nối bởi một cạnh
nhận cùng màu.
Giống như các vấn đề khác trong phần này, 3-Coloring là
một vấn đề khó để liên quan đến một mức độ không sâu
sắc với các vấn đề NP-complete khác mà chúng ta đã thấy.
Vì thế một lần nữa, chúng ta sẽ đạt được tất cả các cách
trở lại 3-SAT. Cho 1 ví dụ 3-SAT, với các biến x1,. . . , xn
và các khoản C1,. . . , Ck, chúng ta sẽ giải quyết nó bằng
cách sử dụng một hộp màu đen cho 3-Coloring.
Sự bắt đầu của việc giảm là khá trực quan. Có lẽ sức mạnh

chính của 3 màu cho mã hóa biểu thức Boolean nằm trong
thực tế là chúng ta có thể liên kết các nút biểu đồ với các
thuật ngữ cụ thể, và bằng cách nối chúng với các cạnh đảm
bảo rằng chúng có được màu sắc khác nhau; điều này có
thể được sử dụng để thiết lập một sự thật và các sai khác.
Vì vậy với điều này trong tâm trí, chúng ta định nghĩa các
nút vi và vi tương ứng cho mỗi biến xi và sự phủ định của
nó xi. Chúng ta cũng xác định ba "nút đặc biệt" T, F, và
B, chúng ta gọi là True, False, và Base.
Để bắt đầu, chúng ta nối mỗi cặp nút vi, vi với nhau bằng
một cạnh, và chúng ta kết hợp cả hai nút này với Base.
(Điều này tạo thành một tam giác trên vi, vi, và Base, cho
mỗi i.) Chúng cũng tham gia True, False, và Base vào một
19


tam giác. Biểu đồ đơn giản G chúng ta đã định nghĩa cho
đến nay được mô tả trong hình 8.11, và nó đã có một số
tài sản hữu ích.

Hình 2: Hình 8.11

• Trong 3 màu của G, các nút vi và vi phải có các màu
khác nhau, và cả hai phải khác với Base.
• Trong 3 màu của G, các nút True, False và Base phải
có tất cả ba màu sắc trong một số hoán vị. Như vậy
chúng ta có thể tham khảo ba màu sắc là Màu True,
màu False, và màu Base, dựa trên những màu này ba
nút được màu sắc. Đặc biệt, điều này có nghĩa là với
mỗi i, một trong các vi hoặc vi có màu True, và màu

kia là màu False. Cho phần còn lại của công trình,
chúng ta sẽ xem xét biến xi được thiết lập để 1 trong
trường hợp được nêu ra của 3-SAT nếu và chỉ khi nút
vi được được giao màu True.
Vì vậy, trong bản tóm tắt, bây giờ chúng ta có một đồ thị
20


G, trong đó bất kỳ 3-coloring ngầm xác định sự phân bố
chân lý cho các biến trong ví dụ 3-SAT. Chúng tôi bây giờ
cần phải phát triển G để chỉ đáp ứng các bài tập có thể
được mở rộng để 3 màu của đồ thị đầy đủ.
Giống như các phép thu giảm 3-SAT khác, hãy xem xét
một mệnh đề như x1 v x2 v x3. Trong ngôn ngữ của 3 màu
của G, nó nói, Ít nhất một trong các nút v1, v2, hoặc v3
nên có được màu True. Vì vậy, những gì chúng ta cần là
một subgraph nhỏ mà chúng ta có thể cắm vào G, sao cho
bất kỳ màu 3 màu nào kéo dài vào subgraph này phải có
tài sản của việc gán màu True cho ít nhất một trong các
v1, v2 hoặc v3. Phải mất một số thử nghiệm để tìm một
subgraph, nhưng một trong những công trình được mô tả
trong hình 8.12.

Hình 3: Hình 8.12

Chuỗi phụ 6 nút này "gắn kết" với phần còn lại của G tại
năm nút hiện có: True, False, và những điều tương ứng
21



với ba điều khoản trong điều khoản mà chúng ta cố gắng
để đại diện (trong trường hợp này, v1, v2, và v3) Bây giờ
giả sử rằng trong một số 3- màu của G cả ba v1, v2 và v3
được gán màu False. Sau đó, hai nút bóng tối nhất trong
đồ thị phụ phải nhận được màu Base, ba các nút được
tô bóng trên chúng phải nhận được, tương ứng, các False,
Base, và True màu sắc, và do đó không có màu sắc nào có
thể được gán cho phần trên cùng được tô bóng nút. Nói
cách khác, một 3-coloring, trong đó không có v1, v2 hoặc
v3 nào được gán màu True không thể được mở rộng đến
một 3-coloring của subgraph này.
Cuối cùng, và ngược lại, một số kiểm tra tay các trường
hợp cho thấy rằng như như một trong các v1, v2 hoặc v3
được gán màu True, đồ thị con đầy đủ có thể là 3-colored.
Từ đó, chúng ta có thể hoàn thành việc xây dựng: Chúng
ta bắt đầu với được định nghĩa ở trên, và cho mỗi mệnh
đề trong ví dụ 3-SAT, chúng ta đính kèm một s subgraph
như thể hiện trong hình 8.12. Hãy gọi biểu đồ kết quả G’
Bây giờ chúng tayêu cầu bồi thường rằng trường hợp 3SAT đã cho là satisfiable nếu và chỉ khi G’ có 3-coloring.
Thứ nhất, giả sử rằng có một sự phân công thỏa mãn cho
trường hợp 3-SAT. Chúng ta xác định màu của G’ bằng
màu cơ bản đầu tiên, True, và False tùy ý với ba màu sắc,
sau đó, đối với mỗi i, gán vi the True màu nếu xi = 1 và
màu False nếu xi = 0. Sau đó chúng ta gán cho vi chỉ có
sẵn màu. Cuối cùng, như đã nói ở trên, bây giờ có thể mở
rộng 3-coloring này thành mỗi subgraph sáu nút, kết quả
là một 3-coloring của tất cả các G’
Ngược lại, giả sử G’ có 3-coloring. Trong màu này, mỗi nút
vi được gán màu True hoặc màu False; chúng ta đặt biến
xi tương ứng. Bây giờ chúng tôi tuyên bố rằng trong mỗi

22


khoản của trường hợp 3-SAT, tại ít nhất một trong các
điều kiện trong mệnh đề có giá trị sự thật 1. Nếu không,
thì tất cả ba trong số các nút tương ứng có màu False trong
3 màu của G’ và, như chúng ta đã thấy ở trên, không có
3-coloring của khoảng tương ứng subgraph phù hợp với
điều này - mâu thuẫn.
Khi k> 3, rất dễ dàng để giảm vấn đề 3-coloring cho kColoring. Về cơ bản, tất cả những gì chúng ta làm là lấy
một ví dụ của 3-Coloring, đại diện bởi một biểu đồ G,
thêm k - 3 nút mới, và nối các nút mới với nhau và để mỗi
nút trong G. Biểu đồ kết quả là k-colorable nếu và chỉ khi
bản gốc đồ thị G có 3-coloring. Do đó k-Coloring cho bất
kỳ k> 3 cũng là NP-complete.

23


4
4.1

Câu 4
Câu 4a: Mã giả giải thuật tô màu tham lam

function tomauthamlam(Array<Vertex> listVertex)
Sắp xếp listVertex theo bậc giảm dần
while(listVertex.size khác 0)
tô màu đỉnh đầu của listVertex, gọi là v
color = 1;

while(true)
if(các đỉnh kề của đỉnh đang tô khác với color)
tô đỉnh v màu color
xóa đỉnh v ra khỏi listVertex
break
else color = color + 1
end
end
4.2

Câu 4b: Đề xuất giải thuật ngẫu nhiên cho tô màu

Thuật toán Monte-Carlo sẽ tìm được giá trị "đúng" nhưng
sẽ mất một khoảng thời gian r = ∞ để tìm được kết quả
đúng. Nên chúng ta tìm một kết quả xấp xỉ gần đúng với
kết quả t r. Giả sử mincoloring = tất cả các ca thi trong
tuần.
Trong trường hợp này, chúng ta sẽ quy bài toán tìm số
màu nhỏ nhất thành bài toán chọn lựa. Nếu giải thuật
Monte-Carlo cho đáp án sai , chúng ta cần phải thay đổi
giá trị ti = t + ∆ và giảm mincoloring = mincoloring − 1 để
giải thuật trên không sai.
Lặp lại khoảng thời gian t lần (thời gian chạy độc lập tuyến
tính) và đến khi giải thuật cho ra kết quả "true". Nếu kết
24


quả bằng "true" phải đảm bảo thoả điều kiện sau:

3 ≤ mincoloring ≤ số lượng ca thi diễn ra. Thiết kế giải

thuật:
Lặp lại ek lần và đảm bảo tất cả các đỉnh đã được tô màu,
c: V → {1, 2, 3, ..., k}. Định nghĩa: Gọi đường đi tô màu
nếu mỗi đỉnh có được tô màu khác các đỉnh kề với nó. Một
ví dụ đơn giản:
• Chọn ngẫu nhiên một đỉnh c được tô màu trong G, c:
→ V → [k]
• Gọi p là đường đi dài nhất của G
• Nếu |p| ≥ k − 1, xuất ra kết quả.
Thời gian chạy: ek có bước lặp O(2k ∗ E ). Tổng cộng
O((2e)k ∗ E ). Kết quả chỉ đúng nếu xác suất trên đường
đi p = k-1 thì số màu tối thiểu cần tô là 1/ek và nhiều
nhất là 1 − 1/ek . Vậy nên quá trình lặp lại ek lần sẽ cho
ra kết quả sai số tối đa là 1/e.

25