Tài liệu Đại số lý thuyết đồ thị

i toán tìm đường đi ngắn nhất. 
Trương Mỹ Dung 37
GHI CHÚ. 
Giả thiết « Hàm trọng lượng không âm » là bắt buộc. Chẳng hạn, sử dụng thuật toán 
Dijktra-Moore cho đồ thị ở hình FIG.3.2, dẫn đến kết quả sai nếu ta chọn gốc là 
đỉnh s1. Thật vậy, đầu tiên, ta chọn đỉnh s2, (s1 → s2) trong khi đó, đường đi ngắn 
nhất là đường đi từ đỉnh s1 đến s2 qua s3 . 
 3 
 3 - 5 
 1 2 2 
 FIG. 3.2. Đồ thị có định hướng, có trọng lượng bất kỳ. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Bài toán tìm đường đi ngắn nhất. 
Trương Mỹ Dung 38
3.3.2. THUẬT TOÁN BELLMAN-FORD (1958-1962) 
Sự hiện diện của dấu bất kỳ của trọng lượng (hay chiều dài ) cho phép, chẳng hạn, 
có thể cải tiến chi phí hay lợi nhuận. Thuật toán DIJKSTRA-MOORE không cho 
phép xét tới những cạnh (cung) có trọng lượng không âm, vì trong trường hợp một 
cạnh được đánh dấu, thì ta không thể thay đổi gì cho những bước lặp tiếp theo. Thuật 
toán DIJKSTRA-MOORE còn được gọi là gán nhãn cố định . 
Để giải quyết cho trường hợp đồ thị có trọng lượng bất kỳ, ta một xét thuật toán cho 
phép một đánh dấu chỉ được xác định hoàn toàn khi thuật toán kết thúc. Một kiểu 
thuật toán như vậy được gọi là điều chỉnh nhãn. 
Thuật toán BELLMAN-FORD chỉ có giá trị cho các đồ thị không có chu trình, có 
trọng lượng bất kỳ. 
Ký hiệu : 
♦ Tập đỉnh được đánh số thứ tự từ 1 ..n. 
♦ Pr(p) = đỉnh trước đỉnh p theo đường đi ngắn nhất từ gốc đến đỉnh p. 
♦ d = khoảng cách ngắn nhất từ gốc đến các đỉnh còn lại trong đồ thị. 
♦ Mark = Tập đỉnh đã đánh dấu (đã xét rồi), định nghĩa như sau : 
 Mark[i] = 1, nếu đỉnh đã xét rồi, 
 0, ngược lại. 
Khoảng cách ngắn nhất từ gốc đến một đỉnh v chỉ được tính khi tất cả các phần 
tử trước của v (Γ -(v)) đã được đánh dấu rồi. Một đỉnh bất kỳ, khi chưa đánh 
dấu, thì khoảng cách từ gốc đến đỉnh đó chưa biết (chưa tính). 
NGUYÊN LÝ THUẬT TOÁN 
1. Gán các giá trị ban đầu. 
™ Chọn đỉnh s1 làm gốc. 
™ Mark = [1,00] ; d[1] = 0 ; Pr[1] = 1. 
2. Ở mỗi bước lặp : 
™ Chọn đỉnh k chưa đánh dấu sao cho tất cả đỉnh trước của k đã đánh dấu 
rồi , nghĩa là : Mark[k] = 0 và ∀ j ∈ Γ -(k) : Mark[j]= 0 
™ Cập nhật Mark : Mark[k] =1 ; 
™ Tính d[k] = min { d[i] + a[i, k]: i ∈ Γ - (k)}, và Pr[k] là chỉ số đạt min. 
ĐỘ PHỨC TẠP : O(nm). O(n3) Cho các đồ thị dầy, i.e., những đồ thị mà m ≈ n². 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Bài toán tìm đường đi ngắn nhất. 
Trương Mỹ Dung 39
THÍ DỤ. 
 3 
 Gán ban đầu : Mark, d, Pr : 
 2 -2 4 Mark = [1, 0, 0, 0, 0, 0}, 
 d[1] = 0 ; 
 1 5 -5 Pr [1] = 1 
 1 1 6 Γ - (2) ={1,3};Γ- (3)={1};Γ- (4)={2,3,6} 
 -2 Γ - (5) ={3} ; Γ- (6) ={2,5} 
 -1 
 3 4 5 
 FIG.3.1. Đồ thị có định hướng, có trọng lượng bất kỳ, không có chu trình, gốc đỉnh 1. 
