BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI ——————————o0o—————————— LƯU THỊ THÊM ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON CÙNG MỘT SỐ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số: 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học TS Trần Minh Tước HÀ NỘI, 2018 Lời cảm ơn Sau thời gian cố gắng, nỗ lực học tập nghiên cứu, đến hồn thành luận văn tốt nghiệp thạc sĩ Để có kết này, tơi xin bày tỏ lòng biết ơn sâu sắc lời cảm ơn chân thành đến thầy giáo, TS Trần Minh Tước, người định hướng nghiên cứu cho suốt thời gian thực luận văn Tơi xin chân thành cảm ơn giúp đỡ quý báu thầy giáo mơn Tốn ứng dụng nói riêng khoa Toán, trường Đại học Sư phạm Hà Nội nói chung Xin cảm ơn người thân gia đình tất người bạn thân yêu thông cảm, chia sẻ tạo điều kiện tốt cho tơi để tơi học tập, nghiên cứu thực luận văn Tơi mong nhận đóng góp ý kiến thầy cô bạn để luận văn hồn thiện Tơi xin chân thành cảm ơn! Hà Nội, tháng 11 năm 2018 Tác giả Lưu Thị Thêm Lời cam đoan Tôi xin cam đoan luận văn cơng trình nghiên cứu riêng tôi, thực hướng dẫn thầy giáo TS Trần Minh Tước Trong trình nghiên cứu, kế thừa thành khoa học nhà khoa học với trân trọng biết ơn Các kết trích dẫn luận văn rõ nguồn gốc Hà Nội, tháng 11 năm 2018 Tác giả Lưu Thị Thêm Mục lục Mở đầu Chương Kiến thức sở 1.1 Đồ thị phân loại đồ thị 1.1.1 Đồ thị có hướng 1.1.2 Đồ thị vô hướng 1.1.3 Đa đồ thị có hướng đa đồ thị vơ 1.1.4 Đồ thị có trọng số 1.2 Đồ thị số vấn đề liên quan 1.3 Bậc đỉnh 1.4 Chu trình, mạch 1.5 Tính liên thơng đồ thị 1.6 Cây khung đồ thị 1.7 Phương pháp duyệt đồ thị 1.8 Luồng mạng 1.9 Ghép cặp đồ thị hướng Chương Vết Euler, mạch Euler đồ thị Euler 2.1 Định nghĩa 2.2 Định lí điều kiện cần đủ để đồ thị đồ thị Euler 2.3 Thuật tốn tìm mạch Euler 2.3.1 Đối với đồ thị vô hướng 2.3.2 Đối với đồ thị có hướng 2.4 Ứng dụng đồ thị Euler giải toán người đưa thư 2.4.1 Thuật tốn tìm lời giải cho tốn người đưa thư đồ thị vơ hướng có trọng số khơng đồ thị Euler[[2]] 7 10 11 12 12 13 13 14 14 15 16 16 18 20 20 21 25 25 Luận văn thạc sĩ 2.4.2 Thuật tốn tìm lời giải cho tốn người đưa thư đồ thị có hướng có trọng số khơng đồ thị Euler[[2]] 28 Chương 3.1 3.2 3.3 3.4 Đường Hamilton, chu trình Hamilton đồ thị Hamilton Định nghĩa đồ thị Hamilton Một số định lí Tìm chu trình Hamilton phương pháp nhân ma trận Ứng dụng: Thuật toán xấp xỉ cho tốn tìm chu trình người bán hàng có trọng số tối thiểu đồ thị có trọng số 3.4.1 Đặt vấn đề 3.4.2 Xây dựng thuật tốn xấp xỉ tìm chu trình Hamilton có trọng số tối thiểu đồ thị có trọng số 3.4.3 Thuật toán cải tiến 33 33 35 40 45 45 48 50 Kết luận 53 Tài liệu tham khảo 54 Lưu Thị Thêm K20-Tốn ứng dụng Mở đầu Lí chọn đề tài Năm 1736 coi năm khai sinh lý thuyết đồ thị với việc công b li gii bi toỏn By cõy cu Kăonigsberg nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler (1707 - 1783) Từ có khái niệm nghiên cứu loại đồ thị gọi đồ thị Euler Năm 1858, nhà toán học Hamilton (1805 - 1865) đưa trò chơi “Đi vòng quanh giới”, mở loạt nghiên cứu cho loại đồ thị đồ thị Hamilton Ra đời muộn số lĩnh vực toán khác lý thuyết đồ thị có nhiều ứng dụng thực tế Khi nghiên cứu lý thuyết đồ thị hai lớp đồ thị ln ln nhắc đến tạo hứng thú cho việc tìm hiểu, phát triển ứng dụng Những phép chứng minh, thuật toán lý thuyết đồ thị tạo cảm hứng cho người nghiên cứu tốn học mà cho lập trình viên cơng nghệ thơng tin Đã có nhiều nghiên cứu hai loại đồ thị có nhiều định lý, mối liên hệ ứng dụng tìm thấy Được gợi ý giảng viên hướng dẫn T.S Trần Minh Tước với mong muốn có hiểu biết đầy đủ mối liên hệ đồ thị Euler, đồ thị Hamilton với số khái niệm khác lý thuyết đồ thị số ứng dụng nó, tơi chọn đề tài: “Đồ thị Euler đồ thị Hamilton số ứng dụng” Mục đích nghiên cứu Nghiên cứu đồ thị Euler, đồ thị Hamilton mối liên hệ chúng với số khái niệm khác lý thuyết đồ thị số ứng dụng hai lớp đồ thị Luận văn thạc sĩ Nhiệm vụ nghiên cứu • Tìm hiểu tính chất mạch Euler, chu trình Hamilton đồ thị • Tìm hiểu mối liên hệ đồ thị Euler, đồ thị Hamilton với khái niệm khác để nghiên cứu thuật tốn liên quan tới hai loại đồ thị • Tìm hiểu số ứng dụng hai loại đồ thị Đối tượng phạm vi nghiên cứu • Đồ thị có hướng đồ thị vơ hướng • Mạch Euler, đồ thị Euler • Chu trình Hamilton, đồ thị Hamilton Phương pháp nghiên cứu Chúng sử dụng chủ yếu việc nghiên cứu lý thuyết, vận dụng luật logic toán học, với số công cụ tổ hợp tối ưu rời rạc Lưu Thị Thêm K20-Toán ứng dụng Chương Kiến thức sở Trong chương này, khái niệm kết tham khảo từ tài liệu "Lý thuyết Tổ hợp Đồ thị", Nxb ĐHQG Hà Nội, 2005 GS TS Ngô Đắc Tân 1.1 Đồ thị phân loại đồ thị Khái niệm đồ thị xuất từ nhiều lĩnh vực khác sống Trong lĩnh vực riêng mình, người ta cần tới kiểu đồ thị Vì mà xuất nhiều loại đồ thị khác Song tựu chung lại ta phân loại chúng theo bốn dạng sau đây: đồ thị có hướng, đồ thị vơ hướng, đa đồ thị có hướng, đa đồ thị vơ hướng Ngồi ra, tùy theo mục đích mà ta gắn trọng số cho đỉnh cạnh đồ thị 1.1.1 Đồ thị có hướng Một đồ thị có hướng G cặp có thứ tự G = (V, E), V tập, E tập tích đề V × V , tức E quan hệ hai V Các phần tử V gọi đỉnh, phần tử E gọi cung đồ thị có hướng G Cụ thể hơn, (a, b) ∈ E (a, b) gọi cung G với đỉnh đầu a, đỉnh cuối b có hướng từ a tới b Ví dụ 1.1.1 Cho G = (V, E) với V = {a, b, c, d, e, f } E = {(a, a), (a, b), (b, d), (d, b), (c, e), (e, a)} Khi G đồ thị có hướng biểu diễn hình (1.1) Luận văn thạc sĩ Hình 1.1: Ví dụ đồ thị có hướng Giả sử G = (V, E) đồ thị có hướng Nếu (a, b) ∈ E đỉnh a b gọi liên thuộc với cung (a, b) Khi a b gọi kề Hai cung G gọi kề chúng có đỉnh chung Cung dạng (a, a) với a ∈ V gọi khuyên Đỉnh không liên thuộc với cung gọi đỉnh cô lập Số đỉnh G, tức | V |, gọi cấp G Số cung G, tức | E |, gọi cỡ G 1.1.2 Đồ thị vô hướng Một đồ thị vô hướng G cặp có thứ tự G = (V, E), V tập, E tập với phần tử đa tập lực lượng V , đa tập khái niệm mở rộng khái niệm tập hợp Trong đa tập, phần tử xuất nhiều lần Tổng số tất lần xuất phần tử gọi lực lượng đa tập Các phần tử V gọi đỉnh, phần tử E gọi cạnh đồ thị vô hướng G Nếu e = {a, b} cạnh G a b gọi đỉnh đầu mút cạnh e hay đỉnh liên thuộc với e Ta thường kí hiệu cạnh e = {a, b} ngắn gọn ab Ví dụ 1.1.2 Cho G = (V, E) với V = {a, b, c, d} E = {{a, a} , {a, b} , {b, d} , {b, c} , {c, d}} Khi G đồ thị vô hướng biểu diễn hình (1.2) Lưu Thị Thêm K20-Tốn ứng dụng Luận văn thạc sĩ Hình 3.7: 3.3 Tìm chu trình Hamilton phương pháp nhân ma trận Phương pháp nhân ma trận dùng để tìm tất chu trình Hamilton đồ thị vơ hướng đồ thị có hướng Nó dùng để tìm chu trình Hamilton ngắn Giống tất phương pháp biết, phương pháp nhân ma trận không hiệu số đỉnh lớn Phương pháp mơ tả qua ví dụ Ví dụ 3.3.1 Cho đồ thị G sau, tìm tất chu trình Hamilton G Hình 3.8: Lưu Thị Thêm 40 K20-Toán ứng dụng Luận văn thạc sĩ Bước 1: Xây dựng ma trận M1 hình thành từ ma trận kề cách thay (i, j) thành chuỗi i, j thành phần nằm đường chéo Ta có: AB AC 0 0 0 BD 0 0 0 CD 0 M1 = 0 0 DE DF 0 0 0 EF FA 0 0 FG GA GC GE 0 Bước 2: Xây dựng ma trận M từ mà trận M1 cách xóa kí tự ban đầu phần tử chuỗi 0 M= 0 A A B 0 0 0 C 0 0 C D D 0 0 0 E 0 E 0 F F 0 0 0 G Bước 3: M2 = M1 ∗ M 0 DF A M2 = EF A 0 0 F GA F AB Lưu Thị Thêm GAB 0 0 F AC F GC GAC ABD ACD 0 BDE BDF 0 CDE CDF 0 DEF DF G 0 EF G 41 F GE 0 GCD GEF K20-Toán ứng dụng Luận văn thạc sĩ Bước 4: M3 = M2 ∗ M M3 = 0 ABDF ACDF BDEF CDEF BDF G CDF G DF GE DEF G 0 0 0 GCDE GCDF 0 0 ABDE BDF A CDF A DEF A DF GA 0 0 DF AC DF GC 0 EF GA DF AB EF AC EF GC EF AB F GAB F GAC GEF A 0 Bước 5: M4 = M3 ∗ M F ABD F ACD F GCD GABD GACD 0 0 ABDEF ABDF G ACDF G BDEF A BDF GA CDEF A CDF GA BDF AC BDF GC BDF GE BDEF G CDF AB 0 CDF GE CDEF G DEF GA DEF AB DF GAB DEF AC DF GAC DEF GC 0 0 EF GAB EF GAC EF ABD EF ACD EF GCD 0 0 0 F GABD F GACD F ABDE F ACDE F GCDE 0 GCDF A GEF AB GEF AC GABDE GACDE GABDF GACDF GCDEF M4 = Bước 6: M5 = M4 ∗ M 0 ABDF GC ABDF GE ACDF GE ABDEF G BDEF GA BDEF AC BDF GAC BDEF GC 0 0 0 0 0 CDEF AB CDF GAB DEF GAB DEF GAC 0 0 0 EF GABD EF GACD 0 0 0 F GABDE F GACDE 0 GCDEF A GCDF AB GEF ABD GEF ACD GABDEF GACDEF CDEF GA M5 = Kết thúc bước ta có tất 23 đường Hamilton Sau kiểm tra điểm kết thúc đường Hamilton có Lưu Thị Thêm 42 K20-Tốn ứng dụng Luận văn thạc sĩ kết nối với điểm đầu cạnh hay khơng ta tìm 11 chu trình Hamilton ABDEFG EFGABD BDEFGA EFGACD CDEFGA GABDEF GACDEF DEFGAB FGABDE DEFGAC FGACDE Ví dụ 3.3.2 Cho đồ thị G Tìm tất chu trình Hamilton G Hình 3.9: Bước 1: Xây dựng ma trận M1 hình thành từ ma trận kề cách thay (i, j) thành chuỗi i, j thành phần nằm đường chéo Ta có: AB 0 AE BA BC BE M1 = CB CD CE 0 DC DE EA EB EC ED Bước 2: Xây dựng ma trận M từ mà trận M1 cách xóa kí tự ban đầu phần tử chuỗi A M= 0 A Lưu Thị Thêm B B B 43 C C C 0 D D E E E E K20-Toán ứng dụng Luận văn thạc sĩ Bước 3: M2 = M1 ∗ M M2 = AEB ABC AEC AED ABE BEA BEC BCD BED CBA CEA CEB CED BAE BCE CBE CDE DEC DCE EBC EDC ECD DCB DEB EAB ECB DEA EBA Bước 4: M3 = M2 ∗ M  M3 = M2 ∗ M AECB BCEA  CEBA CEAB CBEA CDEB CDEA     DCBA DEAB DEBA DECB  DCEA DCEB ECBA EDCB    AEBC ABCD AEDC  AECD  ABCE ABEC ABED   BECD BEDC BAED  BCDE BAEC BCED  CBED CBAE DEBC DCBE EABC EBCD Bước 5: M4 = M3 ∗ M   AEBCD AEDCB ABEDC ABECD ABCDE ABCED BAEDC BAECD CDEAB CBAED BCDEA M4 = CDEBA   DECBA DCEBA DCEAB DEABC DCBEA EDCBA 0 Lưu Thị Thêm 44 DCBAE EABCD K20-Toán ứng dụng Luận văn thạc sĩ Kết thúc bước 5, ta có tất 20 đường Hamilton Sau kiểm tra điểm kết thúc đường Hamilton có kết nối với điểm đầu cạnh hay khơng ta tìm 10 chu trình Hamilton AEDCB ABCDE BCDEA BAEDC CDEAB CBAED DEABC DCBAE EDCBA EABCD 3.4 3.4.1 Ứng dụng: Thuật toán xấp xỉ cho toán tìm chu trình người bán hàng có trọng số tối thiểu đồ thị có trọng số Đặt vấn đề Bài tốn tìm chu trình người bán hàng: Mỗi địa điểm người bán hàng cần đến coi đỉnh đồ thị G Mỗi cách hai địa điểm coi cạnh đồ thị G Trọng số cạnh khoảng cách đỉnh Người bán hàng muốn qua tất địa điểm lần với tổng quãng đường ngắn Tức cần tìm chu trình Hamilton có trọng số tối thiểu đồ thị có trọng số G Trong thực tế, việc tìm chu trình qua đỉnh lần có trọng số tối thiểu vấn đề khó khăn khơng phải đồ thị đồ thị Hamilton Trong phần tìm hành trình có trọng số tối thiểu đồ thị có trọng số hành trình qua đỉnh lần Chúng ta chấp nhận lặp số đỉnh trọng số hành trình nhỏ Bài tốn gọi tốn tìm chu trình người bán hàng, (bài tốn (*)) Ví dụ xét đồ thị sau: Lưu Thị Thêm 45 K20-Toán ứng dụng Luận văn thạc sĩ Hình 3.10: Ta có 1) Hành trình abca có trọng số 2) Hành trình abaca có trọng số Rõ ràng với người cần qua thành phố a, b, c, thành phố lần theo chu trình khơng thiết chu trình đơn giản, lặp đỉnh mà tổng trọng số nhỏ Trong đồ thị có trọng số G, ∀u, v ∈ G, trọng số (u, v) thỏa mãn: w(u, v) ≤ w(u, x) + w(x, v), ∀x = u, x = v ta nói đẳng thức tam giác thỏa mãn G Nhận thấy rằng, G đồ thị mạng lưới đường trọng số cạnh khoảng cách thực tế bất đẳng thức tam giác thỏa mãn G Tuy nhiên, trọng số cạnh đại diện cho số lượng khác ví dụ chi phí vận chuyển bất đẳng thức tam giác khơng thỏa mãn Có kĩ thuật đơn giản để tìm lời giải tốn (*) cho đồ thị G = (V, E) chuyển đổi thành tốn tìm chu trình Hamilton có trọng số tối thiểu đồ thị G = (V , E ), V = V cạnh (u, v) ∈ E có trọng số W (u, v) khoảng cách tối thiểu từ u đến v G Như vậy, cạnh G tương ứng với đường có nhiều cạnh G Việc xây dựng G tiến hành cách dán nhãn cho cạnh G có đường dài cạnh G Ví dụ 3.4.1 Cho đồ thị G đây: Lưu Thị Thêm 46 K20-Toán ứng dụng Luận văn thạc sĩ Hình 3.11: Ta có đồ thị G : Hình 3.12: Một chu trình Hamilton có trọng số tối thiểu G ứng với lời giải cho toán (*) đồ thị G Nên ta cần liệt kê tất chu trình Hamilton sau so sánh đưa chu trình có trọng số tối thiểu Cách tiếp cận đơn giản phương pháp phải làm số lượng lớn chấp nhận tính tốn Đối với đồ thị đầy đủ, vơ hướng có n đỉnh, ta có (n − 1)! chu trình Hamilton khác Để tìm độ dài tất chu trình với tốc độ 108 phép tính / giây, nhà tốn học tính lượng thời gian sau: Lưu Thị Thêm 47 K20-Toán ứng dụng Luận văn thạc sĩ n thời gian 12 giây 15 20 800 năm 50 1049 năm Tính tốn theo mơ hình thể tốc độ tăng trưởng phi thường thời gian tăng số lượng đỉnh n Trong thực tế, ta tìm thuật tốn xấp xỉ, thực thời gian đa thức để giải toán (*) Gọi: L giá trị thu (xấp xỉ) L0 giá trị xác Ta có: L 1≤