Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
BÀI TẬP LỚN
THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN
ĐỀ TÀI 15: BÀI TOÁN TÔ MẦU ĐỒ THỊ

Giáo viên hướng dẫn: PGS. NGUYỄN ĐỨC NGHĨA
Sinh viên thực hiện :
1. Nguyễn Thị Thanh Vi
20073430
CNPM K52
2. Ngô Văn Vĩ 20073500 CNPM K52
3. Nhâm Ngọc Trung 20073050 CNPM K52
Hà Nội, 12/2010
1 | P a g e
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
MỤC LỤC
MỤC LỤC 2
2.4. Ứng dụng 6
2.1. Đọc dữ liệu từ file 35
2.2. Dữ liệu vào từ bàn phím 47
PHỤ LỤC 1: DANH MỤC CÁC HÌNH ẢNH TRONG TÀI LIỆU 62
I. GIỚI THIỆU BÀI TOÁN
1. Tổng quan về đồ thị
1.1. Đồ thị và các cách biểu diễn đồ thị
Đồ thị là gì
Một cách không chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối
với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thường được vẽ
dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạnh).
Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị.

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.
The graph pictured above has this
adjacency list representation:
a adjacent to b,c
b adjacent to a,c
c adjacent to a,b
1.2. Các bài toán điển hình
- Bài toán tập con độc lập
- Bài toán tô mầu đồ thị
- Bài toán tìm đường đi ngắn nhất
- Bài toán luồng cực đại
- Bài toán phủ tối thiểu
- Kiểm tra tính liên thông của đồ thị
- Duyệt đồ thị
- …
2. Bài toán tô mầu đồ thị
Tô màu đồ thị và sự tổng quát của nó là công cụ hữu dụng trong việc mô hình hóa rất nhiều bài
toán khác nhau trong vấn đề xếp lịch, xây dựng chương trình và vấn đề phân công công việc. Bài
toán tô màu đồ thị bao gồm nhiều loại: tô màu đỉnh đồ thị (vertex graph coloring) , tô màu cạnh
đồ thị (edge graph coloring)
2.1. Bài toán tô mầu cạnh
Bài toán
Cho G=(V,E) là đơn đồ thị vô hướng ( G không là đồ thị khuyên) , hãy tìm cách gán (tô màu)
cho mỗi cạnh của đồ thị một màu sao cho hai cạnh có cùng chung 1 đỉnh không bị tô bởi cùng
một màu. Một phép gán màu cho các cạnh như vậy gọi là một phép tô màu cạnh đồ thị. Nói cách
khác, phép tô cạnh đồ thị bởi k màu nói trên có thể được hiểu là một phân hoạch của tập cạnh E
của G thành k tập con (tương ứng với k màu) sao cho mỗi tập con ứng với một màu i nhất định.
Bài toán đặt ra là tìm cách tô màu nào sử dụng số màu ít nhất có thể.
4 | P a g e

