intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Tóm tắt luận văn thạc sĩ khoa học: Bài toán tô màu đồ thị và ứng dụng

Chia sẻ: Lang Nguyen | Ngày: | Loại File: PDF | Số trang:24

484
lượt xem
82
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt luận văn thạc sĩ khoa học: Bài toán tô màu đồ thị và ứng dụng trình bày lý thuyết cơ bản về đồ thị, nghiên cứu sâu các định lý về tô màu, tô màu cạnh, các định lý về tô màu đồ thị phẳng và các bài toán màu đinh, tô màu cạnh.

Chủ đề:
Lưu

Nội dung Text: Tóm tắt luận văn thạc sĩ khoa học: 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 TOÁN TÔ MÀU Đ TH VÀ NG D NG Chuyên ngành: Phương pháp Toá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 hoà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. Hoà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 toá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 toá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 toá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 toá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 toán tô màu ñ th vào gi i toán giúp ta ñ t ñư c m c tiêu: gi i ñư c m t s bài toán không m u m c, các bài toán thư ng g p trong th c t và r i rác m t s bài toán trong các kì thi tuy n Olympic toán qu c t . Nghiên c u khai thác m t s y u t c a bài toán tô màu ñ th và ng d ng này trong vi c gi i các bài toá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 toá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 toá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 toá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 toán tô màu ñ th trong vi c gi i các bài toá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 Kn 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 = ({V1, V2}, E). Đ nh nghĩa 1.1.3.7: Đ th Km,n là ñ th lư ng phân ({V1, V2}, E) v i t p V1 có m ñ nh và t p V2 có n ñ nh và m i ñ nh c a V1 ñư c n i v i m i ñ nh c a V2 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 d0(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 d1(v), là s cung ñi t i ñ nh v (v là ñ nh cu i). Đ nh nghĩa 1.1.5.4: Đ th Kn 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à ∑ d (v ) = 2.card ( E ) v∈V ii) N u G là ñ th có hư ng thì: ∑ d (v) = ∑ d1(v ) = card ( E ) v∈V 0 v∈V 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 Kn có b c n – 1 và Kn có n( n − 1) c nh. 2 M nh ñ 1.1.5.8: Cho ñ th lư ng phân ñ
  7. 7 Km,n = ({V1, V2}, E) v i t p V1 có m ñ nh và t p V2 có n ñ nh. Khi ñó m i ñ nh trong V1 có b c là n, m i ñ nh trong V2 có b c là m và Km,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, e1, v1, e2, v2,..., vn-1, en, w) Trong ñó vi (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 G1 = (V1, E1) và G2 = (V2, E2) g i là ñ ng c u v i nhau n u t n t i song ánh f: V1 → V2 và g: E1 → E2 th a mãn ∀e ∈ E1 : e = ( v, w) ⇔ g (e) = ( f (v ), f (w)) c p hàm f và g g i là m t ñ ng c u t G1 ñ n G2. Đ 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 G1 và G2 g i là ñ ng phôi, n u G1 và G2 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, v1) và (v, v2). N u ta b hai c nh (v, v1) và (v, v2) và thay b ng c nh (v1, v2), 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 G1 = (V1, E1) và G2 = (V2, E2) g i là ñ ng c u v i nhau n u t n t i song ánh f: V1 → V2 th a mãn ∀v, w ∈ G1 : 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 G1 ñ n G2. 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 ≤ 3v − 6 H qu 1.3.2.7: Đ th K5 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 ≤ 2v − 4 H qu 1.3.2.9 : Đ th K3,3 là không ph ng.
  11. 11 CHƯƠNG 2 BÀI TOÁN TÔ MÀU Đ TH 2.1. TÔ MÀU Đ NH: 2.1.1 Tô màu b n ñ : Nh ng bài toá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 toá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 toán tô màu các mi n c a b n ñ tương ñương v i bài toá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 Kn 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 Kn 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 ñ Kn ñ u có: χ( Kn) = 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 toán tu n t ưu tiên ñ nh có b c l n nh t: Cho ñ th G = (V, E) . Thu t toá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’ := [v1, v2, ..., vn] theo th t b c gi m d n d ( v1 ) ≥ d ( v2 ) ≥ ... ≥ d ( vn ) Đ 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 toán tô màu ñ nh: Bài toá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 toá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: Toán, Ti ng Anh, Sinh h c, Hóa h c; L p 2 s h c các môn: Toá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 ñ Kmxn 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 ) ≤ ∆ (G ) + 1 Đ 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 a1 = 2, a2 = 5,..., an+1 = ( n + 1) an + 1 Khi ñó ñ th ñ v i . an + 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 b2 = 3, b3 = 6,..., bn+1 = (bn − 1) n + 2 khi ñó ñ th ñ v i bn+1 − 1 ñ nh và các c nh ñư c tô b ng n màu sao cho không có chu 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 toán tô màu c nh: Bài toá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 toá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 toá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 toá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 toá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 toá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 toán qu c t l n th VI, 1964) Bài toán 7. (Bài toá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 toá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 TOÁN ĐI U KHI N ĐÈN HI U NÚT GIAO THÔNG: 3.1.1 Bài toá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 T1, T2,…, Tn. 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 toán b ng ñ th và ñưa v bài toá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 toán ban ñ u ñưa v bài toá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 TOÁN L P L CH THI: 3.2.1 Bài toá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 toá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 toán l p l ch thi ñư c ñưa v bài toá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 TOÁN PHÂN CHIA T N S : 3.3.1 Bài toá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 toá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 toán phân chia t n s ñư c ñưa v bài toá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 TOÁN THANH GHI TRONG B D CH: 3.4.1 Bài toá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 toá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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2