Đại số lý thuyết đồ thị

ĐẠI SỐ 
LÝ THUYẾT ĐỒ THỊ 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 1 
CHƯƠNG 1. 
CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ. 
1.1 ĐỊNH NGHĨA & THÍ DỤ. 
1.1.1 ĐỊNH NGHĨA. 
1.1.1.1 Đồ thị có định hướng. 
Một đồ thị G = G(X,U) được xác định bởi 
§ Tập hữu hạn X = {x 1,x2,, xn} tập các đỉnh hay nút. 
§ Tập U = {u 1,u2,,u n} Ì X x X tập các cung (cạnh). 
Đối với một cung u = (x i, xj), xi là đỉnh đi, xj là đỉnh đến (hay còn gọi là gốc và 
đích). Cung u đi từ xi và đến xj. 
Cung u dược biểu diễn một cách hình học như sau : 
 xi xj 
 FIG.1.1. Cung u=(x i, xj) 
Một cung (x i, xi) được gọi là một vòng (khuyên). 
Một p-đồ thị là một đồ thị trong đó không có quá p cung dưới dạng (i,j) giữa hai 
đỉnh bất kỳ. 
Thí dụ. 
 x1 u4 x4 u8 
 u7 
 u1 
 u3 u5 x5 
 u6 
 x2 u2 x3 
 FIG. 1.2. Đồ thị xác định bởi (X,U), 
 X = {x1, x 2, x3, x4, x5} ; U = {u1, u2, u3, u 4, u5, u6, u 7, u8} 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 2 
1.1.1.2 Đồ thị không định hướng. 
Khi khảo sát một vài tính chất, sự định hướng của các cung không đóng một vai 
trò gì. Ta chỉ quan tâm đến sự hiện diện của các cung giữa hai đỉnh mà thôi 
(không cần định rõ thứ tự). Một cung không định hướng được gọi là cạnh. Đối với 
một cạnh u = (xi,xj), u được gọi là CẠNH TỚI của hai đỉnh xi và xj. 
Thí dụ. 
 x1 u6 x4 
 u7 
 u1 u2 u3 u4 x5 
 u8 
 x2 u5 x3 
 FIG. 1.3. Đồ thị xác định bởi (X,U), 
 X = {x 1, x2, x 3, x4, x 5} ; U = {u1, u 2, u3, u4, u 5, u6, u7, u8} 
Một đồ thị được gọi là đa đồ thị nếu có nhiều hơn một cạnh giữa hai đỉnh. 
Một đồ thị được gọi là đơn nếu: 
1. Không phải là đa đồ thị ; 
2. Không tồn tại một vòng nào. 
Hai cạnh u và v được gọi là song song khi chúng cùng là cạnh tới của hai đỉnh 
phân biệt. Ký hiệu u ¦ v. 
Theo thí dụ trên, ta có u1 ¦ u2 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 3 
1.1.1.3 Một số định nghĩa cơ bản. 
§ ÁNH XẠ ĐA TRỊ. 
v x j được gọi là ĐỈNH SAU (SUCCESSEUR) của xi nếu (x i,x j) Ỵ U; 
Tập các đỉnh sau của x i ký hiệu là G(xi). 
v x j được gọi là ĐỈNH TRƯỚC (PREDECESSEUR) của xi nếu 
(xj,xi) Ỵ U; Tập các đỉnh trước của xi ký hiệu là G-1(xi). 
v Aùnh xạ G được định nghĩa :với mọi phần tử của X, tương ứng với một 
tập con của X được gọi là một ÁNH XẠ ĐA TRỊ. 
v Đối với một 1-đồ thị, G có thể hoàn toàn xác định bởi (X,G), đây là một 
ký hiệu cơ sở thường dùng trong cấu trúc dữ liệu : DANH SÁCH KỀ. 
THÍ DỤ. Trong đồ thị được định nghĩa ở hình vẽ sau. X = {x1,x2,x3,x4,x5}; 
G(x1) = x2 ; G(x2) = {x3,x4} ; G(x3)={x4,x5} ; G(x 4)={x 1} ; G(x 5)={x4}. 
 x1 x4 
 x5 
 x2 x3 
 FIG. 1.4. Đồ thị xác định bởi (X,G) 
