ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN:
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT
VẤN ĐỀ
ĐỀ TÀI:
PHÂN TÍCH, THIẾT KẾ, CẢI TIẾN VÀ MINH HỌA
THUẬT TOÁN TÔ MÀU ĐỒ THỊ
Ging viên phụ trách: PGS. TS. ĐỖ VĂN NHƠN
Học viên thực hiện: LÂM HÀN VŨ
Mã học viên: CH1301119
TP. HỒ CHÍ MINH, THÁNG 10/2014
MỤC LỤC
Trang 3
LỜI NÓI ĐẦU
Để có thể hoàn thành tốt bài báo cáo, trước tiên tôi gởi lời
chân thành cảm ơn đến PGS. TS. Đỗ Văn Nhơn đã tận tình giảng
dạy và giúp đỡ trong thời gian thực hiện bài tiểu luận.
Xin gửi lời cảm ơn đến gia đình, cảm ơn các anh chị, bạn bè,
những người luôn sát cánh, động viên tôi trên bước đường học tập
cũng như trong cuộc sống. Xin chân thành biết ơn sự tận tình dạy
dỗ và sự giúp đỡ của tất cả quý thầy cô tại trường Đại học Công
Nghệ Thông Tin, đặc biệt là các thầy cô trong khoa Khoa học Máy
tính, cảm ơn các thầy cô thuộc bộ phận quản trị thiết bị đã tạo
điều kiện thuận lợi về mặt tinh thần, điều kiện học tập trong quá
trình học tập môn học. Tất cả các kiến thức mà nhà trường và quý
thầy cô đã truyền đạt là hành trang to lớn để tôi mang theo trên
con đường học tập, làm việc và nghiên cứu cũng như trong quá
trình hoàn thiện nhân cách của mình.
TP. HCM, ngày 10 tháng 10 năm 2014
Học viên

thì phần tử M
i,j
bằng 1, nếu
không, nó có giá trị 0. Cấu trúc này tạo thuận lợi cho việc tìm các đồ thị con và để
đo các đồ thị.
Adjacency matrix
Biểu diễn đồ thị bằng ma trận kề
- Danh sách kề (Adjacency list) - Mỗi đỉnh của đồ thị có một danh sách các đỉnh kề
nó (nghĩa là có một cạnh nối từ đỉnh này đến mỗi đỉnh đó). Trong đồ thị vô hướng,
cấu trúc này có thể gây trùng lặp. Chẳng hạn nếu đỉnh 3 nằm trong danh sách của
đỉnh 2 thì đỉnh 2 cũng phi có trong danh sách của đỉnh 3. Lập trình viên có thể
chọn cách sử dụng phần không gian thừa, hoặc có thể liệt kê các quan hệ kề cạnh
chỉ một lần. Biểu diễn dữ liệu này thuận lợi cho việc từ một đỉnh duy nhất tìm mọi
đỉnh được nối với nó, do các đỉnh này đã được liệt kê tường minh.
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 6
Biểu diễn đồ thị trên sử dụng danh sách kề
a adjacent to b,c
b adjacent to a,c
c adjacent to a,b
Biểu diễn đồ thị bằng dăn sách kề
2. BÀI TOÁN TÔ MÀU ĐỒ THỊ
Tô màu đồ thị bắt nguồn từ bài toán tô màu các quốc gia trên
một bản đồ sao cho không có hai quốc gia nào chung đường biên
giới được tô cùng màu. Nếu chúng ta xem các quốc gia như các
điểm trên mặt phẳng, và vẽ một cạnh kết nối giữa hai cặp đỉnh
tương ứng của hai quốc gia nào có chung đường biên giới, thì ta
thu được một đồ thị phẳng.
Năm 1852, giả thuyết 4 màu được đề cập lần đầu tiên bởi một
người Anh Francis Guthrie. Trong khi tô màu bản đồ cho các vùng