ƒ Bước 1. Chọn đỉnh 3 vì Γ- (3)={1} . Cập nhật Mark[3], Tính d[3] và Pr[3] : 
 Mark[3] = 1 ; d[3] = -2 ; Pr[3] = 1; 
ƒ Bước 2. Ở bước lặp này, ta có thể chọn đỉnh 5 (hay đỉnh 2). 
 Cập nhật Mark[5], Tính d[5] và Pr[5] : 
 Mark[5] = 1 ; d[5] = 2 ; Pr[5] = 3; 
ƒ Bước 3. Chọn đỉnh 2 . Cập nhật Mark[2], Tính d[2] và Pr[2] : 
 Mark[2] = 1 ; d[2] = -1 ; Pr[2] = 3; 
ƒ Bước 4. Chọn đỉnh 6 . Cập nhật Mark[6], Tính d[6] và Pr[6] : 
 Mark[6] = 1 ; d[6] = 1; Pr[6] = 5 
ƒ Bước 5. Chọn đỉnh 4 . Cập nhật Mark[4], Tính d[4] và Pr[4] : 
 Mark[4] = 1 ; d[4] = - 4 ; Pr[4] = 6 
Thuật toán kết thúc vì tất cả các đỉnh đã được chọn rồi. 
Từ thuật toán , ta có kết quả sau : 
 d = [0, -1, -2, -4, 2, 1] 
 Pr = [1, 3, 1, 6, 3, 5] 
ƒ Đường đi ngắn nhất từ s1 đến s2 : s1 → s3 → s2 và độ dài là -1 
ƒ Đường đi ngắn nhất từ s1 đến s3 : s1 → s3 và độ dài là -2 
ƒ Đường đi ngắn nhất từ s1 đến s4 : s1 → s3 → s5 → s6 → s4 và độ dài là - 4 
ƒ Đường đi ngắn nhất từ s1 đến s5 : s1 → s3 → s5 và độ dài là 2 
ƒ Đường đi ngắn nhất từ s1 đến s6 : s1 →s3 → s5 → s6 và độ dài là 1 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Bài toán tìm đường đi ngắn nhất. 
Trương Mỹ Dung 40
3.4. GIỮA TẤT CẢ CÁC CẶP ĐỈNH: THUẬT TOÁN FLOYD (1962). 
Ta sẽ tính một ma trận khoảng cách n x n. Nếu tất cả chiều dài không âm (l(u)≥ 0) ta có 
thể áp dụng n lần thuật toán Dijktra-Moore cho mỗi đỉnh i. . Nếu đồ thị có chứa chiều 
dài âm (l(u) < 0) ta có thể áp dụng n lần thuật toán Bellman-Ford cho mỗiđỉnh i. Thuật 
toán Floyd có cách tiếp cận khác có lợi cho trường hợp ma trận dầy. 
Ký hiệu : 
™ A : ma trận trọng lượng, được gán giá trị ban đầu như sau : 
 0 nếu i = j 
 A[i,j] = l(i, j) nếu (i, j) ∈ U 
 ∞ nguợc lại. 
™ P : ma trận các đỉnh trước, được gán giá trị ban đầu như sau : 
 P[i,j] = i, trong đó P[i,j] là đỉnh trước của đỉnh j trên đường đi từ gốc i đến j 
Khi kết thúc thuật toán, ta có : 
P[i,j] = đỉnh trước của j trên đường đi ngắn nhất từ gốc i đến đỉnh j, với chiều 
dài tương ứng là A[i,j]. 
THỦ TỤC FLOYD(L, P) 
For (k =1; k≤ n ; k++) 
 For (i =1 ;i≤ n ; i++) 
 For (j =1 ;j≤ n ; j++) 
 If (a[i,k] + a[k,j] < a[i,j]) 
 { a[i,j] := a[i,k] + a[k,j] ; p[i,j] :=p[k,j] ;} 
Độ phức tạp : O(n3). 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Bài toán tìm đường đi ngắn nhất. 
Trương Mỹ Dung 41
THÍ DỤ. 
 1 2 2 
 -1 
 6 -2 
 -4 5 
 4 5 3 
