Chương 8: Một số bài toán quan trọng của đồ thị
CHƯƠNG VIII: MỘT SỐ BÀI TOÁN QUAN TRỌNG
CỦA ĐỒ THỊ
Trong chương này chúng ta sẽ đề cập đến một số bài toán quan trọng của lý thuyết đồ thị.
Những bài toán này không chỉ có ý nghĩa đơn thuần về lý thuyết mà còn có những ứng dụng quan
trọng trong thực tế. Nhiều ứng dụng khác nhau của thực tế được phát biểu dưới dạng của các bài
toán này. Những bài toán được đề cập ở đây gồm:
9 Bài toán tô màu đồ thị.
9 Bài toán tìm đường đi ngắn nhất.
9 Bài toán luồng cực đại trên mạng.
Bạn đọc có thể tìm thấy thông tin về chứng minh tính đúng đắn cũng như độ phức tạp của
các thuật toán thông qua tài liệu [1], [2] của tài liệu tham khảo.
8.1. BÀI TOÁN TÔ MÀU ĐỒ THỊ
Định nghĩa 1. Cho trước một số nuyên dương p. Ta nói đồ thị G là p sắc nếu bằng p màu
khác nhau có thể tô trên các đỉnh mỗi đỉnh một màu sao cho hai đỉnh kề nhau tùy ý đều có màu
khác nhau. Số p nhỏ nhất mà đối với số đó đồ thị G là p sắc được gọi là sắc số của đồ thị G và kí
hiệu bằng
γ
(G).
Như vậy, sắc số của một đồ thị là số màu ít nhất cần dùng để tô trên các đỉnh của đồ thị
(mỗi đỉnh một màu) sao cho hai đỉnh kề nhau tùy ý được tô bằn hai màu khác nhau.
Định nhĩa 2. Sắc lớp là số màu ít nhất cần dùng để tô trên các cạnh của đồ thị mỗi cạnh một
màu sao cho hai cạnh kề nhau tùy ý được tô bằng hai màu khác nhau.
Ta có thể chuyển bài toán sắc lớp về bài toán sắc số bằng cách: Đối với mỗi đồ thị G = < V,
E> xây dựng đồ thị G’ = <V’, E’>, trong đó mỗi đỉnh thuộc V’ là một cạnh của G, còn E’ được
xác định như sau:
E’ ={ (v, v’)| u, u’
∈
V} và hai cạnh là kề nhau.
Nói cách khác, ta tạo đồ thị G‘ trong đó mỗi cạnh của nó trở thành một đỉnh của đồ thị, hai
cạnh kề nhau trong G sẽ có một đường nối giữa hai đỉnh của đồ thị trong G’. Bằng cách này ta dễ

deg(v
1
)≥ deg(v
2
)≥..≥deg(v
n
).
 Bước 2. Gán màu 1: cho v
1
; các đỉnh tiếp theo trong danh sách không liền kề với v1
(nếu nó tồn tại) và các đỉnh không kề với đỉnh có màu 1.
 Bước 3. Gán màu 2 cho đỉnh tiếp theo trong danh sách còn chưa được tô màu và các
đỉnh không kề với các đỉnh có màu 2. Nếu vẫn còn các đỉnh chưa được tô màu thì
gán màu 3 cho các đỉnh đầu tiên chưa được tô màu trong danh sách và các đỉnh
chưa tô màu không liền kề với các đỉnh có màu 3.
 Bước 4. Tiếp tục lặp lại bước 3 cho đến khi các đỉnh đã được tô màu.
8.2. BÀI TOÁN TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG
Bài toán. Cho một đồ có hướn G = <V, E>, V = { x
1
, x
2
,.., x
n
}. Với mỗi cung (x
i
, x
j
) có một
số q
ij

xx
xx
kiij
v
v
zz

0
≤
z
ij

≤
q
ij
với mọi (i,j)
∈
V .
nếu x = s,
nếu x = t,
cho các đỉnh còn lại.
Trong đó,
Γ
(x
i
) là tập hợp các cung đi ra khỏi x
i
,
Γ
-1

σ
(x
i
).
 Dạng thứ 2: (-x
j
,
σ
(x
i
)), có nghĩa là có thể giảm luồng theo cung (x
j
, x
i
) với lượng
lớn nhất là
σ
(x
i
).
Quá trình gán nhãn cho đỉnh tương ứng với thủ tục tìm đường đi tăng luồng từ s đến x.
Thuật toán gán nhãn được thực hiện thông qua các bước sau:
Bước 1. Đánh dấu đỉnh s bởi nhãn (+s,+
∞
). Đỉnh s là đỉnh có nhãn và chưa xét, tất cả các
đỉnh còn lại đều chưa có nhãn.
Bước 2. Chọn một đỉnh có nhãn nhưng chưa xét, chẳng hạn đỉnh x
i
, với nhãn là (±x
k

j
∈Γ
-1
(x
i
), z
ji
>0, x
j
chưa có nhãn}
Với mỗi đỉnh x
j
∈ K
+
(x
i
) ta gán cho nhãn (-x
i
, σ(x
j
)), trong đó σ(x
j
) = min { σ(x
i
), z
ij
}.
Với mỗi đỉnh x
j
∈ K