màu khác nhau.Khi đó nếu gọi ∆ là giá trị lớn nhất trong tập bậc của đỉnh v ( ∆=maxdeg(v) ) thì
hiển nhiên:
Χ’(G) ≥ ∆
Từ nhận xét trên cộng với tính chất 3 của sắc số cạnh χ′(G) ta suy ra được nhận xét sau:
(
Công thức trên cũng là công thức biểu diễn của định lý Vizing mà chúng ta sẽ phát biểu dưới
đây.
Định lý Vizing :
Bất kì một đơn đồ thị G nào cũng có số : χ’(G) thỏa mãn χ’(G)=∆ hoặc χ’=∆+1
Chứng minh: Vì chúng ta chỉ quan tâm đến nội dung của các định lý, lấy cơ sở cho việc xây
dựng thuật toán giải quyết bài toán tô màu cạnh đồ thị. Do đó trong báo cáo này, tất cả những
phần chứng minh các định lý các bổ để sẽ được trình bày ở phần phụ phía cuối báo cáo.
Đến đây, chúng ta đã biết được sắc số cạnh của một đơn đồ thị biến thiên trong khoảng [Δ(G),
Δ(G) +1] . Bài toán tô màu cạnh đồ thị đặt ra yêu cầu phải xác định một cách tô màu với số màu
ít nhất có thể để tô màu tất cả các cạnh của đồ thị. Vậy trong hệ bất đẳng thức (1) khi nào bất
đẳng thức bên trái xảy ra dấu bằng.
Định lý 1: Nếu G là đồ thị 2 phía thì χ’(G) = ∆
2.4. Ứng dụng
- Bài toán lập lịch:
6 | P a g e
Δ(G)≤ χ′(G) ≤ Δ(G) + 1
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
Ở đây nhóm xin đưa ra một ví dụ cụ thể là bài toán lập lịch thi: hãy lập lịch thi trong một trường
đại học sao cho không có sinh viên nào thi hai môn cùng một lúc
Giải pháp:
Biểu diễn bằng đồ thị với:
• Mỗi môn học là một đỉnh
• Nếu hai môn học nào được dự thi bởi cùng 1 sinh viên thì sẽ nối bằng 1 cạnh
• Các lập lịch sẽ tương ứng với bài toán tô mầu của đồ thị này: số các mầu được tô là số
các đợt thi, các đỉnh có cùng mầu sẽ thi cùng 1 đợt.

- Một đồ thị đơn giản G với n đỉnh bao gồm một tập các đỉnh V,với | V |= n, và một bộ các
cạnh E, sao cho mỗi cạnh là một cặp không có thứ tự của các đỉnh khác nhau. Lưu ý rằng
định nghĩa của G rõ ràng cấm các vòng lặp(cạnh nối một đỉnh với chính nó) và các cạnh
đa (nhiều cạnh tham gia một cặp đỉnh), khi thiết lập E cũng phải được giới hạn. Chúng tôi có
thể gán nhãn các đỉnh của G với 1 số nguyên, 2, , n.
- Nếu các cặp không có thứ tự của các đỉnh {u, v} là một cạnh trong G, chúng ta nói u đó là
một lân cận của v (hoặc u kề với v) và viết uv ∈ E. Lân cận đối xứng rõ ràng là một mối quan
hệ: uv ∈ E nếu và chỉ nếu vu ∈ E .
- Bậc của một đỉnh v, ký hiệu là d (v), là số lân cận của v. Số bậc tối đa của tất cả các đỉnh
của G được ký hiệu là Δ.
- Các ma trận kề của G là một ma trận n × n với các mục trong hàng u và cột v bằng 1
nếu uv ∈ E và bằng 0 nếu ngược lại.
- Cho đồ thị G và H, tích đề các G × H được định nghĩa là các đồ thị mà tập các đỉnh là V
(G) × V (H)với một cạnh đang kết nối đỉnh (u
1,
v
1)
với đỉnh (u
2,
v
2)
nếu và chỉ nếu hoặc
u
1
= u
2
và {v
1,
v
2}

vấn đề thực sự hữu ích trong thực tế. Các lớp của tất cả các vấn đề như vậy có thuật toán thời
gian đa thức được ký hiệu là P. Đối với một số vấn đề, không có thuật toán thời gian đa thức
được biết đến, nhưng những vấn đề này có thuật toán thời gian đa thức bất định: hãy thử tất
cả các ứng viên cho các giải pháp cùng một lúc và cho mỗi ứng viên nhất định, xác minh
xem đó là một giải pháp chính xác trong thời gian đa thức.
1.2. Thuật toán
Nhóm bắt đầu với tích Đề Các cho phép chúng ta chuyển đổi các vấn đề của việc tìm kiếm một
tập m-màu của các đỉnh n của một đồ thị tương đương như việc tìm kiếm một bộ độc lập kích
thước n trong tích đề các G × K
m .
- Tích Đề Các
Một đơn đồ thị G với n đỉnh là tô được bằng m mầu khi và chỉ khi tích đề các G × K
m
có một tập
độc lập kích thước n.
Chứng minh.
Giả sử có một tập m-màu của các đỉnh của G. Xác định một tập con S của các đỉnh của tích đề
các G × K
m
như sau. Một đỉnh (u, v) của G × K
m
thuộc S nếu và chỉ nếu đỉnh u của G được giao
màu v đối với tập m màu thích hợp. Vì mỗi đỉnh của G được giao một màu duy nhất, | S | = n.
Bây giờ chúng ta sẽ chỉ ra rằng S là một tập độc lập. Cho (u
1,
v
1)
và (u
2,
v

= v
2,
từ mỗi đỉnh
trong G đượcgiao một màu duy nhất. Nhưng sau đó {v
1,
v
1}
không thể là một cạnh
trong K
m
khi K
m
là một đơn đồ thị (mâu thuẫn).
• {U
1,
u
2}
là một cạnh trong G, và v
1
= v
2.
Nhưng điều này vi phạm các định nghĩa của
một tập m màu của G từ đỉnh kề phải được giao các màu khác nhau (mâu thuẫn).
Vì vậy không thể có một cạnh giữa hai đỉnh trong S và S phải là một tập độc lập.
Ngược lại, giả sử có một tập độc lập S kích thước n trong tích đề các G × K
m
. Chúng ta sẽ chỉ ra
rằng G có m màu riêng biệt. Nếu m lớn hơn hoặc bằng n thì G có thể được m màu một cách tầm
thường , do đó giả sử m nhỏ hơn n. Sự phân chia các đỉnh của S vào nhiều nhất là m lớp tương
đương C

và C'
j
thì (u, v
i)
thuộcC
i
và (u,
v
j)
thuộc C
j.
Khi K
m
đầy đủ, {v
i,
v
k}
là một cạnh trong K
m,
do đó, {(u, v
i),
(u, v
j)}
là một
cạnh trong tích đề các G ×K
m
. Điều này mâu thuẫn với thực tế là S là một tập độc lập .Vì
vậy, các bộ C
'1,
C'

2,
v
2),
, (u
2

i (2),
v
2)
o
o (U
m

1,
v
m),
(u
m

2,
v
m),
, (u
m

i (m), m
v)
Nếu một số u
i


i

j
xuất hiện trong danh sách là
riêng biệt và từ | S | = n , có n u
i

j i
phân biệt mọi đỉnh của G được chứa trong một số
lớp tương đương 'C Do đó,
Chỉ định màu i đến đỉnh u của G nếu u thuộc về các lớp tương đương C
i
' . Điều này tạo ra một
tập m-màu của các đỉnh của G.
Bây giờ chúng ta định nghĩa hai thủ tục để thực hiện với tập độc lập trong tích đề các G × K
m
.
- Thủ tục 1
Với một tập độc lập S của tích đề các G×K
m
nếu S không có đỉnh có thể thêm, đầu ra S. Ngược
lại, cho mỗi đỉnh có thể thêm (u, v) của S, tìm số ρ (S∪ {(u, v)}) của đỉnh có thể thêm của tập độc
lập S ∪ {(u, v)}. Cho (u,v )
max
biểu thị một đỉnh có thể thêm sao cho ρ (S ∪ {(u, v)
max})
là lớn
nhất và chứa tập độc lập S ∪ {(u, v)
max}
. Lặp lại cho đến khi tập độc lập không có đỉnh có thể

trong S
1.
Xác định S
(u
1
, v
1
), (u
2
, v
2
)
bằng cách thêm (u
1
, v
1
) vào S và bỏ (u
2,
v
2)
từ S. Thực hiện thủ tục 3.1 trên S
(u
1,
v
1),
(u
2,
v
2)
và đầu

j)}.
o Thực hiện thủ tục 3.1 trên S
i, j.
o Đối với r = 1, 2, , n thực hiện thủ tục 3.2 lặp lại r lần.
o Kết quả là một tập độc lập tối đa S
i, j.
• Phần II. Với mỗi cặp tập độc lập tối đa S
i, j,
S
k, l
tìm thấy trong phần I
o Khởi tạo S đặt độc lập
i, j, k, l
= S
i, j
∩ S
k, l.
o Thực hiện thủ tục 3,1 trên S
i, j, k, l.
o Đối với r = 1, 2, , n thực hiện thủ tục 3,2 lần r lặp đi lặp lại.
o Kết quả là một tập độc lập tối đa S
i, j, k, l.
• Phần III. Nếu một tập độc lập S với kích thước n đã được tìm thấy tại bất kỳ giai
đoạn của phần I hoặc phần II, đầu ra S như là một tập m-màu của các đỉnh
của G theo Bổ đề Đề các. Ngược lại, kết luận thuật toán không thể tìm thấy bất kỳ
tương ứng m-màu của các đỉnh của G.
1.3. Ví dụ
Chúng ta thể hiện các bước của thuật toán bằng một ví dụ nhỏ. Đồ thị đầu vào được thể hiện
dưới đây trong hình 3.1 với n = 4 đỉnh có nhãn V = {1, 2, 3, 4}. Các thuật toán tìm kiếm cho một
tương ứng 3- màu của các đỉnh bằng cách sử dụng các thiết lập của các màu {1, 2, 3} đại diện