Gán ban đầu : cho các ma trận A, P. 
 1 2 3 4 1 2 3 4 
 1 0 2 ∝ 6 1 1 1 1 
 A0 = 2 ∝ 0 -2 ∝ P0 = 2 2 2 2 
 3 ∝ 5 0 5 3 3 3 3 
 4 -4 -1 ∝ 0 4 4 4 4 
 Các bước lặp : 
ƒ k =1. 
 1 2 3 4 1 2 3 4 
 1 0 2 ∝ 6 1 1 1 1 
 A1 = 2 ∝ 0 -2 ∝ P1 = 2 2 2 2 
 3 ∝ 5 0 5 3 3 3 3 
 4 -4 -2 ∝ 0 4 1 4 4 
ƒ k = 2 
 1 2 3 4 1 2 3 4 
 1 0 2 0 6 1 1 2 1 
 A2 = 2 ∝ 0 -2 ∝ P2 = 2 2 2 2 
 3 ∝ 5 0 5 3 3 3 3 
 4 -4 -2 -4 0 4 1 2 4 
ƒ k =3 
 1 2 3 4 1 2 3 4 
 1 0 2 0 5 1 1 2 3 
 A3 = 2 ∝ 0 -2 3 P3 = 0 2 2 3 
 3 ∝ 5 0 5 0 3 3 3 
 4 -4 -2 -4 0 4 1 2 4 
ƒ k = 4 
 1 2 3 4 1 2 3 4 
 1 0 2 0 5 1 1 2 3 
 A4 = 2 -1 0 -2 3 P4 = 0 2 2 3 
 3 1 3 0 5 4 1 3 3 
 4 -4 -2 -4 0 4 1 2 4 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Bài toán tìm đường đi ngắn nhất. 
Trương Mỹ Dung 42
Cách nhận biết đường đi ngắn nhất. 
Để nhận được đường đi ngắn nhất từ s1 đến sj , ta sử dụng dòng thứ i của ma trận 
P. Chẳng hạn, ta muốn nhận được đường đi ngắn nhất µ : s4 → s3, ta tham khảo 
ma trận P như sau : P[4,3]=2 :s2 là đỉnh trước của s3 ; P[4,2]=1 : s1 là đỉnh trước 
của s2 ; P[4,1]=4 :s4 là đỉnh trước của s1 . 
Cuối cùng, kết quả là µ = s4 → s1 → s2→ s3. 
Một trong ứng dụng của Thuật toán FLOYD là tìm đường đi giũa hai đỉnh. Thuật 
toán này được WARSHALL phát triễn cùng năm (1962), và thuật toán thường mang 
tên FLOYD-WARSHALL ». 
Ký hiệu : 
™ A = ma trận kề của đồ thị, được gán giá trị ban đầu như sau : 
 l nếu (i, j) ∈ U 
 A[i,j] = 0 nguợc lại. 
™ P = ma trận các đỉnh trước, được gán giá trị ban đầu như sau : 
 0 nếu a[i,j] = 0, 
 P[i,j] = 1 nguợc lại. 
Khi kết thúc thuật toán : 
P[i,j] = đỉnh trước của j trên đường đi từ đỉnh i đến đỉnh j (nghĩa là a[i,j]=1). 
THỦ TỤC FLOYD-WARSHAL(A, P) 
For (k =1 ;k≤ n ; k++) 
 For (i =1 ;i≤ n ; i++) 
 For (j =1 ;j≤ n ; j++) 
 If (a[i,j] = = 0) 
 { a[i,j] = a[i,k] *a[k,j] ; p[i,j] =p[k,j] } 
Độ phức tạp : O(n3). 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Bài toán tìm đường đi ngắn nhất. 
Trương Mỹ Dung 43
THÍ DỤ. 
 1 2 
 4 3 
Gán ban đầu : cho các ma trận A, P. 
 1 2 3 4 1 2 3 4 
 1 0 1 0 1 0 1 0 1 
 A0 = 2 0 0 1 0 P0 = 0 0 2 0 
 3 0 1 0 1 0 3 0 3 
 4 1 1 0 0 4 4 0 0 