§ KỀ. 
v Hai đỉnh được gọi là kề nếu chúng được nối bởi một cung (cạnh). 
v Hai cung (cạnh) được gọi là kề nếu chúng có ít nhất một đỉnh chung. 
§ BẬC CỦA ĐỈNH. 
v Nửa bậc ngoài của đỉnh x i , ký hiệu d+(xi) là số các cung khởi đầu từ 
(hay đi ra từ) x i . Ta có d+(xi) = card (G(x i)). (ký hiệu card(A) chỉ số 
phần tư û của tập A). 
v Nửa bậc trong của đỉnh xi , ký hiệu d-(xi) là số các cung kết thúc tại 
(hay đi vào từ) xi . Ta có d-(xi)=card(G-1(xi)). 
v Bậc của đỉnh x i , d(x i) = d +(x i) + d-(xi). Bậc của một đỉnh trong một 
đồ thị không định hướng là tổng số các cạnh tới của nó. 
Bậc của một đỉnh có vòng được cộng thêm 2 cho mỗi vòng. 
THÍ DỤ. [xem FIG. 1.4]. 
d+(x 2)= 2 ; d-(x2)= 1 ; d(x 2)=3. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 4 
d+(x 4)= 1 ; d-(x4)= 3 ; d(x 4)=6. (Vì tại đỉnh x4 có một vòng). 
v Đỉnh có bậc = 0 được gọi là đỉnh cô lập. 
v Đỉnh có bậc = 1 được gọi là đỉnh treo và cung (cạnh) tới của nó 
được gọi là cạnh treo. 
v ĐỊNH LÝ (công thức liên hệ giữa bậc và số cạnh). 
1. Tổng bậc các đỉnh = 2 x số cạnh. 
2. Xét đồ thị có định hướng G = (X, U). Ta có 
 å d+(x) = å d-(x) = card(U) (số cung). 
CHỨNG MINH. Truy chứng theo đỉnh. 
v HỆ QUẢ. Số đỉnh bậc lẻ là số chẳn. 
CHỨNG MINH. 
 å d(đỉnh bậc lẻ) + å d(đỉnh bậc chẳn) = 2 x số cạnh. 