Đỉnh có thể thêm
của S
1,1
∪{(u, v)}
ρ
(1,1
S ∪ {(u, v)})
(2, 2) (3, 3), (4, 2), (4, 3) 3
(2, 3) (3, 2), (4,
2), (4, 3)
3
(3, 2) (2, 3), (4, 3) 2
13 | P a g e
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
(3, 3) (2, 2), (4, 2) 2
(4,
)
(2, 2), (2, 3), (3, 3)
3
(4, 3) (2, 2), (2, 3), (3, 2) 3
Tối đa ρ
(1,1
S ∪ {(u, v)}) = 3 cho (v, u) = (2, 2). Thêm đỉnh (2, 2) vào S
1,1.
Tập độc lập S
1,1
= {(1, 1), (2, 2)}. Kích thước: 2.
Đỉnh có thể thêm (u, v) củaS
1,1
Đỉnh có thể thêm của S

của kích thước yêu cầu n = 4. Bây giờ đầu ra phần III S
1,1
được yêu cầu đúng 3-màu của
đầu vào đồ thị G và thuật toán kết thúc. Lưu ý rằng chúng ta giải thích kết quả như sau: đỉnh
1 được tô với màu 1 (màu xanh), đỉnh 2 được tô với màu 2 (màu đỏ), đỉnh 3 được tô với màu
3 (màu xanh) và đỉnh 4 được tô với màu 2 ( màu đỏ).
1.4. Độ phức tạp:
Tiếp theo để đánh giá độ phức tạp của giải thuật, nhóm sẽ chỉ ra rằng thuật toán kết thúc trong
thời gian đa thức, trong khi tìm kiếm một tập m-màu cho một đồ thị với n đỉnh, bằng cách xác
định một đa thức của N=nm đó là một cận trên trên tổng số bước tính toán thực hiện bởi thuật
toán.Lưu ý rằng chúng ta xem xét
14 | P a g e
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
• kiểm tra xem một cặp của các đỉnh được kết nối bởi một cạnh trong G, và
• so sánh xem một số nguyên cho trước nhỏ hơn một số nguyên cho trước được tính toán
các bước cơ bản.
Mệnh Đề 1
Cho một đồ thị đơn giản G với n đỉnh và một tập độc lập S của G×K
m
, thủ tục 1 mất ít
nhất (nm)
5
bước.
Chứng minh
Kiểm tra việc một đỉnh riêng có thể thêm thì mất tối đa (nm)
2
bước, từ đỉnh có ít hơn các lân
cận nm và cho mỗi lân cận phải mất ít hơn nm bước để kiểm tra xem nó là ở ngoài tập độc
lập. Đối với một tập độc lập riêng, việc tìm kiếm số ρ của các đỉnh có thể thêm mất ít
nhất (nm)