Các bước lặp : 
ƒ k =1. 
 1 2 3 4 1 2 3 4 
 1 0 1 0 1 0 1 0 1 
 A1 = 2 0 0 1 0 P1 = 0 0 2 0 
 3 0 1 0 1 0 3 0 3 
 4 1 1 0 1 4 4 0 1 
ƒ k = 2 
 1 2 3 4 1 2 3 4 
 1 0 1 1 1 0 1 2 1 
 A2 = 2 0 0 1 0 P2 = 0 0 2 0 
 3 0 1 1 1 0 3 2 3 
 4 1 1 1 1 4 4 2 1 
ƒ k =3 
 1 2 3 4 1 2 3 4 
 1 0 1 1 1 0 1 2 1 
 A3 = 2 0 1 1 1 P3 = 0 3 2 3 
 3 0 1 1 1 0 3 2 3 
 4 1 1 1 1 4 4 2 1 
ƒ k = 4 
 1 2 3 4 1 2 3 4 
 1 1 1 1 1 4 1 2 1 
 A4 = 2 1 1 1 1 P4 = 4 3 2 3 
 3 1 1 1 1 4 3 2 3 
 4 1 1 1 1 4 4 2 1 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 43
CHƯƠNG 4. 
ĐỒ THỊ PHẲNG & BÀI TOÁN 
TÔ MÀU. 
4.1. ĐINH NGHĨA VỀ ĐỒ THỊ PHẲNG. 
Đồ thị phẳng là một đồ thị có thể biểu diễn trên một mặt phẳng (hay trên hình 
cầu) sao cho hai cung (hay hai cạnh) không cắt nhau. 
Ghi chú. Hai cạnh có chung một đỉnh được gọi là không cắt nhau. 
 Cắt nhau Không cắt nhau . 
Thí dụ. Đồ thị G1 là đồ thị phẳng và G2 , G3 là các biểu diễn phẳng của G1. 
 Đồ thị G1 Biểu diễn G2, G3 của G1. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 44
Cho G là đồ thị phẳng. Một mặt (FACE) của G là một miền, giới hạn bởi các 
cạnh, không có đỉnh lẫn cạnh ở bên trong. Trong các mặt này luôn luôn có một 
và chỉ một mặt vô hạn. Đường biên (CONTOUR) của một mặt r là chu trình 
hợp thành từ các cạnh biên của r. Hai mặt r và s được gọi là KỀ 
(ADJACENTES) nếu đường biên của chúng có chung ít nhất một cạnh. Hai mặt 
không có chung một đỉnh nào thì sẽ không kề. 
THÍ DỤ. 
™ Một bản đồ địa dư là một đồ thị phẳng (với điều kiện là không có đảo). 
Đồ thị này đặc biệt mỗi đỉnh có bậc ≥ 3. Mặt h là mặt vô hạn, những 
mặt còn lại a, b, c, d, e, f, g là những mặt hữu hạn. 
 h 
 A a 
 c 
 a b 
 d e 
 f 
 FIG. 4.1. ĐỒ THỊ PHẲNG. 
™ Bài toán ba làng và ba nhà máy. Ta có 3 làng a, b, c, mà ta muốn 
đặt đường nối với 3 nhà máy : một nhà máy cung cấp nước d, một nhà 
máy cung cấp ga e, một nhà máy cung cấp điện f. Vấn đề đặt ra là , ta 
có thể đặt trên một mặt phẳng sao cho các đường dẫn không giao nhau 
ngoài các đỉnh cực biên ? Đồ thị biểu diễn 3 làng và 3 nhà máy cho phép 
định nghĩa một lớp các đồ thị không phẳng. 
 a b c 
 d e f 
 FIG 4.2. ĐỒ THỊ KHÔNG PHẲNG LOẠI 1 : K3,3. 
