Chuyên đề Một số yếu tố của lí thuyết đồ thị và ứng dụng

1 
GIẢNG DẠY CHUYÊN ĐỀ 
“MỘT SỐ YẾU TỐ CỦA LÍ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG” 
cho học sinh các lớp chuyên Toán trường THPT chuyên 
(Bài giảng tại Lớp tập huấn giáo viên chuyên Toán - Đợt 2) 
 Nguyễn Khắc Minh 
 (Cục Khảo thí và Kiểm định CLGD - Bộ GD&ĐT) 
 Theo quy định của Bộ GD&ĐT, chuyên đề “Một số yếu tố của lí thuyết đồ thị và 
ứng dụng” là một chuyên đề cần được giảng dạy cho học sinh các lớp chuyên Toán 
trường THPT chuyên trên phạm vi toàn quốc. 
1. Nội dung tối thiểu cần giảng dạy 
 Theo các văn bản chỉ đạo chuyên môn của Bộ GD&ĐT, đối với Chuyên đề nêu 
trên giáo viên cần giảng dạy cho học sinh các kiến thức tối thiểu dưới đây: 
 a. Các khái niệm cơ bản: Đồ thị; đỉnh, đỉnh cô lập, cạnh vô hướng, cạnh có 
hướng của đồ thị; đồ thị có hướng; đồ thị đơn vô hướng hữu hạn; đồ thị đầy đủ; đồ 
thị bù; phần của đồ thị (còn được gọi là “đồ thị con” trong một số tài liệu), đồ thị 
con (còn được gọi là “đồ thị con cảm sinh” trong một số tài liệu); bậc của đỉnh trong 
đồ thị đơn vô hướng hữu hạn; đồ thị thuần nhất; đường đi, độ dài đường đi, đường 
đi khép kín, xích (có tài liệu gọi là đường đi đơn giản), xích đơn, chu trình (có tài 
liệu gọi là chu trình đơn giản), chu trình đơn, đường đi Ơle, đường đi Hamintơn, chu 
trình Ơle, chu trình Hamintơn trong đồ thị đơn vô hướng hữu hạn; đồ thị liên thông, 
cây, đồ thị Ơle, đồ thị Hamintơn; thành phần liên thông của đồ thị đơn vô hướng 
hữu hạn; đồ thị lưỡng phân (còn được gọi là “đồ thị hai phe” trong một số tài liệu). 
 b. Một số kết quả đơn giản 
  Định lí 1. Số đỉnh bậc lẻ trong một đồ thị đơn vô hướng hữu hạn là một số chẵn. 
  Định lí 2. Trong đồ thị đơn vô hướng n đỉnh (n  Z, n  2) tồn tại ít nhất hai 
đỉnh có cùng bậc. 
  Định lí 3. Nếu đồ thị G đơn vô hướng n đỉnh (n  Z, n  2) có đúng hai đỉnh 
cùng bậc thì G phải có đúng một đỉnh bậc 0 hoặc đúng một đỉnh bậc n – 1. 
  Định lí 4. Mỗi đồ thị đơn vô hướng hữu hạn không liên thông đều bị phân chia 
một cách duy nhất thành các thành phần liên thông. 
  Định lí 5. Nếu mỗi đỉnh của đồ thị G đơn vô hướng n đỉnh (n  Z, n  2) đều có 
bậc không nhỏ hơn n/2 thì G là đồ thị liên thông. 
  Định lí 6. Đồ thị G đơn vô hướng hữu hạn là đồ thị Ơle khi và chỉ khi hai điều 
kiện sau được đồng thời thoả mãn: 
 i) G là đồ thị liên thông. 
 ii) Mọi đỉnh của G đều có bậc chẵn. 
  Định lí 7. Nếu tất cả các cạnh của một đồ thị đơn vô hướng đầy đủ 6 đỉnh được 