Bước 3. Lặp lại bước 2 cho đến khi một tron hai khả năng sau xảy ra:
 Đỉnh t được đánh dấu, chuyển sang bước 4.

179
Chương 8: Một số bài toán quan trọng của đồ thị
 Đỉnh t không có nhãn và không thể đánh dấu tiếp tục được nữa. Khi đó luồng đang
xét là luồng cực đại. Nếu kí hiệu X
0
là tập các đỉnh có nhãn, Y
0
là tập các đỉnh
không có nhãn thì (X
0
,Y
0
) sẽ là lát cắt hẹp nhất. Thuật toán dừng.
Bước 4. Đặt x=t.
Bước 5. Tiến hành tăng luồng:
 Nếu đỉnh x có nhãn là (+u,
σ
(x)) thì tăng luồng theo cung (u,x) từ z(u,x) lên z(u,x)+
σ
(t).
 Nếu đỉnh x có nhãn là (-u,
σ
(x)) thì giảm lượng vận chuyển trên cung (u,x) từ z(u,x)
xuống còn (z(u,x)-
σ
(t)).
Bước 6. Nếu u=s thì xóa tất cả các nhãn và quay lại bước 1 với luồng đã điều chỉnh ở bước

là (+x
1
, ∞). Ta có V
x
=φ, V
c
= {x
1
}.
Bước 2. Xét đỉnh x
1
, ta có
K
+
(x
1
) = { x
2
, x
3
}, K
-
(x
1
) = φ.
Nhãn của x
2
là {+x
1
, min(∞, 2-0)}=(+x

5
}, K
-
(x
2
) = φ.
Nhãn của x
4
là {+x
2
, min(2, 4-0)}=(+x
2
,2).

180
Chương 8: Một số bài toán quan trọng của đồ thị
Nhãn của x
5
là {+x
2
, min(2, 2-0)}=(+x
2
,2).
Hai tập V
x
= {x
1,
x
2
}, V

6
đã được gán nhãn.
Bước 4. Đặt x = t.
Bước 5. Đỉnh x = x
6
có nhãn là (+u, σ(x))= (+x
4
,2). Tăng luồng trên cung ( x
4
, x
6
) từ 0 lên
0+σ(t)=2.
Bước 6. Vì u=x
4
≠ s nên đặt x= x
4
.
Bước 5. Đỉnh x= x
4
có nhãn là (+u, σ(x)) =(+x
2
,2). Tăng luồng trên cung (x
2
,x
4
) từ 0 lên 0
+σ(t)=2.
Bước 6. Vì u = x
2

, ta có
K
+
(x
1
) = { x
3
}, K
-
(x
1
) = φ.
Nhãn của x
3
là {+x
1
, min(∞, 4-0)}=(+x
1
,4).
Hai tập V
x
= {x
1
}, V
c
={ x
3
}.
Bước 2. xét đỉnh x
3

3
, x
6
) từ 0 lên
0+σ(t)=1.
Bước 6. Vì u=x
3
≠ s nên đặt x= x
3
.

181
Chương 8: Một số bài toán quan trọng của đồ thị
Bước 5. Đỉnh x= x
3
có nhãn là (+u, σ(x)) =(+x
1
,4). Tăng luồng trên cung (x
1
,x
3
) từ 0 lên 0
+σ(t)=1.
Bước 6. Vì u = x
1
=s nên xóa tất cả các nhãn và quay lại bước 1.
Lần lặp thứ 3:
Bước 1. Gán nhãn cho x
1
là (+x

x
= {x
1
}, V
c
={ x
3
}.
Bước 2. Xét đỉnh x
3
, ta có
K
+
(x
3
) = { x
4
}, K
-
(x
3
) = φ.
Nhãn của x
4
là {+x
3
, min(3, 4-0)}=(+x
3
,3).
Hai tập V

,2).
Hai tập V
x
= {x
1,
x
3
, x
4
}, V
c
={ x
2
}.
Bước 2. Xét đỉnh x
2
, ta có
K
+
(x
2
) = {x
5
}, K
-
(x
2
) = φ.
Nhãn của x
5

-
(x
5
) = φ.
Nhãn của x
6
là {+x
5
, 2). Đỉnh t = x
6
đã được gán nhãn.
Dùng bước 4, 5 và 6 ta tìm được đường đi tăng luồng là:
x
1
→x
3
→ x
4
← x
2
→ x
5
→ x
6