g
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 45
4.2. CÔNG THỨC EULER , HỆ QUẢ & THÍ DỤ. 
4.2..1. CÔNG THỨC EULER. 
Cho một đồ thị phẳng liên thông có n đỉnh, m cạnh và f mặt, ta có 
n - m + f = 2 
Chứng minh. Truy chứng trên số cạnh : 
™ m = 1. Ta có n= 2 đỉnh và f=1 mặt. Ta có n – m + f = 2 – 1 + 1 = 2 
Vậy công thức EULER đúng cho trường hợp m = 1. 
™ Giả sử công thức EULER đúng cho trường hợp đồ thị Gi-1 có mi – 1 cạnh. 
Ta sẽ chứng minh công thức EULER cũng đúng cho trường hợp đồ thị có mi 
cạnh. 
Gọi cạnh u = (x,y) là cạnh vẽ thêm vào Gi-1 để có Gi. 
Hiễn nhiên là có it nhất một đỉnh thuộc Gi-1 và u=(x,y) thuộc một mặt K 
của Gi-1. Giả sử x ∈ Gi-1. Có 2 trường hợp xãy ra : 
1. y ∈ K. Do đó ta có : x 
fi = fi-1 + 1. 
ni = ni-1 K 
mi = mi-1 + 1 
Ta có : y 
 ni - mi + fi = ni – (mi-1 + 1) + (fi-1 + 1). 
 = ni – mi-1 + fi-1 = 2 
Vậy công thức EULER đúng. 
2. y ∉ K. Ta có : 
fi = fi-1 . 
ni = ni-1 + 1 
mi = mi-1 + 1 
Ta có : 
 ni - mi + fi = (ni + 1) – (mi-1 + 1) + fi-1 
 = ni – mi-1 + fi-1 = 2 
Vậy công thức EULER đúng. 
Vậy công thức EULER đúng với mọi m. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 46
4.2.2. Hệ quả. 
Trong một đồ thị đơn giản phẳng, liên thông bất kỳ có n đỉnh, m cạnh (m > 2) 
và f mặt. Khi ấy, ta có : 
 3f/2 ≤ m ≤ 3n - 6. (1) 
Chứng minh. 
Mỗi mặt bị bao ít nhất 3 cạnh, mỗi cạnh thuộc 2 mặt. 
Ba cạnh xác định tối đa 2 mặt. Vậy số mặt tối đa là 2m/3. 
Ta có f ≤ 2m/3. Dùng công thức EULER suy ra bất đẳng thức (1). 
4.2.3. Hệ quả. 
Trong tất cả các đồ thị phẳng đơn giản, có ít nhất một đỉnh có bậc ≤ 5. 
Chứng minh. 
Giả sử mọi đỉnh có bậc > 6. Khi ấy 2m > 6n ⇒ m > 3n > 3n – 6. Mâu thuẩn. 
4.2.4. THÍ DỤ. 
Dùng công thức EULER, ta sẽ chứng minh là tất cả đồ thị đầy đủ 5 đỉnh K5 là 
không phẳng. 
 FIG 4.3. ĐỒ THỊ KHÔNG PHẲNG LOẠI 2 : K5. 
Chứng minh. 
Ta có số đỉnh n = 5, Số cạnh m = n(n-1)/2 = 10. 
Nếu K5 phẳng, áp dụng hệ quả 3.2.2 ta có : 
 10 = m ≤ 3n – 6 = 3x5 – 6 = 9. 
Mâu thuẩn. Vậy K5 không phẳng. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 47
Nhận xét. 
™ Đồ thị những làng và những nhà máy (Loại 1 : K3,3) và đồ thị đầy đủ 5 
đỉnh (loại 2 :K5) cho phép định nghĩa tất cả những đồ thị mà không phẳng. 
™ K5, K3,3 cùng là đồ thị đều. 
™ Đồ thị K5 không phẳng với số đỉnh nhỏ nhất, đồ thị K3,3 là đồ thị không phẳng 
có số cạnh nhỏ nhất, và cả hai là đồ thị không phẳng đơn giản nhất. 
4.3. BẤT ĐẲNG THỨC CẠNH- ĐỈNH. 
4.3.1. THÍ DỤ. 
Ta xét bài toán xác định xem đồ thị G cho trước có phẳng không ? 
™ THÍ DỤ 1. Cho đồ thị K4.. K4 phẳng. 
™ THÍ DỤ 2. Cho đồ thị G sau : 
 a b c d 
 h g f e 
 G phẳng vì ta có thể vẽ lại như sau : 
 g b f 
 a c 
 h d e 
™ THÍ DỤ 3. Đồ thị sau đây không phẳng. 
 a b c 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 48
 1 2 3 