tô bởi hai màu thì phải tồn tại ít nhất một chu trình đơn độ dài 3 có tất cả các cạnh 
cùng màu. 
2 
2. Nội dung nâng cao nên giảng dạy 
  Các kết quả lí thuyết đã được trình bày trong Bài giảng của PGS. TS. Phan Thị 
Hà Dương tại Lớp tập huấn. 
  Về tính liên thông của đồ thị 
 - Định lí 1.1: Nếu G là đồ thị đơn, vô hướng, có n đỉnh và k thành phần liên thông 
thì số cạnh tối đa trong G bằng 
1
( , ) ( )( 1)
2
S n k n k n k    . 
 - Định lí 1.2: Nếu G là đồ thị đơn, vô hướng, có n đỉnh và có số cạnh lớn hơn 
1
( ,2) ( 2)( 1)
2
S n n n   
thì G là đồ thị liên thông. 
  Về đồ thị Hamintơn 
 Xét đồ thị G đơn, vô hướng, n đỉnh. Kí hiệu các đỉnh của G bởi 1 2, ,..., na a a và kí 
hiệu ( ,i ja a ) là cạnh có hai đầu mút là ia và ja . 
 Bậc của đỉnh ia được kí hiệu bởi ( )id a . 
 Xét xích đơn A có độ dài l; không mất tổng quát, giả sử A = 1 2 1... la a a  . 
 - Định nghĩa: A được gọi là xích đơn đầy đủ nếu không thể kéo dài A bằng cách 
thêm vào A các cạnh liên thuộc đỉnh 1a hoặc đỉnh 1la  . 
 - Định lí 2.1: Nếu xích đơn đầy đủ A độ dài l có các đầu mút 1a , 1la  thỏa mãn 
điều kiện 
1 1( ) ( ) 1ld a d a l   
thì đồ thị con cảm sinh 0G của G, với tập đỉnh { 1 2 1, ,..., la a a  }, là đồ thị Hamintơn. 
 - Định lí 2.2: Giả sử G là đồ thị liên thông. Khi đó, hoặc G là đồ thị Hamintơn 
hoặc độ dài l của xích đơn có độ dài lớn nhất trong G thỏa mãn bất đẳng thức 
1 1( ) ( )ll d a d a   , 
trong đó 1a và 1la  là các đầu mút của xích đơn đó. 
 - Hệ quả: Giả sử đồ thị G không có chu trình Hamintơn. Khi đó, nếu ia và ja là 
hai đỉnh có bậc nhỏ nhất trong G thì ( ) ( )i jl d a d a  , với l là độ dài của xích đơn 
có độ dài lớn nhất trong G. 
 - Định lí 2.3 (Dấu hiệu Dirac): Nếu bậc (trong G) của mỗi đỉnh đều lớn hơn hoặc 
bằng 
2
n
 thì G là đồ thị Hamintơn. 
 - Định lí 2.4 (Dấu hiệu Ore): 
 + Nếu với hai đỉnh tùy ý ia và ja đều có 
( ) ( ) 1i jd a d a n   
thì G có đường đi Hamintơn. 
3 
 + Nếu với hai đỉnh tùy ý ia và ja đều có 
( ) ( )i jd a d a n  
thì G có chu trình Hamintơn. 
  Về đồ thị lưỡng phân và bài toán ghép cặp 
 - Định lí 3.1: Đồ thị G đơn, vô hướng, hữu hạn là đồ thị lưỡng phân khi và chỉ khi 
mọi chu trình đơn trong G đều có độ dài chẵn. 
 - Định lí 3.2: Định lí Hall. 
3. Phương pháp giảng dạy 
  Các giáo viên nên dẫn dắt học sinh đến các khái niệm, các kết quả thông qua 
các bài toán cụ thể được phát biểu bằng ngôn ngữ đời sống. 
 Lưu ý: Nhằm tránh sự đơn điệu trong việc dẫn dắt học sinh tới khái niệm “đồ thị” 
