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

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.
Nội dung trích xuất từ tài liệu:
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 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 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 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 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 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 Đ 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 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 ...