bên ngoài S mà có đúng một lân cận (u
2,
v
2)
bên trong S có tối đa
(nm)
2
bước, khi có ít hơn nm đỉnh ngoài S và chúng ta phải tìm ra nếu ít nhất một trong các lân
cận bé hơn nm của bất kỳ đỉnh nào ở trong S. Nếu như một đỉnh (u
1,
v
1)
đã được tìm thấy, phải
mất một bước để hoán đổi (u
1,
v
1)
và (u
2,
v
2).
Sau đó, bằng mệnh đề 4.1, phải mất ít
nhất (nm)
5
bước để thực hiện các thủ tục 1 vào tập độc lập kết quả. Như vậy, thủ tục 2 mất ít
nhất (nm)
2
+1 + (nm)
5
bước.

+ nm bước được
thực hiện. Có nm lượt cho i = 1, 2, , n, và j = 1, 2, , m, do đó, một phần I thực hiện tổng cộng
tối đa là nm((nm)
5
+ (nm)
6
+ (nm)
3
+nm) = (nm)
6
+ (nm)
7
+ (nm)
4
+ (nm)
2
bước.
15 | P a g e
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
Mệnh Đề 4
Cho một đơn đồ thị G với n đỉnh và m màu, thuật toán mất ít
hơn (nm)
8
+2 (nm)
7
+ (nm)
6
+ (nm)
5
+(nm)