công việc. Các công việc có thể được lập lịch theo bất kì thứ tự nào,
nhưng những cặp công việc đụng độ nhau cần phải được sắp vào những
slot thời gian khác nhau. Sự đụng độ ở đây có thể do cả hai cùng phải sử
dụng một tài nguyên không thể chia sẽ nào đó. Việc lập lịch cần đảm
bảo thời gian để hoàn thành tất cả các công việc ngắn nhất (dùng ít slot
thời gian nhất).
Đồ thị tương ứng để giải quyết bài toán lập lịch được phát biểu
như trên là đồ thị gồm tập các đỉnh là các công việc cần lập lịch. Hai
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 8
đỉnh tương ứng với hai công việc có đụng độ với nhau thì được nối với
nhau bằng 1 cạnh. Sắc số của đồ thị (sẽ được trình bày ở phần II) cũng
tương ứng chính là thời gian tối ưu (số slot thời gian nhỏ nhất) để giải
quyết toàn bộ công việc mà không xảy ra bất kì sự đụng độ nào.
3.2. Register Allocation
Việc đưa các biến số thường dùng vào thanh ghi, một bộ nhớ dung
lượng nhỏ và rất nhanh được sử dụng để tăng tốc độ xử lí của các
chương trình máy tính bằng cách cung cấp các truy cập trực tiếp đến
các giá trị cần dùng, là một trong những hoạt động then chốt làm tăng
tốc độ của chương trình. Việc này có tên là Register Allocation và thường
được thực hiện bởi một trình biên dịch trong giai đoạn phát sinh mã hóa.
Yêu cầu đặt ra là số lượng các biến cần dùng đến, cần được lưu vào
thanh ghi có thể rất lớn và số lượng thanh ghi trong máy tính thì hạn
chế, ta cần tiết kiệm số thanh ghi tới mức tối đa có thể.
Vấn đề Register Allocation được giải quyết như sau : trình biên
dịch xây dựng một đồ thị mà ở đó, các đỉnh của đồ thị là kí hiệu của các
than ghi và cạnh nối giữa 2 nodes nếu chúng cùng lúc cần dùng đến.
Nếu đồ thị có thể được tô chỉ với k màu thì các biến có thể chỉ cần lưu
trữ trong k thanh ghi.
3.3. Sắp lịch thi, sắp thời khóa biểu

o Bài toán tô màu đỉnh trở nên tối ưu khi số màu được sử
dụng để tô các đỉnh trong V của đồ thị G là ít nhất.
o Số màu ít nhất có thể tô hoàn chỉnh đồ thị G được gọi là
chromatic number - sắc số , kí hiệu: X(G)
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 10
o Bài toán tô k màu lên 1 đồ thị được gọi là bài toán k-
coloring. Bài toán được gọi là k-chromatic nếu k =
X(G).
Ví dụ:
Cho đồ thị G(V,G) như sau:
Với k = 3. Bài toán k-coloring được thực hiện cho kết quả:
Tuy nhiên, sắc số của đồ thị G là X(G) = 2 nếu như ta tô màu như
sau:
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 11
Như vậy, kếu k=X(G) = 2, bài toán được gọi là k-chromatic.
2.2. Đa thức màu (Chromatic Polynomial)
Trong lý thuyết đồ thị, Đa thức màu (tiếng Anh: Chromatic
polynomial) của một đồ thị biểu diễn số cách tô màu các đỉnh của
đồ thị đó theo số màu. Đa thức màu là đối tượng nghiên cứu của lý
thuyết đại số đồ thị, một nhánh của toán học.
Đa thức màu được đề xuất bởi Geogre David Birkho‰ trong
một nỗ lực của ông nhằm giải quyết bài toán định lý bốn màu.
Định lý của Geogre David Birkho‰ được phát biểu như sau :
− Mọi đồ thị phẳng G đều có sắc số không lớn hơn 4, nếu
với mọi G, trong đó P(G,k) xác định số cách tô
màu đỉnh G bởi k màu.
− Giá trị của đa thức màu của đồ thị G tại k bằng số cách tô màu
đỉnh đồ thị G với k màu. Đa thức màu thường được kí hiệu là ,

Đồ thị chu
trình C
n
Đồ thị
Perdesen
2.3. Tô màu cạnh
− Bài toán tô màu cạnh của 1 đồ thị là phương pháp tô màu
cho riêng từng cạnh của đồ thị, sao cho ở bất kì đỉnh nào
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 13
trên đồ thị, các cạnh nối đến đỉnh đó phải có màu khác
nhau.
− Bài toán tô màu cạnh với k màu được gọi là bài toán k-
edge-coloring.
− Đồ thị được tô hoàn chỉnh sử dụng ít màu nhất được gọi là
chromatic index, hay edge chromatic number.
2.4. Tô màu toàn bộ
Phương pháp tô màu toàn bộ là sự kết hợp vừa tô màu đỉnh, vừa tô
màu cạnh. Nghĩa là đồ thị gồm các đỉnh và cạnh sau khi tô màu
thỏa mãn 2 tính chất:
− Bất kì 2 đỉnh có chung cạnh không trùng màu với nhau.
− Bất kì các cạnh có chung đỉnh không trùng màu với nhau.
2.5. Các tính chất
Đồ thị phẳng: Đồ thị vô hướng G được gọi là đồ thị phẳng nếu
ta có thể biểu diễn nó trên một mặt phẳng sao cho không có cạnh
nào cắt nhau.
Các đồ thị không phẳng nổi tiếng:
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 14
Đồ thị k5- đồ thị đầy đủ Đồ thị K

