Tóm tắt luận văn Bài toán tô màu đồ thị và ứng dụng

Nội dung text: Tóm tắt luận văn Bài toán tô màu đồ thị và ứng dụng

1. 1 BỘ GIÁO D ỤC VÀ ĐÀO T ẠO ĐẠI H ỌC ĐÀ N ẴNG NGUY ỄN THANH S ƠN BÀI TỐN TƠ MÀU ĐỒ TH Ị VÀ ỨNG D ỤNG Chuyên ngành: Ph ươ ng pháp Tốn s ơ c ấp Mã s ố: 60 46 40 TĨM T ẮT LU ẬN V ĂN TH ẠC S Ĩ KHOA H ỌC Đà N ẵng - N ăm 2011
2. 2 Cơng trình được hồn thành t ại ĐẠI H ỌC ĐÀ N ẴNG Ng ười h ướng d ẫn khoa h ọc: PGS-TSKH Tr ần Qu ốc Chi ến Ph ản bi ện 1: TS. Cao V ăn Nuơi Ph ản bi ện 2: TS. Hồng Quang Tuy ến Lu ận v ăn s ẽ được b ảo v ệ trước H ộ i đồng ch ấm Lu ận v ăn t ốt nghi ệp th ạc sĩ khoa h ọc h ọp t ại Đại h ọc Đà N ẵng vào ngày 17 tháng 8 năm 2011 Cĩ th ể tìm hi ểu lu ận v ăn t ại: - Trung tâm Thơng tin-Học li ệu, Đạ i h ọc Đà N ẵng - Th ư vi ện tr ường Đại h ọc S ư Ph ạm, Đại h ọc Đà N ẵng
3. 3 MỞ ĐẦU 1. Lí do ch ọn đề tài: Lý thuy ết đồ th ị là m ột ph ần c ủa ngành tốn h ọc hi ện đại, được phát tri ển t ừ lâu nh ưng l ại cĩ nhi ều ứng d ụng hi ện đại, nĩ khá “g ần gũi” v ới th ực t ế. Trong ch ươ ng trình THPT, sách giáo khoa trang b ị cho h ọc sinh các ki ến th ức v ề tơ màu đồ th ị cịn ít, đặc bi ệt là bài tốn tơ màu đồ th ị để ph ục v ụ cho vi ệc b ồi d ưỡng h ọc sinh, h ơn n ữa các bài tốn gi ải bằng ph ươ ng pháp tơ màu đồ th ị r ất g ần v ới th ực t ế. Vì v ậy, chuyên đề này ch ứa đựng nhi ều ti ềm n ăng để khai thác b ồi d ưỡng cho h ọc sinh. Vi ệc cung c ấp m ột s ố ph ươ ng pháp gi ải bài tốn b ằng ph ươ ng pháp tơ màu đồ th ị là m ột nhu c ầu c ần thi ết. M ặt khác, vi ệc v ận d ụng kết qu ả bài tốn tơ màu đồ th ị vào gi ải tốn giúp ta đạt được m ục tiêu: gi ải được m ột s ố bài tốn khơng m ẫu m ực, các bài tốn th ường g ặp trong th ực t ế và r ải rác m ột s ố bài tốn trong các kì thi tuy ển Olympic tốn qu ốc t ế. Nghiên c ứu khai thác m ột s ố y ếu t ố c ủa bài tốn tơ màu đồ th ị và ứng d ụng này trong vi ệc gi ải các bài tốn ở ph ổ thơng, c ũng được m ột số tác gi ả quan tâm, xu ất phát t ừ nh ững lý do trên tơi l ựa ch ọn đề tài: “Bài tốn tơ màu đồ th ị và ứng d ụng ” để nghiên c ứu. 2. M ục đích nghiên c ứu: 3. Đối t ượng và ph ạm vi nghiên c ứu: 4. Phươ ng pháp nghiên c ứu: 5. Ý ngh ĩa khoa h ọc và th ực tiễn c ủa đề tài: 6. C ấu trúc lu ận v ăn: Lu ận v ăn g ồm 3 ch ươ ng:
4. 4 Ch ươ ng 1. Các khái ni ệm c ơ b ản c ủa lý thuy ết đồ th ị: Trình bày nh ững ki ến th ức c ơ b ản c ủa lý thuy ết đồ th ị. Ch ươ ng 2. Bài tốn tơ màu đồ th ị: Nghiên cứu sâu các định lí v ề tơ màu đỉnh, tơ màu c ạnh, các định lí v ề tơ màu đồ th ị ph ẳng và các bài tốn tơ màu đỉnh, tơ màu cạnh. Ch ươ ng 3. Ứng d ụng: Trình bày các ứng d ụng c ủa bài tốn tơ màu đồ th ị trong vi ệc gi ải các bài tốn ph ổ thơng và các v ấn đề th ực t ế.
5. 5 CH ƯƠ NG 1 CÁC KHÁI NI ỆM C Ơ B ẢN CỦA LÝ THUY ẾT ĐỒ TH Ị. 1.1. CÁC KHÁI NI ỆM V Ề ĐỒ THỊ: 1.1.1 Các định ngh ĩa: Định ngh ĩa 1.1.1.1: Đồ th ị vơ h ướng G = (V,E) g ồm m ột t ập V các đỉnh và t ập E các c ạnh. Mỗi c ạnh e∈E được liên k ết v ới m ột c ặp đỉnh (v, w) (khơng k ể th ứ t ự) Định ngh ĩa 1.1.1.2: Đồ th ị cĩ h ướng G = (V,E) g ồm m ột t ập V các đỉnh và t ập E các c ạnh cĩ h ướng g ọi là cung. Mỗi c ạnh e ∈E được liên k ết v ới m ột c ặp đỉnh (v, w) (cĩ th ứ t ự) Ghi chú: Cho đồ th ị cĩ h ướng G = (V,E). N ếu ta thay m ỗi cung c ủa G bằng m ột c ạnh, thì đồ th ị vơ h ướng nh ận được g ọi là đồ th ị lĩt c ủa G. Đồ th ị vơ h ướng cĩ th ể coi là đồ th ị cĩ h ướng trong đĩ m ỗi cạnh e = (v,w) t ươ ng ứng v ới hai cung (v,w) và (w,v). 1.1.2 Các khái ni ệm: 1.1.3 Các lo ại đồ th ị: Định ngh ĩa 1.1.3.1: Đồ th ị h ữu h ạn. Định ngh ĩa 1.1.3.2: Đồ th ị đơ n. Định ngh ĩa 1.1.3.3: Đồ th ị vơ h ướng đủ. Định ngh ĩa 1.1.3.4: Đồ th ị K n là đơ n đồ th ị vơ h ướng đủ n đỉnh. Định ngh ĩa 1.1.3.5: Đồ th ị cĩ h ướng đủ. Định ngh ĩa 1.1.3.6: Đồ th ị l ưỡng phân G = (V,E), Ký hi ệu: G = ({V 1, V 2}, E). Định ngh ĩa 1.1.3.7: Đồ th ị K m,n là đồ th ị l ưỡng phân ({V 1, V 2}, E) v ới t ập V 1 cĩ m đỉnh và t ập V 2 cĩ n đỉnh và m ỗi đỉnh của V 1 được n ối v ới m ỗi đỉnh c ủa V 2 b ằng m ột c ạnh duy nh ất.
6. 6 Định ngh ĩa 1.1.3.8: Đồ th ị G g ọi là đồ th ị thu ần nh ất b ậc a (a ∈ N), n ếu m ỗi đỉnh đều cĩ b ậc a. 1.1.4 Bi ểu di ễn đồ th ị b ằng hình h ọc: a) Bi ểu di ễn đỉnh: b) Bi ểu di ễn c ạnh: c) Bi ểu di ễn cung: 1.1.5 B ậc, n ửa b ậc vào, n ửa b ậc ra: Cho đồ thi G = (V, E). Định ngh ĩa 1.1.5.1: Bậc c ủa đỉnh v ∈V. Định ngh ĩa 1.1.5.2: Đỉnh treo là đỉnh cĩ b ậc b ằng 1. Định ngh ĩa 1.1.5.3: Cho G = (V,E) là đồ th ị cĩ h ướng, v ∈V. Nửa b ậc ra c ủa đỉnh v, ký hi ệu d 0(v), là s ố cung đi ra t ừ đỉnh v (v là đỉnh đầu). N ửa b ậc vào c ủa đỉnh v ∈V, ký hi ệu d 1(v), là s ố cung đi t ới đỉnh v (v là đỉnh cu ối). Định ngh ĩa 1.1.5.4: Đồ th ị K n là đồ th ị đơ n, đủ n đỉnh. Bổ đề 1.1.5.5: (B ổ đề b ắt tay- Hand Shaking Lemma) Cho đồ th ị G = (V, E). Khi đĩ: i) Tổng b ậc các đỉnh c ủa đồ th ị là s ố ch ẵn và ∑ dv()= 2.ar cdE ( ) v∈ V ii) N ếu G là đồ th ị cĩ h ướng thì: = = ∑dv() ∑ dv () cdE ar() vV∈0 vV ∈ 1 Trong đĩ card(E), kí hi ệu s ố ph ần t ử c ủa t ập X. Hệ qu ả 1.1.5.6: S ố đỉnh b ậc l ẻ c ủa đồ th ị vơ h ướng là s ố ch ẵn. Mệnh đề 1.1.5.7: Mỗi đỉnh c ủa đồ th ị K n cĩ b ậc n – 1 và K n cĩ − n ( n 1) cạnh. Mệnh2 đề 1.1.5.8: Cho đồ th ị l ưỡng phân đủ
7. 7 Km,n = ({V 1, V 2}, E) v ới t ập V 1 cĩ m đỉnh và t ập V 2 cĩ n đỉnh. Khi đĩ mỗi đỉnh trong V 1 cĩ b ậc là n, m ỗi đỉnh trong V 2 cĩ b ậc là m và K m,n cĩ m.n c ạnh. 1.2. ĐƯỜNG ĐI, CHU TRÌNH VÀ TÍNH LIÊN THƠNG: 1.2.1 Các định ngh ĩa: Cho đồ th ị G = (V,E). Định ngh ĩa 1.2.1.1: Dây µ t ừ đỉnh v đến đỉnh w là dãy các đỉnh và c ạnh n ối ti ếp nhau b ắt đầu t ừ đỉnh v đến k ết thúc t ại đỉnh w. Số c ạnh trên dây µ g ọi là độ dài c ủa dây µ . Dây µ t ừ đỉnh v đến đỉnh w độ dài n được bi ểu di ễn nh ư sau: µ = (v, e 1, v 1, e 2, v2, , v n-1, e n, w) Trong đĩ v i (i = 1, , n-1) là các đỉnh trên dây và ei (i = 1, ,n) là các c ạnh trên dây liên thu ộc đỉnh k ề tr ước và sau nĩ. Các đỉnh và c ạnh trên dây cĩ th ể l ặp l ại. Định ngh ĩa 1.2.1.2: Đường đi t ừ đỉnh v đến đỉnh w. Định ngh ĩa 1.2.1.3: Đường đi s ơ c ấp. Định ngh ĩa 1.2.1.4: Vịng. Dây cĩ h ướng trong đồ th ị cĩ h ướng Định ngh ĩa 1.2.1.5: Đường đi cĩ h ướng trong đồ thị cĩ h ướng. Định ngh ĩa 1.2.1.6: Đường đi cĩ h ướng s ơ c ấp. Định ngh ĩa 1.2.1.7: Vịng cĩ h ướng. Định ngh ĩa 1.2.1.8: Chu trình. Định ngh ĩa 1.2.1.9: Chu trình s ơ c ấp. Định ngh ĩa 1.2.1.10: Chu trình cĩ h ướng. Định ngh ĩa 1.2.1.11: Chu trình cĩ h ướng s ơ c ấp. Định ngh ĩa 1.2.1.12: Đồ th ị vơ h ướng g ọi là liên thơng, n ếu mọi c ặp đỉnh c ủa nĩ đều cĩ đường đi n ối chúng v ới nhau. Định ngh ĩa 1.2.1.13: Đồ th ị cĩ h ướng g ọi là liên thơng m ạnh, nếu m ọi c ặp đỉnh c ủa nĩ đều cĩ đường đi cĩ h ướng n ối chúng v ới
8. 8 nhau. Định ngh ĩa 1.2.1.14: Đồ th ị cĩ h ướng g ọi là liên thơng y ếu, nếu đồ th ị lĩt (vơ h ướng) c ủa nĩ liên thơng. Định ngh ĩa 1.2.1.15: Đồ th ị cĩ h ướng g ọi là bán liên thơng, nếu v ới m ọi c ặp đỉnh (u, v) bao gi ờ c ũng t ồn t ại đường đi cĩ h ướng từ u đến v ho ặc t ừ v đến u. Định ngh ĩa 1.2.1.16: Cho đồ th ị G = (V, E). Đồ th ị G ’ = (V ’, E’) g ọi là đồ th ị con c ủa G n ếu V ’ ⊂ V và E ’ ⊂ E Định ngh ĩa 1.2.1.17: Đồ th ị con G ’ = (V ’, E ’) c ủa đồ th ị (cĩ hướng) G = (V, E) g ọi là thành ph ần liên thơng (m ạnh) c ủa đồ th ị G, nếu nĩ là đồ th ị con liên thơng (m ạnh) t ối đại c ủa G, t ức là khơng t ồn tại đồ th ị con liên thơng (m ạnh) G ’’ = (V ’’ , E ’’ ) ≠ G ’ c ủa G th ỏa V ’ ⊂ V ’’ , E ’ ⊂ E ’’ . 1.2.2 Các định lí: Định lí 1.2.2.1: i) Trong đồ th ị vơ h ướng m ỗi dãy t ừ đỉnh v đến w ch ứa đường đi sơ c ấp t ừ v đến w. ii) Trong đồ th ị cĩ h ướng m ỗi dãy cĩ h ướng đi t ừ đỉnh v đến w ch ứa đường đi cĩ h ướng s ơ c ấp t ừ đỉnh v đến w. Định lí 1.2.2.2: Đồ th ị G l ưỡng phân khi và ch ỉ khi G khơng ch ứa chu trình độ dài l ẻ. Định lí 1.2.2.3: Cho G = (V, E) v ới n đỉnh, và k thành ph ần liên thơng. Khi đĩ s ố c ạnh m c ủa đồ th ị th ỏa b ất đẳng th ức: (n− k )( n − k + 1) n− k ≤ m ≤ 2 Hệ qu ả 1.2.2.4: M ọi đơ n đồ th ị n đỉnh v ới s ố c ạnh − − ( n 1)( n 2) là liên thơng. 2 1.3. ĐỒ TH Ị PH ẲNG: 1.3.1 Các định ngh ĩa:
9. 9 Định ngh ĩa 1.3.1.1: M ột đồ th ị g ọi là đồ th ị hình h ọc ph ẳng n ếu nĩ được bi ểu di ễn trên m ặt ph ẳng sao cho các c ạnh khơng c ắt nhau. Định ngh ĩa 1.3.1.2: M ột đồ th ị g ọi là ph ẳng n ếu nĩ đẳng c ấu với đồ th ị hình h ọc ph ẳng. Định ngh ĩa 1.3.1.3: Hai đồ th ị G 1 = (V 1, E 1) và G2 = (V 2, E 2) g ọi là đẳng c ấu v ới nhau n ếu t ồn t ại song ánh f: V 1 → V2 và g: E 1 → E 2 th ỏa mãn ∀∈ = ⇔ = eEev1 : (,w) ge () ((), fvf (w)) cặp hàm f và g g ọi là m ột đẳng c ấu t ừ G 1 đến G 2. Định ngh ĩa 1.3.1.4: Đồ th ị G g ọi là đồ th ị tuy ến tính ph ẳng, nếu G là đồ th ị hình h ọc ph ẳng cĩ các c ạnh là đoạn th ẳng. Định ngh ĩa 1.3.1.5: Hai đồ th ị G 1 và G 2 g ọi là đồng phơi, n ếu G1 và G 2 cĩ th ể rút g ọn thành nh ững đồ th ị đẳng c ấu qua m ột s ố phép rút g ọn. Định ngh ĩa 1.3.1.6: Cho đồ th ị G cĩ đỉnh v b ậc 2 v ới các c ạnh (v, v 1) và (v, v 2). N ếu ta b ỏ hai c ạnh (v, v 1) và (v, v 2) và thay b ằng cạnh (v 1, v 2), thì ta nĩi r ằng ta đã th ực hi ện phép rút g ọn n ối ti ếp. Đồ th ị G ’ thu được g ọi là đồ th ị rút g ọn t ừ G. 1.3.2 Các định lí: Mệnh đề 1.3.2.1: Hai đơ n đồ th ị G 1 = (V 1, E 1) và G2 = (V 2, E 2) g ọi là đẳng c ấu v ới nhau n ếu t ồn t ại song ánh f: V 1 → ∀ ∈ ⇔ V2 th ỏa mãn v, w G 1 : v k ề w f(v) k ề f(w). Trong tr ường hợp này, hàm f g ọi là m ột đẳng c ấu t ừ G 1 đến G 2. Ghi chú: V ới m ột đồ th ị hình h ọc ph ẳng liên thơng, m ặt ph ẳng được chia làm các mi ền con g ọi là m ặt. M ỗi m ặt gi ới h ạn b ởi chu trình g ọi là biên c ủa m ặt. S ố c ạnh trên biên c ủa m ặt f được g ọi là b ậc của m ặt, kí hi ệu deg(f). B ậc nh ỏ nh ất g ọi là đai c ủa đồ th ị. Mệnh đề 1.3.2.2: M ọi chu trình đồ th ị ph ẳng cĩ độ dài ch ẵn khi
10. 10 và ch ỉ khi m ọi mặt c ủa đồ th ị cĩ b ậc ch ẵn. Định lí 1.3.2.3: M ỗi đơ n đồ th ị ph ẳng đẳng c ấu v ới đồ th ị tuy ến tính ph ẳng. Định lí 1.3.2.4 (Cơng th ức Euler): Cho G là đồ th ị liên thơng ph ẳng cĩ e c ạnh, v đỉnh và f m ặt. Khi đĩ, ta cĩ: f = e – v + 2. Định lí 1.3.2.5(B ất đẳng th ức c ạnh-đỉnh): Cho G là đơ n đồ th ị ph ẳng liên thơng v ới e c ạnh, v đỉnh và đai g ( g ≥ 3 ), khơng cĩ đỉnh g treo. Khi đĩ, ta cĩ: e≤( v − 2) g−2 Hệ qu ả 1.3.2.6: Cho G là đơ n đồ th ị ph ẳng liên thơng v ới e cạnh và v đỉnh (v ≥ 3) khơng cĩ đỉnh treo. Khi đĩ, ta cĩ: e≤3 v − 6 Hệ qu ả 1.3.2.7: Đồ th ị K 5 là khơng ph ẳng. Hệ qu ả 1.3.2.8: Cho G là đơ n đồ th ị ph ẳng liên thơng v ới e cạnh và v đỉnh (v ≥ 3) . Khơng cĩ đỉnh treo và khơng cĩ chu trình độ dài 3. Khi đĩ, ta cĩ: e≤2 v − 4 H ệ qu ả 1.3.2.9 : Đồ th ị K 3,3 là khơng ph ẳng.
11. 11 CHƯƠ NG 2 BÀI TỐN TƠ MÀU ĐỒ TH Ị 2.1. TƠ MÀU ĐỈNH: 2.1.1 Tơ màu b ản đồ: Nh ững bài tốn liên quan đến tơ màu b ản đồ đã d ẫn đến r ất nhi ều k ết qu ả trong lý thuy ết đồ th ị. Khi tơ màu b ản đồ, ta th ường tơ 2 mi ền cĩ chung đường biên gi ới b ằng 2 màu khác nhau. M ột bài tốn đặt ra là xác định s ố màu t ối thi ểu c ần s ử d ụng để tơ màu các mi ền b ản đồ sao cho các mi ền k ề nhau khơng được tơ cùng màu. 2.1.2. Đồ th ị đối ng ẫu: Mỗi b ản đồ trên m ặt ph ẳng cĩ th ể bi ểu di ễn b ằng m ột đồ th ị: Mỗi mi ền bi ểu di ễn b ằng 1 đỉnh; 2 đỉnh s ẽ được n ối v ới nhau khi 2 mi ền t ươ ng ứng cĩ chung đường biên gi ới. Hai mi ền ch ỉ chung nhau tại 1 điểm coi nh ư khơng k ề nhau. Đồ th ị này được g ọi là đồ th ị đối ng ẫu ( hay đồ th ị kép ) c ủa b ản đồ. T ừ ph ươ ng pháp xây d ựng đồ th ị kép c ủa 1 b ản đồ, d ễ th ấy m ỗi b ản đồ ph ẳng s ẽ t ươ ng ứng v ới 1 đồ th ị kép ph ẳng . Bài tốn tơ màu các mi ền c ủa b ản đồ t ươ ng đươ ng v ới bài tốn tơ màu các đỉnh đồ th ị đối ng ẫu sao cho các đỉnh k ề nhau cĩ màu khác nhau. 2.1.3. Các định ngh ĩa: Định ngh ĩa 2.1.3.1: Tơ màu đỉnh c ủa m ột đơ n đồ th ị là s ự gán màu cho các đỉnh c ủa nĩ m ột màu c ụ th ể sao cho khơng cĩ 2 đỉnh
12. 12 kề nhau được gán cùng màu. Định ngh ĩa 2.1.3.2: S ắc s ố c ủa m ột đồ th ị G (Chromatic number) ( kí hi ệu χ(G ) ), là s ố màu t ối thi ểu c ần s ử d ụng để tơ màu đồ th ị này. 2.1.4. Các định lý: Định lý 2.1.4.1: N ếu đồ th ị G ch ứa đồ th ị con đẳng c ấu v ới K n thì χ(G) ≥ n . Định lý 2.1.4.2(Konig) : M ột đơ n đồ th ị cĩ th ể tơ b ằng 2 màu khi và ch ỉ khi nĩ khơng cĩ chu trình độ dài l ẻ. Định lý 2.1.4.3: Mọi đơ n đồ th ị G ta luơn cĩ χ(G) ≤∆ (G) + 1 .( Đẳng th ức xảy ra khi G là đồ th ị đủ ho ặc G là chu trình cĩ độ dài l ẻ).( ∆(G) :là b ậc đỉnh l ớn nh ất c ủa G). Định lý 2.1.4.4 (Định lý Brooks) : Cho G là đơ n đồ th ị n đỉnh liên thơng khác K n và khơng ph ải chu trình cĩ độ dài l ẻ. Khi đĩ χ(G) ≤ ∆ (G) Định lý 2.1.4.5: Mọi đơ n đồ th ị đầy đủ K n đều cĩ: χ( K n) = n. Định lý 2.1.4.6:Mọi chu trình độ dài l ẻ đều cĩ s ắc s ố là 3. Ghi chú: Nếu G' là m ột đồ th ị con c ủa G thì χ()G ≥ χ ( G ') . 2.1.5. Thu ật tốn tu ần t ự ưu tiên đỉnh cĩ b ậc l ớn nh ất: Cho đồ th ị G = (V, E) . Thu ật tốn sau s ẽ tơ màu các đỉnh đồ th ị với s ố màu k g ần v ới s ắc s ố χ(G ) . ’ (i) L ập danh sách các đỉnh đồ th ị E := [v 1, v 2, , v n] theo th ứ t ự bậc gi ảm d ần ≥ ≥ ≥ dv(1 ) dv ( 2 ) dv (n ) Đặt i := 1. (ii) Tơ màu i cho đỉnh đầu tiên trong danh sách. Duy ệt l ần l ượt các đỉnh ti ếp theo và tơ màu i cho đỉnh khơng k ề đỉnh đã tơ màu i. (iii) Nếu t ất c ả các đỉnh đã được tơ màu thì k ết thúc: đồ th ị đã được tơ màu b ằng i màu. Ng ược l ại sang b ước (iv).
13. 13 (iv) Lo ại kh ỏi E ’ các đỉnh đã được tơ màu, đặt i := i + 1 và quay lại b ước (ii). + Ghi chú: (i) M ỗi đỉnh v∈ G được tơ b ằng màu cĩ s ố hi ệu th ấp nh ất ch ưa tơ cho đỉnh k ề v, và s ố đỉnh k ề v khơng v ượt quá ∆(G ) + 1 . (ii) Cĩ th ể hi ệu ch ỉnh E ’ ở b ước (iv) nh ư sau: Lo ại kh ỏi E ’ các đỉnh đã tơ màu. S ắp x ếp l ại các đỉnh trong E ’ theo th ứ t ự b ậc gi ảm d ần các đỉnh trong đồ th ị con c ủa G, cĩ được bằng cách lo ại b ỏ các đỉnh đã tơ màu và các c ạnh liên thu ộc chúng. 2.1.6. Bài tốn tơ màu đỉnh: Bài tốn 1: Một ng ười nuơi các lo ại con v ật sau: A, B, C, D, E, F. Vì m ối quan h ệ gi ữa v ật ăn th ịt và con m ồi, mà m ột s ố lo ại con v ật cĩ th ể s ống trong cùng m ột chu ồng nh ưng cĩ nh ững lo ại con v ật khơng th ể s ống trong cùng m ột chu ồng. Bảng sau ch ỉ ra nh ững lo ại con v ật khơng th ể sống cùng chu ồng: Lo ại con v ật A B C D E F Khơng th ể B, C A, C, A, C, F B, C, D, E sống cùng E B, F lo ại con v ật D, E Xác định s ố l ượng chu ồng nuơi ít nh ất mà ng ười nuơi c ần dùng để cĩ thể nuơi t ất c ả các lo ại con v ật trên? Bài tốn 2: Tr ường THPT ở m ột Huy ện, trong m ột h ọc k ỳ c ủa năm h ọc nhà tr ường tổ ch ức cho h ọc sinh l ớp 12 (thí sinh t ự do) theo học m ột trong 7 l ớp sau: Lớp 1 s ẽ h ọc các mơn: Tốn, Ti ếng Anh, Sinh h ọc, Hĩa h ọc; Lớp 2 s ẽ h ọc các mơn: Tốn, Ti ếng Anh, Tin h ọc, Địa lý; Lớp 3 s ẽ h ọc các mơn: Sinh h ọc, GDCD, V ật lý, Địa lý;
14. 14 Lớp 4 s ẽ h ọc các mơn: Ng ữ v ăn, Sinh h ọc, Tin h ọc, L ịch s ử; Lớp 5 s ẽ h ọc các mơn: Ti ếng Anh, GDCD, Tin h ọc, L ịch s ử; Lớp 6 s ẽ h ọc các mơn: Ng ữ v ăn, Hĩa h ọc, GDCD, Tin h ọc; Lớp 7 s ẽ h ọc các mơn: V ật lý, L ịch s ử, Địa lý, GDCD. Cu ối k ỳ nhà tr ường t ổ ch ức cho các l ớp thi các mơn đã h ọc. Hãy s ắp x ếp m ột l ịch thi để các l ớp đều cĩ th ể tham gia thi các mơn mà h ọ đã h ọc sao cho s ố l ần t ổ ch ức thi là ít nh ất. 2.2. TƠ MÀU ĐỒ TH Ị PH ẲNG: 2.2.1 Định ngh ĩa: M ột đồ th ị được g ọi là ph ẳng n ếu nĩ cĩ th ể v ẽ được trên m ột mặt ph ẳng mà khơng cĩ các c ạnh nào c ắt nhau ( ở m ọi điểm khơng ph ải là điểm mút c ủa các c ạnh) Hình v ẽ nh ư th ế g ọi là m ột bi ểu di ễn ph ẳng c ủa đồ th ị. 2.2.2 Các định lí: Định lý 2.2.2.1: M ọi b ản đồ t ạo b ởi các đường th ẳng trên m ặt ph ẳng cĩ th ể tơ b ằng 2 màu. Định lý 2.2.2.2: Điều ki ện c ần và đủ để b ản đồ cĩ th ể tơ b ằng 2 màu là m ọi đỉnh c ủa đồ th ị ph ẳng t ươ ng ứng v ới b ậc ch ẵn l ớn h ơn ho ặc b ằng 2. Định lý 2.2.2.3(Kempe-Heawood): M ọi đồ th ị ph ẳng đều cĩ s ắc số nh ỏ h ơn ho ặc b ằng 5. Định lí 2.2.2.4 (Định lý 4 màu): M ọi đồ th ị ph ẳng đều cĩ s ắc s ố khơng l ớn h ơn 4. 2.3. TƠ MÀU C ẠNH : 2.3.1 Các định ngh ĩa: Định ngh ĩa 2.3.1.1: Tơ màu c ạnh m ột đơ n đồ th ị là s ự gán màu cho các c ạnh c ủa nĩ sao cho khơng cĩ hai c ạnh k ề được gán cùng m ột màu.
15. 15 Định ngh ĩa 2.3.1.2: S ắc s ố c ạnh c ủa đồ th ị G, ký hi ệu χ'(G) , là s ố màu t ối thi ểu c ần thiết để tơ màu c ạnh đồ th ị. Ghi chú: Mọi đồ th ị G ta cĩ: χ' ()()G ≥ ∆ G Gi ả s ử ta tơ màu các c ạnh c ủa đồ th ị G = (V,E). Cơng vi ệc này cĩ th ể đư a v ề vi ệc tơ màu các đỉnh c ủa đồ th ị đường L(G). 2.3.2 Các định lí: Định lý 2.3.2.1: χ'(G) = χ (L(G)) , L(G) là đồ th ị đường. Định lý 2.3.2.2: (Định lý Konig 1916 ) Nếu G là đồ th ị l ưỡng phân thì χ '(G )= ∆ ( G ) . Ghi chú: Đặc bi ệt s ắc s ố c ạnh c ủa đồ th ị l ưỡng phân đủ K mxn là max{m , n } Định lý 2.3.2.3: χ' =∆ =− (i) N ếu n ch ẵn, thì (K)n (K) n n 1 χ' =∆ += (ii) N ếu n l ẻ, thì (K)n (K) n 1 n Định lý 2.3.2.4: ( Định lý Vizing 1964 ) Mọi đơ n đồ th ị G đều th ỏa mãn: ∆()G ≤χ '() G ≤∆ ()1 G + Định lý 2.3.2.5: Cho G là đồ th ị đủ v ới s ố đỉnh là 2n. Khi đĩ χ '(G )= 2 n − 1 Định lý 2.3.2.6: Cho G là đồ th ị đủ v ới s ố đỉnh là 2n-1. Khi đĩ χ '(G )= 2 n − 1 Định lý 2.3.2.7: Cho dãy s ố nguyên = = =++ . Khi đĩ đồ th ị đủ v ới aa12, 2 5, , an+ 1 ( na 1)n 1 + a n 1 đỉnh v ới các c ạnh được tơ b ằng n màu luơn luơn cĩ chu trình tam giác cùng màu. Định lý 2.3.2.8: Cho dãy s ố nguyên == =−+ bb 2 3, 3 6, , b n + 1 ( bn n 1) 2 khi đĩ đồ th ị đủ v ới − đỉnh và các c ạnh được tơ b ằng n màu sao cho khơng cĩ chu bn+1 1 trình tam giác cùng màu thì trong đồ th ị cĩ hình 5 cạnh v ới các c ạnh
16. 16 cùng màu và các đường chéo được tơ các màu khác. 2.3.3 Bài tốn tơ màu c ạnh: Bài tốn 1. Cĩ 5 thành ph ố, t ừ m ỗi thành ph ố cĩ đường bay đến một s ố thành ph ố khác. Bi ết r ằng c ứ l ấy ba thành ph ố b ất kì trong 5 thành ph ố đĩ thì cĩ hai thành ph ố cĩ đường bay tr ực ti ếp đến nhau và hai thành ph ố ch ưa cĩ đường bay nh ư v ậy. Ch ứng minh r ằng: a) M ỗi thành ph ố cĩ đường bay tr ực ti ếp đến hai và ch ỉ hai thành ph ố khác; b) T ừ m ỗi thành ph ố cĩ th ể bay đến các thành ph ố khác, m ỗi nơi m ột l ần và quay v ề ch ỗ c ũ. Bài tốn 2. Cĩ 6 đội bĩng thi đấu v ới nhau (M ỗi đội ph ải đấu một tr ận v ới 5 đội khác) . Ch ứng minh r ằng vào b ất c ứ lúc nào c ũng cĩ ba đội trong đĩ t ừng c ặp đã đấu v ới nhau r ồi ho ặc ch ưa đấu v ới nhau tr ận nào. Bài tốn 3 . Ch ứng minh r ằng trong b ất kì 6 ng ười nào c ũng cĩ hai nhĩm, m ỗi nhĩm ba ng ười, t ừng đơi m ột đã quen bi ết nhau ho ặc mới g ặp nhau l ần đầu tiên. Bài tốn 4. Trong m ột bu ổi h ọp t ổ đầu n ăm h ọc l ớp 10, b ạn t ổ tr ưởng phát hi ện ra m ột điều: m ỗi b ạn trong t ổ (t ổ cĩ 9 b ạn) đã quen đúng v ới ba b ạn khác. Bạn Bích nĩi ngay: “Vơ lí khơng th ể được!” Vì sao b ạn Bích l ại cĩ th ể nĩi nh ư th ế? Bài tốn 5. Trong phịng cĩ 9 ng ười, trong đĩ b ất k ỳ 3 ng ười nào c ũng cĩ 2 ng ười quen nhau. Ch ứng minh r ằng cĩ 4 ng ười t ừng đơi m ột quen nhau. Bài tốn 6. Cĩ 17 nhà bác h ọc, m ỗi ng ười trao đổi th ư t ừ v ới 16 ng ười khác. Trong th ư, h ọ ch ỉ bàn v ề ba đề tài, nh ưng b ất c ứ hai nhà bác h ọc nào c ũng ch ỉ bàn với nhau ch ỉ v ề m ột đề tài. Ch ứng minh rằng cĩ khơng ít h ơn 3 nhà bác h ọc đã bàn v ới nhau v ề cùng m ột
17. 17 đề tài. (Đề thi tốn qu ốc t ế l ần th ứ VI, 1964) Bài tốn 7. (Bài tốn n ữ sinh Lucas) Trong m ột ký túc xá cĩ 2n nữ sinh. M ỗi sáng h ọ đi t ừng c ặp đến tr ường. Cĩ th ể s ắp x ếp nhi ều nh ất bao nhiêu l ần đi nh ư v ậy sao cho khơng cĩ 2 n ữ sinh đi cùng nhau quá m ột l ần? Bài tốn 8. Trong khơng gian cho 7 điểm sao cho khơng cĩ b ất cứ 3 điểm nào trong s ố đĩ th ẳng hàng. M ột s ố c ặp điểm được n ối v ới nhau b ằng các đoạn th ẳng. G ọi n là s ố đoạn th ẳng đã n ối. M ỗi đoạn th ẳng được tơ b ởi m ột trong hai màu đỏ ho ặc xanh. Tìm giá tr ị nh ỏ nh ất c ủa n, sao cho v ới m ọi cách n ối n đoạn th ẳng đã được tơ màu trong 7 điểm đã cho luơn t ồn t ại m ột tam giác cĩ c ạnh cùng màu? (Thi IMO l ần th ứ 33,1992 )
18. 18 CH ƯƠ NG 3 : ỨNG D ỤNG 3.1. BÀI TỐN ĐIỀU KHI ỂN ĐÈN HI ỆU NÚT GIAO THƠNG: 3.1.1 Bài tốn: Gi ả s ử ta c ần thi ết l ập m ột quy trình điều khi ển đèn hi ệu ở nút giao thơng ph ức t ạp, nhi ều giao l ộ, sao cho trong m ột kho ản th ời gian ấn định, m ột s ố tuy ến được thơng qua, trong khi m ột s ố tuy ến khác b ị cấm để tránh x ảy ra đụng độ. Vấn đề đặt ra là phân ho ạch các tuy ến đường thành m ột s ố ít nh ất các nhĩm, sao cho các tuy ến trong m ỗi nhĩm khơng đụng độ. Khi đĩ th ời gian ch ờ đợi t ối đa để được thơng đường là ít nh ất. 3.1.2 Cách gi ải: Gi ả s ử nút giao thơng cĩ n tuy ến T 1, T 2, , T n. Nh ững tuy ến giao nhau cĩ th ể d ẫn đến đụng độ g ọi là các tuy ến xung kh ắc. Nh ư v ậy đèn hi ệu ph ải báo sao cho nh ững tuy ến xung kh ắc khơng đồng th ời giao thơng, và cho phép đồng th ời l ưu thơng nh ững tuy ến khơng xung kh ắc. Ta mơ hình hĩa bài tốn b ằng đồ th ị và đư a v ề bài tốn tơ màu đồ th ị nh ư sau: Các đỉnh c ủa đồ th ị là các tuy ến đường, và hai tuy ến k ề nhau khi và ch ỉ khi chúng xung kh ắc. Ta tơ màu các đỉnh đồ th ị sao cho các đỉnh k ề nhau khơng cùng màu. Ta coi m ỗi màu đại di ện cho m ột pha điều khi ển đèn báo: các tuy ến cùng màu đĩ l ưu thơng. Nh ư v ậy bài tốn ban đầu đư a v ề bài tốn tơ màu đồ th ị v ới s ố màu ít nh ất. 3.1.3 Ví d ụ: Xét nút giao thơng sau:
19. 19 D C E B A Hỏi c ần bao nhiêu pha để điều khi ển nút giao thơng l ưu thơng t ất cả các tuy ến? Ở đây C và E là đường 1 chi ều, cịn các đường khác là đường 2 chi ều. 3.2. BÀI TỐN L ẬP L ỊCH THI: 3.2.1 Bài tốn: Gi ả s ử m ỗi h ọc sinh ph ải thi m ột s ố mơn trong n mơn thi. Hãy lập l ịch thi sao cho khơng cĩ h ọc sinh nào cĩ hai mơn thi cùng m ột th ời gian và s ố đợt thi là ít nh ất. 3.2.2 Cách gi ải: Để gi ải bài tốn ta l ập đồ th ị cĩ các đỉnh là các mơn thi và hai mơn thi k ề nhau n ếu cĩ m ột h ọc sinh thi c ả hai mơn này. Th ời gian thi c ủa m ỗi mơn được bi ểu th ị b ằng các màu khác nhau. Nh ư v ậy bài tốn l ập l ịch thi được đư a v ề bài tốn tơ màu đồ th ị. 3.2.3 Ví d ụ: Cĩ 9 mơn thi c ần x ếp l ịch, các mơn h ọc được đánh số t ừ 1 đến 9, các c ặp mơn thi sau cĩ chung h ọc sinh. (1, 2); (1, 3); (1, 5); (1, 6); (1, 8); (2, 3); (2, 4); (2, 5); (2, 7); (2, 9); (3, 4); (3, 6); (3, 8); (4, 5); (4, 6); (4, 8); (5, 3); (5, 6); (5, 9); (6, 2); (6, 8); (7, 6); (7, 8); (7, 9); (8, 9); (9, 1). Hãy s ắp x ếp l ịch thi sao cho các h ọc sinh đều tham gia thi được các mơn trên.
20. 20 3.3. BÀI TỐN PHÂN CHIA T ẦN S Ố: 3.3.1 Bài tốn: Cĩ n đài phát. Hãy phân chia các kênh truy ền hình cho các đài phát sao cho hai đài cách nhau khơng quá 100 (km) khơng được trùng kênh và s ố kênh dùng là ít nh ất. 3.3.2 Cách gi ải: Để gi ải bài tốn ta l ập đồ th ị cĩ các đỉnh là các đài phát và hai đài phát k ề nhau n ếu kho ảng cách gi ữa chúng khơng quá 100 (km). Kênh truy ền hình c ủa m ỗi đài được bi ểu th ị b ằng các màu khác nhau. Nh ư v ậy bài tốn phân chia t ần s ố được đư a v ề bài tốn tơ màu đồ th ị. 3.3.3 Ví d ụ: Xác định s ố kênh truy ền hình ít nh ất dùng để phân chia cho các đài truy ền hình ở 11 t ỉnh (m ỗi t ỉnh ch ỉ cĩ m ột đài truy ền hình) : Đà N ẵng, Qu ảng Ngãi, Bình Định, Phú Yên, Khánh Hịa, Lâm Đồng, Ninh Thu ận, Bình Ph ước, Gia Lai, Kon Tum, Đắk L ắk sao cho khơng cĩ hai đài phát nào ở hai t ỉnh n ằm c ạnh nhau trên b ảng đồ địa lí dùng cùng m ột kênh. 3.4. BÀI TỐN THANH GHI TRONG B Ộ D ỊCH: 3.4.1 Bài tốn: Trong các b ộ d ịch hi ệu qu ả cao, vi ệc th ực hi ện các vịng l ặp được t ăng t ốc khi các bi ến dùng th ường xuyên được ghi t ạm th ời trong các thanh ghi ch ỉ s ố của b ộ x ử lí trung tâm (CPU) mà khơng ph ải ở trong b ộ nh ớ thơng th ường. V ới m ột vịng l ặp cho tr ước, c ần ít nh ất bao nhiêu thanh ghi ch ỉ s ố. 3.4.2 Cách gi ải: Ta gi ải bài tốn b ằng mơ hình tơ màu đồ th ị. Để xây d ựng mơ hình ta coi m ỗi đỉnh c ủa đồ th ị là m ột bi ến trong vịng l ặp. Gi ữa hai đỉnh cĩ m ột c ạnh n ếu các bi ến bi ểu th ị b ằng các đỉnh này ph ải được
21. 21 lưu trong các thanh ghi ch ỉ s ố t ại cùng th ời điểm khi th ực hi ện vịng lặp. Nh ư v ậy s ố màu c ủa đồ th ị chính là s ố thanh ghi c ần cĩ vì nh ững thanh ghi khác nhau được phân cho các bi ến khi các đỉnh bi ểu th ị các bi ến này là li ền k ề trong đồ th ị. 3.5 M ỘT S Ố ỨNG D ỤNG KHÁC V Ề TƠ MÀU: Bài tốn 1 . (Bài tốn n ữ sinh Kirkman) Trong m ột ký túc xá cĩ 15 n ữ sinh. M ỗi sáng h ọ đi t ừng nhĩm 3 ng ười đến tr ường v ới t ất c ả 7 ngày trong tu ần. Cĩ th ể s ắp x ếp nhi ều nh ất bao nhiêu l ần đi nh ư v ậy sao cho khơng cĩ 2 n ữ sinh đi cùng nhau quá m ột l ần. Bài tốn 2. Gi ả s ử trong n ăm thành ph ố ở Vi ệt Nam: Hà N ội, Đồng H ới, Hu ế, Đà N ẵng, H ải Phịng n ếu ch ọn ra ba thành ph ố b ất kỳ đều cĩ hai thành ph ố n ối v ới nhau b ởi đường hàng khơng tr ực ti ếp và hai thành ph ố khơng cĩ đường hàng khơng tr ực ti ếp. a) Ch ứng minh r ằng m ỗi thành ph ố đều cĩ đường hàng khơng tr ực ti ếp v ới đúng hai thành ph ố khác. b) M ột khách du l ịch mu ốn đến c ả n ăm thành ph ố trên để tham quan các th ắng c ảnh. H ỏi khi xu ất phát t ại m ột thành ph ố b ất k ỳ trong năm thành ph ố trên, ng ười ta cĩ th ể ch ọn đường hàng khơng tr ực ti ếp để đến các thành ph ố cịn l ại, m ỗi thành ph ố m ột l ần và quay v ề thành ph ố xu ất phát được hay khơng? Bài tốn 3. (Bài tốn x ếp th ời khĩa bi ểu ở tr ường h ọc) Cho danh sách m ột s ố giáo viên và danh sách các l ớp h ọc được dạy b ởi các giáo viên này. Gi ả s ử r ằng cĩ đủ phịng h ọc để cho các giáo viên th ực hi ện các ti ết d ạy c ủa mình t ại các l ớp nh ưng t ại m ột th ời điểm thì m ột giáo viên ch ỉ cĩ th ể d ạy t ại m ột l ớp và cùng m ột lúc tại m ột l ớp khơng th ể cĩ nhi ều h ơn m ột giáo viên d ạy. Xác định th ời gian t ối thi ểu c ần thi ết để b ố trí cho các giáo viên th ực hi ện các ti ết
22. 22 dạy c ủa mình t ại các l ớp, bi ết r ằng m ột ti ết d ạy cĩ th ời gian 45 phút. Bài tốn 4. Trong m ột n ước, b ất k ỳ 2 thành ph ố nào c ũng n ối với nhau tr ực ti ếp b ằng m ột trong các ph ươ ng ti ện giao thơng: ơ tơ, tàu h ỏa ho ặc máy bay. Bi ết r ằng: khơng cĩ thành ph ố nào được n ối với các thành ph ố khác b ằng c ả 3 ph ươ ng ti ện giao thơng, đồng th ời khơng cĩ b ộ ba thành ph ố nào t ừng c ặp được n ối v ới nhau b ằng cùng một ph ươ ng ti ện. Trong n ước đĩ, cĩ th ể cĩ nhi ều nh ất là bao nhiêu thành ph ố? (Thi h ọc sinh gi ỏi M ỹ, 1981; Bungari, 1981) Bài tốn 5 . Cĩ 20 đội bĩng thi đấu v ới nhau. H ỏi s ố tr ận đã đấu tối thi ểu là bao nhiêu để cho trong b ất c ứ ba đội bĩng nào c ũng cĩ hai đội đã đấu v ới nhau r ồi? (Thi h ọc sinh gi ỏi Liên Xơ, l ớp 9-10, ngày th ứ 2, 1969) Bài tốn 6. a) Cĩ 8 thành ph ố; gi ữa b ất kì 2 thành ph ố nào c ũng cĩ đường giao thơng b ằng m ột trong các ph ươ ng ti ện: ơtơ, tàu th ủy ho ặc máy bay. Ch ứng minh r ằng cĩ ít nh ất 4 thành ph ố được n ối v ới nhau b ằng cùng m ột ph ươ ng ti ện giao thơng. b) Cho m ột đồ th ị đầy đủ v ới n đỉnh, m ỗi c ạnh c ủa nĩ đều được tơ b ằng m ột trong 3 màu. Ch ứng minh r ằng cĩ m ột đồ th ị con liên n thơng, ch ứa khơng ít h ơn đỉnh, cĩ các c ạnh được tơ cùng m ột 2 màu. (Câu b: đề thi sinh viên gi ỏi, khoa Tốn lý, tr ường đại h ọc t ổng h ợp Lomonossov, 1982) Bài tốn 7. Cho 9 điểm trong khơng gian trong đĩ khơng cĩ 4 điểm nào đồng ph ẳng. T ất c ả nh ững điểm này được n ối v ới nhau t ừng cặp b ằng các đoạn th ẳng. M ỗi đoạn th ẳng được tơ màu xanh ho ặc màu đỏ ho ặc khơng tơ màu. Tìm giá tr ị nh ỏ nh ất c ủa n sao cho v ới
23. 23 mỗi cách tơ màu n đoạn th ẳng luơn t ồn t ại m ột tam giác cĩ c ạnh cùng màu. Bài tốn 8. Cho đồ th ị đầy đủ cĩ k đỉnh; các c ạnh được tơ màu xanh, đỏ ho ặc tr ắng. Tìm giá tr ị nh ỏ nh ất c ủa n sao cho v ới m ọi cách tơ màu n c ạnh c ủa đồ th ị luơn tìm được m ột tam giác cĩ c ạnh cùng màu. Bài tốn 9. Ch ứng minh r ằng trong sáu ng ười b ất kì ho ặc cĩ ba ng ười đơi m ột quen nhau, ho ặc cĩ ba ng ười đơi m ột khơng quen nhau. Bài tốn 10 . Một hình ch ữ nh ật k ẻ ơ vuơng cĩ 1991 hàng và 1992 c ột. Kí hi ệu ơ vuơng n ằm ở giao c ủa hàng th ứ m (k ể t ừ trên xu ống d ưới) và c ột th ứ n (k ể t ừ trái sang ph ải) là (m; n). Tơ màu các ơ vuơng c ủa b ảng theo cách sau: l ần th ứ nh ất tơ 3 ơ (r; s), (r+1; s+1), (r+2; s+1), v ới r, s là hai s ố t ự nhiên cho tr ước th ỏa mãn 1≤r ≤ 1989 và 1≤s ≤ 1991 ; t ừ l ần th ứ hai m ỗi l ần tơ đúng ba ơ ch ưa cĩ màu n ằm c ạnh nhau ho ặc trong cùng m ột hàng ho ặc trong cùng m ột c ột. H ỏi b ằng cách đĩ cĩ th ể tơ màu được t ất c ả các ơ vuơng c ủa b ảng đã cho hay khơng?
24. 24 KẾT LU ẬN - Qua quá trình nghiên c ứu đề tài tơi đã nh ận được m ột s ố k ết qu ả sau: 1. Với b ản thân đã h ệ th ống được m ột s ố ki ến th ức cơ b ản về Lý Thuy ết tơ màu tơ thị và hi ểu sâu h ơn v ề các định lí và các bài tốn tơ màu đồ th ị. 2. Đư a ra được các ph ươ ng án v ận d ụng. 3. Xây d ựng được h ệ th ống các bài tốn s ơ c ấp gi ải được b ằng cách v ận d ụng nh ững k ết qu ả c ủa bài tốn tơ màu đồ th ị. 4. Hướng phát tri ển c ủa đề tài: Ti ếp t ục nghiên c ứu v ận d ụng lý lu ận và k ết qu ả c ủa lý thuy ết tơ màu đồ th ị và vi ệc b ồi d ưỡng h ọc sinh. - Lu ận v ăn này được vi ết v ới mong mu ốn nghiên c ứu sâu nh ững định lý và ứng d ụng c ủa bài tốn tơ màu đồ th ị, để t ừ đĩ xây d ựng một h ệ th ống các bài tốn s ơ c ấp cĩ th ể gi ải được b ằng cách v ận d ụng nh ững k ết qu ả c ủa bài tốn tơ màu đồ th ị.