Trên các cung thuận ta tăng vận chuyển lên một lượng là σ(t) = 2, trên cung ngược ta giảm
vận chuyển đi một lượng là σ(t).
Lần lặp thứ 4:

182

, 1}.
Hai tập V
x
= {x
1
}, V
c
={ x
3
}.
Bước 2. Xét đỉnh x
3
, ta có
K
+
(x
3
) = { x
4
}, K
-
(x
3
) = φ.
Nhãn của x
4
là {+x
3
, min(1, 4-2)}=(+x
3

= {x
1
, x
3
, x
4
}, Y0= {x
2
, x
5
, x
6
}.
8.3. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
Xét đồ thị G=<V, E>; trong đó | V| = n, | E | = m. Với mỗi cạnh (u, v)∈E, ta đặt tương ứng
với nó một số thực A<u,v> được gọi là trọng số của cạnh. Ta sẽ đặt A[u,v]=
∞
nếu (u, v)∉E. Nếu
dãy v
0
, v
1
,..., v
k
là một đường đi trên G thì
],[
1
1
∑
=


183
Chương 8: Một số bài toán quan trọng của đồ thị
cách gán d[v] = d[u] + A[u, v]. Quá trình sẽ kết thúc khi nào ta không thể làm tốt hơn lên được
bất kỳ cận trên nào, khi đó d[v] sẽ cho ta giá trị ngắn nhất từ đỉnh s đến đỉnh v. Giá trị d[v] được
gọi là nhãn của đỉnh v. Ví dụ dưới đây thể hiện tư tưởng trên bằng một thuật toán gán nhãn tổng
quát như sau:
Ví dụ. Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh Z trên đồ thị hình 8.3.
B 7 F
6 4 5 6

5 4 6 3
A C D G Z
8 4 4 5

E 6 H

Hình 8.3. Đồ thị trọng số G
 Bước 1. Gán cho nhãn đỉnh A là 0;
 Bước 2. Trong số các cạnh (cung) xuất phát từ A, ta chọn cạnh có độ dài nhỏ nhất,
sau đó gán nhãn cho đỉnh đó bằng nhãn của đỉnh A cộng với độ dài cạnh tương ứng.
Ta chọn được đỉnh C có trọng số AC = 5, nhãn d[C] = 0 + 5 = 5.
 Bước 3. Tiếp đó, trong số các cạnh (cung) đi từ một đỉnh có nhãn là A hoặc C tới một
đỉnh chưa được gán nhãn, ta chọn cạnh (cung) sao cho nhãn của đỉnh cộng với trọng
số cạnh tương ứng là nhỏ nhất gán cho nhãn của đỉnh cuối của cạnh (cung). Như vậy,
ta lần lượt gán được các nhãn như sau: d[B] = 6 vì d[B] <d[C] + | CB| = 5 + 4; d[E]
= 8; Tiếp tục làm như vậy cho tới khi đỉnh Z được gán nhãn đó chính là độ dài đường
đi ngắn nhất từ A đến Z. Thực chất, nhãn của mỗi đỉnh chính là đường đi ngắn nhất từ
đỉnh nguồn tới nó. Quá trình có thể được mô tả như trong bảng dưới đây.
Bước Đỉnh được gán nhãn Nhãn các đỉnh Đỉnh đã dùng để gán nhãn

A
C
B
E
D
Z

184
Chương 8: Một số bài toán quan trọng của đồ thị
Như vậy, độ dài đường đi ngắn nhất từ A đến Z là 18. Đường đi ngắn nhất từ A đến Z qua
các đỉnh: A-> C-> D -> G -> Z.
8.3.2. Thuật toán Dijkstra
Thuật toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại được Dijkstra đề nghị áp
dụng cho trường hợp đồ thị có hướng với trọng số không âm. Thuật toán được thực hiện trên cơ
sở gán tạm thời cho các đỉnh. Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất
tới đỉnh đó. Các nhãn này sẽ được biến đổi (tính lại) nhờ một thủ tục lặp, mà ở mỗi bước lặp một
số đỉnh sẽ có nhãn không thay đổi, nhãn đó chính là độ dài đường đi ngắn nhất từ s đến đỉnh đó.
Thuật toán có thể được mô tả bằng thủ tực Dijkstra như sau:
void Dijkstra(void)
/*Đầu vào G=(V, E) với n đỉnh có ma trận trọng số A[u,v]≥ 0; s∈V */
/*Đầu ra là khoảng cách nhỏ nhất từ s đến các đỉnh còn lại d[v]: v∈V*/
/*Truoc[v] ghi lại đỉnh trước v trong đường đi ngắn nhất từ s đến v*/
{
/* Bước 1: Khởi tạo nhãn tạm thời cho các đỉnh*/
for ( v∈ V ) {
d[v] = A[s,v];
truoc[v]=s;
}
d[s]=0; T = V\{s}; /*T là tập đỉnh có nhãn tạm thời*/
/* Bước lặp */