4.3.2. BẤT ĐẲNG THỨC CẠNH – ĐỈNH. 
Cho G là một đồ thị phẳng liên thông có n đỉnh, m cạnh và đường biên của 
các mặt có số cạnh g ≥ 3. Khi ấy, ta có : 
 m ≤ (n-2) g/ (g-2). 
Chứng minh. 
Giả sử ma trận kề cạnh- mặt có dạng : 
 f1 f2 . fj fF 
 m1 . 
 m2 . 
A = . . 
 mI . . . mij 
 . 
 mf 
trong đó : 
 mij = 1 nếu mI là cạnh biên của fj, 
 0 ngược lại. 
Xét hàng thứ i, ta có : 
 Σ mij ≤ 2 ( vì mij là cạnh biên của nhiều nhất 2 mặt) 
Suy ra Σ Σ mij ≤ 2m (1) 
Xét cột thứ j, ta có : 
 Σ mij ≥ g (vì mặt fj có it nhất g cạnh biên) 
Suy ra Σ Σ mij ≥ gf (2) 
Theo công thức EULER, ta có : 
n - m + f = 2 (3) 
 Theo (2), (1), ta có : 
 gf = g(2 + m - n) ≤ 2m 
 (2 + m - n) ≤ 2m/g 
 ⇔ m(1-2/g) ≤ n – 2 
 ⇔ m ≤ (n-2) g/(g-2) 
 BĐT đã chứng minh xong. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 49
™ THÍ DỤ. 
Nhờ Bất đẳng thức trên, ta sẽ chứng minh được rằng đồ thị 3 làng và 3 nhà máy 
K3,3 , xem hình FIG. 4.2. không phẳng. 
Thật vậy, nhận xét rằng mọi chu trình trong K3,3 có số cạnh ít nhất là 4. Vậy 
nếu K3,3 phẳng mọi mặt phải có số cạnh ít nhất là 4. 
Theo Bất đẳng thức trên, ta có : 9 = m ≤ (6-2) 4/(4-2) = 8. Mâu thuẩn. 
Vậy K3,3 không phẳng. 
4.4. PHÉP ĐỒNG DẠNG. 
4.4.1. ĐỊNH NGHĨA. 
Hai đồ thị được gọi là đồng dạng với nhau nếu đồ thị này có được bằng 
cách biến đổi đồ thị kia theo cách thêm đỉnh bậc 2 hoặc bỏ đi đỉnh bậc 2. 
THÍ DỤ. a b → a c b → a b 
 Thêm Bớt 
 Đỉnh c bậc 2 vào ab Đỉnh c bậc 2 khỏi acb. 
4.4.2. BỔ ĐỀ. 
Giả sử H là đồ thị con của G. Khi ấy : 
™ Nếu G phẳng thì H phẳng. 
™ Nếu H không phẳng thì G cũng không phẳng. 
4.4.3. BỔ ĐỀ. 
Mọi đồ thị là phẳng nếu đồng dạng của nó là phẳng. 
4.5. ĐỊNH LÝ KURATOWSKI. 
Đồ thị G là phẳng nếu và chỉ nếu G không chứa một đồ thị con đồng cấu với 
K5 cũng như với K3,3. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 50
4.6. BÀI TOÁN TÔ MÀU ĐỒ THỊ. 
4.6.1. ĐỊNH NGHĨA. 
Phép tô màu một đồ thị là phép gán màu cho các đỉnh của đồ thị sao cho hai đỉnh 
kề nhau có màu khác nhau. 
Một cách hình thức có thể định nghĩa phép tô màu như sau : 
Phép tô màu là một ánh xạ γ : X → N sao cho ∀ (x, y) ∈ X, γ(x) ≠ γ (y). 
THÍ DỤ. 
 FIG 4.4. 
Số màu (phân biệt) ít nhất cần thiết để tô màu các đỉnh của đồ thị G được 
gọi là Sắc tố (CHROMATIQUE) và ký hiệu là γ (G). 
Một đồ thị G γ (G) ≤ k được gọi là k-sắc tố. 
Chận trên của sắc tố được cho bởi d + 1 với d bậc lớn nhất của đỉnh. 
 γ (G) ≤ d + 1 