hay một số khái niệm khác như “đường đi trong đồ thị”, …, các giáo viên nên tìm 
đến các bài toán vui, các bài toán cổ có bản chất đồ thị mà học sinh đã biết trong quá 
trình học tập từ cấp Tiểu học. 
 - Ví dụ 1: Giáo viên có thể dẫn dắt học sinh tới khái niệm “đồ thị” cũng như khái 
niệm “đường đi trong đồ thị” thông qua bài toán vui sau: 
 Bài toán 1: Trên một bờ sông có một con sói, một con dê và một cái bắp cải. Một 
bác lái đò phải chở cả sói, dê và bắp cải sang sông. Mỗi lần sang sông, bác chỉ chở 
được đúng một trong ba đối tượng trên. Hơn nữa, bác lái đò phải đảm bảo không 
được để lại trên bờ sông chỉ có sói và dê, cũng như chỉ có dê và bắp cải. Hỏi bác lái 
đò phải chở sói, dê và bắp cải sang sông bằng cách nào ? 
 - Ví dụ 2: Để dẫn dắt học sinh tới dấu hiệu Dirac hay dấu hiệu Ore về đồ thị 
Hamintơn, giáo viên có thể xuất phát từ bài toán đơn giản sau: 
 Bài toán 2: Có 6 loại sợi, mỗi loại sợi có một màu và hai loại sợi khác nhau có 
màu khác nhau. Từ các loại sợi đó, người ta dệt nên các tấm vải hai màu. Biết rằng, 
trong quá trình dệt, mỗi loại sợi đều được ghép với tối thiểu ba loại sợi khác. Chứng 
minh rằng có thể chọn ra được 3 tấm vải mà ở 3 tấm vải đó có đầy đủ cả 6 loại sợi. 
  Đối với việc giảng dạy các kết quả hay các bài tập, các giáo viên không nên 
trình bày ngay chứng minh của các kết quả hay lời giải của các bài tập đó, mà nên 
có bước phân tích dẫn dắt học học sinh tới các chứng minh hay lời giải. Qua đó, 
giáo viên giúp học sinh rèn luyện kĩ năng phân tích cấu trúc của đồ thị, … . 
4. Một số kết quả tham khảo 
 Cho G là đồ thị đơn, vô hướng, hữu hạn. Kí hiệu M(n, G) là số cạnh lớn nhất của 
một đồ thị đơn, vô hướng, có n đỉnh và không nhận G làm đồ thị con cảm sinh. 
 Kí hiệu nK là đồ thị đơn, vô hướng, đầy đủ, có n đỉnh. 
 Kí hiệu ,m nK là đồ thị đơn, vô hướng, lưỡng phân, đầy đủ, có số đỉnh của mỗi 
phần tương ứng là m và n. 
  Kết quả 4.1 (Định lí Turan): 
2
3( , )
4
n
M n K
 
  
 
. 
4 
  Kết quả 4.2: Số cạnh lớn nhất của đồ thị đơn, vô hướng, n đỉnh và trong đó 
không có hai chu trình đơn độ dài 3 có chung cạnh bằng 
2
4
n 
 
 
. 
  Kết quả 4.3: 2,2
(1 4 3)
( , )
4
n n
M n K
 
 . 
  Kết quả 4.4: 2,
(1 1 4( 1)( 1))
( , )
4
m
n m n
M n K
   
 . 
  Kết quả 4.5: 
1 1
2
,
1
( , ) ( 1) .
2 4
m m
l m
mn
M n K l n

   . 
  Kết quả 4.6: Tồn tại vô hạn số nguyên dương n sao cho 
3 3
2, 1( , )
2 4 2 4
m
mn mn mn mn
M n K     . 
  Kết quả 4.7: Tồn tại vô hạn số nguyên dương n sao cho 
3
2, 1( , )
2
m
mn
M n K mn   . 
  Kết quả 4.8: Với p là số nguyên tố lẻ, ta luôn có 
5 4
3
3,3( , )
2
p p
M p K

 .