§ ĐỒ THỊ BÙ. 
G = (X, U) và `G = (X,`U). (xi,xj) Ỵ U Þ (xi,xj) Ï `U et (x i,x j) ÏU 
Þ (xi,xj) Ỵ`U. 
`G được gọi là đồ thị bù của G. 
§ ĐỒ THỊ RIÊNG PHẦN (BỘ PHẬN). 
G=(X,U) và U p Ì U. G p=(X,U p) là một đồ thị riêng phần của G ; 
§ ĐỒ THỊ CON. 
G=(X,U) và X s Ì X. G s=(X s,V) là một đồ thị con của G; trong đó 
V là thu hẹp của hàm đặc trưng của U trên Xs. 
V={(x,y)/(x,y) Ỵ UÇXs x X s}. "x i Ỵ Xs, Gs(xi)=G(xi)ÇXs. 
§ ĐỒ THỊ CON RIÊNG PHẦN. Tổng hợp hai định nghĩa trên. 
THÍ DỤ. Mạng giao thông đường bộ cả nước. 
v Mạng xe bus : đồ thị riêng phần. 
v Mạng giao thông đường bộ T.P. Hồ Chí Minh: đồ thị con. 
v Mạng xe bus T.P. Hồ Chí Minh: đồ thị con riêng phần. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 5 
§ ĐỒ THỊ đối xứng : (x i,x j) Ỵ U Þ (xi,xi) Ỵ U. 
§ ĐỒ THỊ phản đối xứng : (x i,x j) Ỵ U Þ (xj,xi) Ï U. 
§ ĐỒ THỊ phản chiếu : (x i,x i) Ỵ U, " x i Ỵ U. 
§ ĐỒ THỊ bắc cầu : (xi,xj) Ỵ U, (x j,xk) Ỵ U Þ (x i,xk) Ỵ U. 
§ ĐỒ THỊ đầy đủ : (x i,xj) Ï U Þ (xj,xi) Ỵ U (có duy nhất một cạnh 
giữa hai đỉnh). Một đồ thị đủ có n đỉnh sẽ có n(n-1)/2 cạnh. Ký hiệu Kn. 
§ CLIQUE :Tập các đỉnh của một đồ thị con đầy đủ. 
§ ĐỒ THỊ HAI PHẦN (LƯỠNG PHÂN) G=(X,U) nếu : 
1. X phân hoạch thành X1 và X2. 
2. " (x1,x2) Ỵ U thì x1 Ỵ X1, x2 Ỵ X2. 
Nếu Card(X1) = n, Card(X 2) = m, ký hiệu Kn,m . 
Thí dụ : Đồ thị sau lưỡng phân, nhưng không đầy đủ. 
 K2,2 K3,2 
§ ĐỀU. Là đồ thị mà mọi đỉnh có cùng bậc. 
THÍ DỤ. 
 x2 
 x1 x4 
 x3 
 FIG. 1.5. Đồ thị phản chiếu , phản đối xứng, bắc cầu và đầy đủ. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 6 
1.1.2 THÍ DỤ. 
§ THÍ DỤ 1. Đường đi ngắn nhất. 
Bài to án 1. Cho một đồ thị có định hướng, G = (X,U), một định giá 
v : U ® R và s, t là hai đỉnh phân biệt của X. 
Bài toán đặt ra . Tìm đường đi ngắn nhất giữa s và t ? 
Lời giải. Thuật giải Dijkstra, Bellman-Ford (xem Chương 3). 
` 
§ THÍ DỤ 2. Cây phủ tối thiểu. 
Xét bài toán trên một mạng, chẳng hạn mạng cung cấp điện, nước từ một 
nguồn duy nhất. 
Bài toán 2. Một đồ thị không định hướng G = (X,U), một hàm định giá trọng 
lươ ïng v : U ® R+ và hai đỉnh phân biệt s, t của X. 
Bài toán đặt ra . Tìm một cây phủ với trong lượng tối thiểu ? 
Lời giải : Thuật giải Kruskal, Prim (xem Chương 2). 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 7 
1.2 BIỂU DIỄN ĐỒ THỊ. 
Có rất nhiều cách đe å biểu diễn đồ thị. Tuy nhiên, các cách biểu diễn này không 
tương đương với nhau theo quan điểm của các thuật toán. Người ta, phân biệt một vài 
cách biểu diễn chính, chẳng hạn biểu diễn bằng ma trận kề, ma trận tới đỉnh – cung 
(hay đỉnh – cạnh trong trường hợp không định hướng) và bằng danh sách kề. 
1.2.1 Biểu diễn bằng cách sử dụng các Bảng. 
1.2.1.1. Ma trận kề. 
Xét một 1 - đồ thị có n đỉnh. Ma trận kề là một ma trận (n x n) có n hàng tương ứng 
với các đỉnh khởi đầu và n cột tương ứng với các đỉnh kết thúc, được định nghĩa như 
sau : 
 xij = 1 (True) nếu có một cung (cạnh) nối x i và xj. 
 = 0 (False) ngược lại. 
THÍ DỤ. x2 
 u2 u1 u4 
 x1 u3 x3 
 FIG.1.6. 1. Đồ thị. 
Ma trận kề của đồ thị này như sau : 
 x1 x2 x3 ¬ kết thúc 
x1 0 1 1 
x2 1 0 1 
x3 0 0 0 
 ­ 
 khởi đầu 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 8 