nhưng điều ngược lại chưa chắc đã đúng.
− Chỉ số clique (clique number) của đồ thị G là số đỉnh của clique lớn
nhất trong G. Chỉ số clique của đồ thị G được ký hiệu là ω(G).
3 đỉnh AA,BB,CC tạo thành 1 clique. Đồ thị trên có nhiều clique lớn nhất
với chỉ số là 3.
III. THIẾT KẾ THUẬT TOÁN
1. Phương pháp vét cạn
Phương pháp vét cạn thường được sử dụng trong tô màu đồ thị để
thử tất cả các khả năng có thể, nghĩa là đầu tiên thử tiến hành tô màu
đồ thị bằng 1 màu, 2 màu, 3 màu, cho đến khi tìm ra phương pháp
thỏa mãn yêu cầu, đây là phương pháp tối ưu nhất để tìm ra cách tô có
số màu sử dụng bằng với sắc số của đồ thị.
Ta thiết kế thuật toán vét cạn dựa theo nguyên tắc số màu tăng
dần như sau: Lưu trữ các màu đã tô của mỗi đỉnh trong đồ thị bằng cấu
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 16
trúc cây, mỗi đỉnh trong đồ thị là 1 bậc của cây, đỉnh cuối cùng của đồ
thị sẽ là nút lá trong cây.
Giải thuật:
Treenode treecolor = Root // Cây dùng lưu trữ màu của các đỉnh;
Hàm tô màu :
// V: đỉnh đang xét, Colors: tập màu có thể tô được trên đỉnh
đó
bool Coloring(V, Colors, treecolor)
success = true;
1. foreach C in Colors
1.1 Tô màu C cho V
1.2 Thêm V đã được tô màu vào 1 nhánh của
treecolor
2. Nếu V là đỉnh cuối cùng trong tập các đỉnh của đồ thị

, như vậy, thuật toán vét cạn có độ phức
tạp O(2
n
).
Phương pháp vét cạn đưa ra kết quả tốt nhất, nó có vẻ rất thích
hợp với các đồ thị nhỏ, tuy nhiên đối với các đồ thị phức tạp thì sẽ tiêu
tốn rất nhiều thời gian thực hiện cũng như tài nguyên hệ thống. Do đó,
để giải quyết các bài toán đồ thị phức tạp, ta có thể tiếp cận vấn đề
theo hướng cố gắng tìm ra một giải pháp tốt, không nhất thiết là giải
pháp tối ưu.
2. Phương pháp tham lam
Có rất nhiều giải pháp được đưa ra nhằm giải quyết bài toán tô màu đồ
thị với số đỉnh lớn và có độ phức tạp hợp lý hơn so với phương pháp vét
cạn. Một trong những giải pháp được sử dụng nhiều nhất đó là áp dụng
phương pháp tham lam.
Thuật toán được trình bày như sau:
Begin
1. Colors = null; // tập màu dùng tô các đỉnh.
2. for i =1 to n do // cho i chạy từ đầu đến cuối
tập đỉnh của G
2.2 Nếu Colors khác NULL ==> Tô màu đầu tiên không
xung đột cho v
i
2.3 Nếu Colors == NULL ==> Thêm 1 màu mới vào
Colors, tô màu đó cho v
i
End.
Ví dụ :
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 18