4.6.2. CÁC ỨNG DỤNG. 
™ XẾP LỊCH THI. 
Giả sử ta khảo sát việc thi vấn đáp của một kỳ thi. Có những ràng buộc sau : 
♦ Một thầy , một lúc chỉ có thể hỏi thi một em. 
♦ Một thí sinh thi với một thầy vào một thời gian đã định trước. 
Sự phân bố thí sinh thi với thầy nào đã được ấn định trươc. (Thầy Pi thí sinh 
Ej) : 
THÍ DỤ. (P1, E1), (P1, E2), (P1, E3), (P2, E1), (P2, E2), 
™ BẢN ĐỒ ĐỊA DƯ. 
Một bài toán hết sức lý thú là tô màu các bản đồ sao cho hai vùng khác nhau 
không cùng một màu. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 51
4.6.3. THUẬT TOÁN TÔ MÀU. 
DỮ LIỆU : Đồ thị G = (X, U). 
KẾT QUẢ : Một phép tô màu γ : X → N. 
BEGIN. 
Cho τ = x1, x2, ,xn là một phép đánh số thứ tự các đỉnh của G. 
Cho C = {1 , 2, , k} tập các màu. 
FOR i=1 To n Do 
 γ(xi) = Min{k ∈ C :∀ đỉnh y kề x,, γ(y) ≠ k} 
END. 
4.6.4. ĐỊNH LÝ. 
Nếu G có chứa một đồ thị con đẳng hình với Km thì γ (G) ≥ m. 
CHỨNG MINH. Hiễn nhiên. 
4.6.5. ĐỊNH LÝ 5 MÀU (KEMPE-HEAWOOD). 
Mọi đồ thị phẳng đều có 5-sắc tố. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 3. Đồ thị phẳng và Bài toán Tô màu. 
Trương Mỹ Dung 52
4.6.6. BÀI TOÁN 4 MÀU. 
™ GIẢ THIẾT BÀI TOÁN 4 MÀU. 
Trên một bản đồ bất kỳ, ta nói nó được tô màu nếu mỗi miền của bản đồ được tô 
một màu xác định sao cho 2 miền kề nhau (chung một phần biên) phải được tô 
bằng hai màu khác nhau. Vấn đề đặt ra là cần dùng tối thiểu bao nhiêu màu để 
tô được một bản đồ bất kỳ. Vấn đề này được đặt ra từ năm 1852 do giáo sư De 
Morgan đặt ra : « Mọi bản đồ đều có thể tô bằng 4 màu sao cho hai nước nằm kề 
nhau phải được tô bằng hai màu khác nhau ». Sau đó có rất nhiều cố gắng của 
các nhà toán học để giải bài toán này nhưng đều không đi đến kết quả cuối cùng. 
Cho đến năm 1976, một nhóm các nhà toán học (K. Appel, W. Haken, J.Koch) 
đã xây dựng một lời giải dựa trên kết quả do máy tính IBM cung cấp đã khẳng 
định được giả thiết 4 màu là đúng. 
™ LIÊN QUAN GIỮA BÀI TOÁN 4 MÀU & SẮC TỐ ĐỒ THỊ PHẲNG. 
Cho một đồ thị phẳng G liên thông, không có đỉnh cô lập. Ta xây dựng một đồ 
thị đối ngẫu của nó gọi là G’ như sau : 
ƒ Mỗi đỉnh x* của G’ tương ứng đúng với một mặt s của G. 
ƒ Mỡi cạnh u* của G’ nối 2 đỉnh của G’ tương ứng với 2 vùng kề nhau 
và cắt cạnh chung của hai vùng đó. 
G’ được xây dựng như trên là một đồ thị phẳng, và cũng không có đỉnh cô lập. 
Chú ý : Đối ngẫu của G’ là G. 
™ HỆ QUẢ. 
Trong tất cả các bản đồ địa dư, có ít nhất một mặt có đường biên có số 
cạnh ≤ 5. 
Chứng minh. 
Chuyển bản đồ địa dư thành đồ thị đối ngẫu. Giả thiết trở thành « có it nhất một 
đỉnh có bậc 5 ≤ ». áp dụng Hệ quả 4.2.3. suy ra kết luận của hệ quả trên. 
™ ĐỊNH LÝ 4 MÀU. 
Mọi đồ thị phẳng có sắc tố γ (G) ≤ 4. 
Simpo PDF Merge and Split Unregistered Version -