+ (nm)
6
+ (nm)
4
+ (nm)
2)
+ ((nm)
8
+
(nm)
7
+ (nm)
5
+ (nm)
3)
= (nm)
8
+2 (nm)
7
+ (nm)
6
+ (nm)
5
+ (nm)
4
+ (nm)
3
+ (nm)
2
bước để

để tô màu cạnh kề của nó. Trong đó ở bước i tùy theo cách cài đặt sẽ có những cách đánh
màu khác nhau.
16 | P a g e
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
Với thuật toán trên chúng ta có thể tìm được 1 cách tô màu cho các cạnh của đồ thị với số
màu không quá Δ+1 màu ( vấn đề này sẽ thấy rõ hơn khi đi sâu vào phần cài dặt). Vậy đó đã là
số màu nhỏ nhất hay chưa. Theo định lý Vizing chúng ta phát biểu ở trên, ta có Δ(G)≤ χ′(G) ≤
Δ(G) + 1. Vậy sắc số cạnh chỉ có thể nằm ở 1 trong hai giá trị là Δ(G) và Δ(G) + 1. Với việc
chọn số màu lớn nhất có thể tô là Δ(G)+1, thuật toán đã kẹp được cận trên của sắc số cạnh. Với
việc lựa chọn màu có chỉ số nhỏ nhất chưa được sử dụng để tô các cạnh kề cho một cạnh, số màu
được sử dụng là số màu nhỏ nhất.
2.2. Ví dụ
Ta có đồ thị sau:
Ta sắp xếp các cạnh theo thứ tự như sau:
17 | P a g e
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
Bước 1 : tô màu cạnh thứ 1
Cạnh này tô màu đỏ trước tiên
Bước 2 : tô màu cạnh 2.
Cạnh 2 kề với cạnh 1 (tô màu đỏ) do đó cạnh 2 sẽ tô màu xanh lá cây
Bước 3: tô màu cạnh 3
18 | P a g e
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
Cạnh 3 kề với cạnh 1 (tô màu đỏ), cạnh 2 (tô màu xanh lá cây) do đó cạnh 3 phải tô màu xanh da
trời
19 | P a g e
Algo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52
Bước 4: tô màu cạnh 4
Cạnh 4 kề với cạnh 1 (tô màu đỏ) nên sẽ tô màu xanh lá cây
Bước 5: tô màu cạnh 5

Menu chương trình hiển thị các lựa chọn nhập dữ liệu:
25 | P a g e