1.2.1.2. Ma trận tới đỉnh – cung (đỉnh – cạnh). 
v Dòng « đỉnh. 
v Cột « cung (cạnh). 
Cho đồ thị G = (X, U). Một ma trận tới A = [aij]] được định nghĩa như sau : 
Nếu cạnh u = (x i, xj) Ỵ U thì trên cột u, aiu = 1, aju = -1, ngược lại thì có giá trị 0. 
THÍ DỤ. Đối với 1. Đồ thị ở hình FIG .1.6. ta có : 
 U1 u2 u3 u4 
x1 1 -1 1 0 
x2 -1 1 0 1 
x3 0 0 -1 -1 
CHÚ Ý : Tổng các dòng bằng không (một cung có đỉnh gốc và một đỉnh kết thúc). 
Tất cả các ma trận con vuông đều có định thức bằng 1, -1 hay 0. 
Có một cách khác cho ma trận tới như sau : 
Cho đồ thị G = (X, U). Một ma trận tới A = [aij]] được định nghĩa như sau : 
 aiu = 1 nếu u = (x i,xj) Ỵ U 
 = 0 ngược lại. 
THÍ DỤ. Đối với 1. Đồ th ị ở hình FIG .1.6. ta có : 
 u1 u2 u3 u4 
x1 1 0 1 0 
x2 0 1 0 1 
x3 0 0 0 0 
CHÚ Ý : Tổng các dòng bằng số các cung tới. 
1.2.2 Biểu diễn bằng cách sử dụng các con trỏ. 
Lợi ích của cách biểu diễn bằng con trỏ hay Danh sách kề (nhờ vào ánh xạ đa trị G) là 
giảm thiểu chổ trong bộ nhớ. 
THÍ DỤ. Đối với 1.đồ thị của hình FIG.1.6. ta có : 
x1 x2 x3 
x2 x1 x3 
x3 
z 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 9 
1.3 PHÉP DUYỆT ĐỒ THỊ. (Parcours de graphes). 
Nhiều bài toán trên đồ thị cần khảo sát sự vét kiệt các đỉnh và các cung 
(cạnh) của đồ thị. Có 2 cách duyệt đồ thị : phép duyệt theo chiều sâu (Parcours 
en profondeur) và phép duyệt theo chiều rộng (Parcours en largeur). 
1.3.1. DUYỆT THEO CHIỀU SÂU. 
NGUYÊN LÝ : 
Khởi từ một đỉnh, đi theo các cung (ca ïnh) xa nhất có thể. Trở lại đỉnh sau 
của cạnh xa nhất, tiếp tục duyệt như trước, cho đến đỉnh cuối cùng. 
Thí dụ. Ta có đồ thị theo hình vẽ sau : 
 s7 s1 s5 s8 
 s6 s3 s2 s4 
 s9 
 FIG. 1.7. 
Phép duyệt theo chiều sâu thực hiện trên đồ thị ở hình FIG.1.7 như sau : 
§ Khởi từ đỉnh s1. Đỉnh đầu tiên được duyệt là s3. 
§ Khởi từ đỉnh s3. Đỉnh được duyệt là s2. Đỉnh sau của s3 là s6. 
§ Khởi từ đỉnh s6. Đỉnh sau của s1 là s5. 
§ Khởi từ đỉnh s5. Đỉnh sau của s1 là s7. 
§ Khởi từ đỉnh s7. 
§ Khởi từ đỉnh s4. Đỉnh được duyệt là s9. 
§ Khởi từ đỉnh s8. 
§ Kết thúc vì tất cả các đỉnh đã được duyệt. 
Simpo PDF Merge and Split Unregistered Version - 
Chương 1. Các Khái niệm cơ bản về Đồ thị. 
Trương Mỹ Dung 10 
Ký hiệu : 
s[k], k : 1..n là tập đỉnh có n phần tử, được đánh số thứ tự từ 1 đến n. 
Mark[k], k : 1..n là hàm nguyên : 
= 1 nếu đỉnh đã được duyệt (có nghĩa đã được đánh dấu), 
= 0 ngược lại. 
Ma  ...  đượ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 -