nhiên, sau khi tô màu cho 1 đỉnh, ta tạm thời loại bỏ đỉnh đó ra khỏi đồ
thị và tiếp tục thực hiện với các đỉnh tiếp theo.
Cải tiến giải thuật tham lam: Với giải thuật tham lam cải tiến, còn
được gọi là phương pháp Largest Degree First, các đỉnh được sắp
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 21
xếp theo bậc từ cao xuống thấp, quá trình tô màu được thực hiện
bằng cách chọn đỉnh có bậc cao nhất, gán cho màu được tô ít nhất
không xung đột.
Với giải thuật này, số màu sử dụng để tô đồ thị sẽ ít hơn so với giải
thuật tham lam ban đầu, tuy nhiên độ phức tạp cao hơn do tốn chi
phí sắp xếp các đỉnh và tính bậc các đỉnh của đồ thị, nhưng vẫn ở
mức chấp nhận được.
IV. PHÂN TÍCH THUẬT TOÁN
Sử dụng phương pháp vét cạn cho đồ thị chắc chắn sẽ cho
được một lời giải tối ưu, tuy nhiên, ta phải trả một giá khá đắt bởi
độ phức tạp cao của phương pháp này. Thực tế cho thấy, phương
pháp vét cạn cho tô màu đồ thị chỉ phù hợp cho những đồ thị đơn
giải với kích thước nhỏ. Một phương pháp khá quen thuộc và hiệu
quả là phương pháp tham lam. Chúng tôi sử dụng phương pháp
tham lam cùng một số heuristic để giải quyết bài toán.
Giải thuật tha lam cho bài toán tô màu đô thị xem xét các
đỉnh theo một thứ tự cụ thể và tô cho một màu x trong tập những
màu sẵn có sao cho x chưa được tô cho bất cứ đỉnh kề nào của ;
trong trường hợp tất cả những màu sẵn có đề được các đỉnh kề của
sử dụng, ta tô bằng một màu mới. Mức độ tối ưu của việc tô màu
phụ thuộc vào chiến lược lựa chọn sắp xếp thứ tự cho các đỉnh.
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ
Trang 22
Giải thuật tô màu đồ thị theo phương pháp tham lam cho kết quả khác

Lập danh sách các đỉnh của đồ thị E’ = [v1, v2, ,vn];
Bước 1 :
If(E’ = {} or k = n) then Stop, đồ thị được tô bằng i
màu.
Else
Sắp xếp E’ theo thứ tự bậc giảm dần : degree(v1)
degree(v2) … degree(vn)
Bước 2 :
S := đỉnh đầu tiên trong danh sách;
n:=n+1;
For(int j:=0; j< i; j++)
if( màu j chưa được dùng bởi bất kì đỉnh nào kề S)
then
{
tô màu j cho S;
IsColored(S) := true;
}
Bước 4 :
If( !IsColored(S)) then
{
i := i + 1;
tô màu i cho S;
IsColored(S) := true;
}
Bước 5 :
Degree[S] = -1;
Foreach(Node node in Kề(S)]
Degree[node]:= Degree[node] – 1;
Quay lại Bước 1;
VI. ĐÁNH GIÁ & CHỨNG MINH THUẬT TOÁN

+ Không cho lời giải tối ưu trong mọi trường hợp, nhưng
lời giải tốt và có thể chấp nhận được.
+ Tốc độ thực hiện nhanh chóng.
+ Là sự kết hợp giữa phương pháp tham lam và quy tắc
heuristic (Largest degree ¨ll recursive).
VII. CÀI ĐẶT CHƯƠNG TRÌNH
Sử dụng thuật toán tô màu đồ thị đã được trình bày ở mục
(III) để xây dựng chương trình.
1. Nền tảng công nghệ:
Chương trình giải bài toán tô màu đồ thị được xây dựng chủ
yếu sử dụng:
− Ngôn ngữ lập trình C#
− IDE lập trình Microsoft Visual Sutdio 2012
− Microsoft XNA 3.1
Chương trình được xây dựng trên nền tảng Microsoft XNA
Framework 3.1 nên ta cần cài đặt thêm Microsoft XNA Framework
Redistributable 3.1 mới có thể chạy được chương trình. Ta có thể
download gói này ở địa chỉ sau: http://www.microsoft.com/en-
us/download/details.aspx?id=15163.
2. Giao diện chương trình
Giao diện chương trình gồm:
• Biểu diễn đồ thị vô hướng đọc từ ¨le input.txt. Đồ thị gồm các
node và cạnh nối giữa chúng. Mỗi node có thông tin: tên
node và bậc của node. Mặt định, tất cả các node trong đồ thị
được tô chung một màu.
GVHD: PGS. TS. Đỗ Văn Nhơn Học viên: Lâm Hàn Vũ