Luận văn Nghiên cứu một số vấn đề của lý thuyết đồ thị ứng dụng trong giải quyết một số bài toán thực tế

KH OA C NT T – Đ H KH TN TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP.HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM TẠ TRƯỜNG ĐỨC ANH - NGUYỄN NHẬT QUỲNH NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG GIẢI QUYẾT MỘT SỐ BÀI TOÁN THỰC TẾ LUẬN VĂN CỬ NHÂN TIN HỌC TP.HỒ CHÍ MINH, 2004 KH OA C NT T – Đ H KH TN TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP.HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM TẠ TRƯỜNG ĐỨC ANH _0012007 NGUYỄN NHẬT QUỲNH_0012082 NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG GIẢI QUYẾT MỘT SỐ BÀI TOÁN THỰC TẾ LUẬN VĂ CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN T.S DƯƠNG ANH ĐỨC NIÊN KHÓA 2000 - 2004 KH OA C NT T – Đ H KH TN NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… KH OA C NT T – Đ H KH TN NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… KH OA C NT T – Đ H KH TN LỜI CẢM ƠN Luận văn của chúng em sẽ rất khó hoàn thành nếu không có sự truyền đạt kiến thức quí báu và sự hướng dẫn tận tình của Thầy Dương Anh Đức và thầy Lê Thụy Anh. Chúng em xin chân thành cám ơn sự chỉ bảo của các thầy. Chúng con xin gửi tất cả lòng biết ơn, sự kính trọng đến ông bà, cha mẹ, cùng toàn thể gia đình, những người đã nuôi dạy, đã cho chúng con niềm tin và nghị lực để vượt qua mọi khó khăn. Chúng em xin trân trọng cám ơn quý Thầy cô trong Khoa Công nghệ thông tin trường Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng dạy, truyền đạt những kiến thức quý báu và tạo điều kiện cho chúng em được thực hiện luận văn này. Xin chân thành cám ơn sự giúp đỡ, động viên và chỉ bảo rất nhiệt tình của các anh chị đi trước và tất cả bạn bè. Các anh chị, các bạn luôn có mặt trong những thời điểm khó khăn nhất, tiếp thêm động lực và ý chí, giúp chúng tôi hoàn thành được luận văn. Mặc dù đã cố gắng nỗ lực hết sức mình, song chắc chắn luận văn không khỏi còn nhiều thiếu sót. Chúng em rất mong nhận được sự thông cảm và chỉ bảo tận tình của quý Thầy cô và các bạn. Tp.HCM, 7/2004 Nhóm sinh viên thực hiện Tạ Trường Đức Anh Nguyễn Nhật Quynh KH OA C NT T – Đ H KH TN MỤC LỤC CHƯƠNG 1 : MỞ ĐẦU ....................................................................................1 1.1. Ý nghĩa và mục tiêu của đề tài..........................................................................1 1.2. Nội dung của luận văn .......................................................................................2 CHƯƠNG 2 : TỔNG QUAN VỀ BÀI TOÁN LUỒNG TRÊN MẠNG........3 2.1. Một số khái niệm................................................................................................3 2.1.1. Đồ thị ...........................................................................................................3 2.1.2. Các phép biến đổi đồ thị ..............................................................................3 2.2. Các bài toán luồng trên mạng...........................................................................4 2.3. Một số ứng dụng cho bài toán luồng trên mạng .............................................4 2.3.1. Đường đi ngắn nhất......................................................................................4 2.3.2. Luồng cực đại ..............................................................................................4 2.3.3. Luồng có chi phí cực tiểu.............................................................................6 2.3.4. Phân công và xếp cặp...................................................................................7 2.4. Tóm tắt chương 2 ...............................................................................................7 CHƯƠNG 3 : LUỒNG CỰC ĐẠI ....................................................................8 3.1. ịnh nghĩa và ký hiệu.......................................................................................8 3.2. Luồng và lát cắt..................................................................................................8 3.2.1. Mạng thặng dư .............................................................................................9 3.2.2. Lát cắt s-t......................................................................................................9 3.2.3. Độ thông qua thặng dư của một lát cắt s-t .................................................10 3.2.4. Luồng qua một lát cắt s-t ...........................................................................10 3.3. Thuật toán đường tăng trưởng.......................................................................11 3.4. Thuật toán gán nhãn và định lý lát cắt tối thiểu ...........................................12 3.4.1. Độ phức tạp của thuật toán gán nhãn.........................................................14 3.4.2. Hạn chế của thuật toán gán nhãn ...............................................................14 3.5. Luồng có chặn dưới .........................................................................................15 3.5.1. Xác định luồng cực đại ..............................................................................16 3.5.2. Xây dựng luồng khả thi..............................................................................16 3.5.3. Mô tả đặc điểm của luồng khả thi trên mạng lưu thông ............................17 3.6. Cải tiến thuật toán đường tăng trưởng..........................................................19 3.6.1. Các nhãn khoảng cách ...............................................................................20 3.6.2. Thuật toán tỉ lệ với độ thông qua ...............................................................21 3.6.3. Thuật toán đường đi tăng trưởng ngắn nhất...............................................23 3.6.4. Thuật toán đẩy luồng .................................................................................25 3.7. Tóm tắt chương 3 .............................................................................................27 CHƯƠNG 4 : LUỒNG VỚI CHI PHÍ CỰC TIỂU ......................................28 4.1. Giới thiệu ..........................................................................................................28 4.1.1. Các giả thiết ...............................................................................................28 4.1.2. Đồ thị thặng dư ..........................................................................................29 4.2. Các điều kiện tối ưu cho bài toán ...................................................................29 4.2.1. Các điều kiện tối ưu về chu trình âm .........................................................29 4.2.2. Các điều kiện tối ưu về chi phí rút gọn......................................................29 4.2.3. Các điều kiện tối ưu bổ sung......................................................................31 4.3. Liên hệ các luồng tối ưu và các khả năng tối ưu của đỉnh ...........................31 KH OA C NT T – Đ H KH TN 4.4. Thuật toán khử chu trình âm và tính chất nguyên.......................................33 4.5. Thuật toán đường đi ngắn nhất liên tiếp .......................................................35 4.6. Thuật toán Primal-dual...................................................................................39 4.7. Các thuật toán cải tiến.....................................................................................42 4.7.1. Cải tiến thuật toán đường đi ngắn nhất liên tiếp ........................................43 4.7.2. Một số cách cải tiến khác...........................................................................43 4.8. Tóm tắt chương 4 .............................................................................................46 CHƯƠNG 5 : SỰ PHÂN CÔNG VÀ XẾP CẶP ...........................................48 5.1. Giới thiệu ..........................................................................................................48 5.1.1. Các cạnh bắt cặp và các nút bắt cặp...........................................................48 5.1.2. Đường đi xen kẽ và chu trình xen kẽ .........................................................48 5.1.3. Đường tăng trưởng.....................................................................................49 5.1.4. Sự khác biệt đối xứng ................................................................................50 5.2. Bài toán bắt cặp lớn nhất trên đồ thị phân đôi .............................................50 5.2.1. Chuyển về bài toán luồng cực đại trong mạng đơn giản ...........................50 5.2.2. Thuật toán bắt cặp lớn nhất trên đồ thị phân đôi .......................................51 5.3. Bài toán bắt cặp có trọng số trên đồ thị phân đôi .........................................55 5.3.1. Thuật toán đường đi ngắn nhất liên tiếp ....................................................55 5.3.2. Thuật toán Hungary ...................................................................................55 5.3.3. Thuật toán tỉ lệ theo chi phí .......................................................................56 5.4. Bài toán bắt cặp trên đồ thị tổng quát ...........................................................56 5.4.1. Các khó khăn gặp phải trong thuật toán bắt cặp trên mạng phân đôi ........57 5.4.2. Hoa và nụ ...................................................................................................58 5.4.3. Sự thu nhỏ nụ .............................................................................................59 5.4.4. Thuật toán bắt cặp trên đồ thị không phân đôi...........................................60 5.5. Tóm tắt chương 5 .............................................................................................64 CHƯƠNG 6 : LUỒNG TỔNG QUÁT...........................................................65 6.1. Giới thiệu ..........................................................................................................65 6.2. Các cấu trúc rừng tăng trưởng.......................................................................66 6.2.1. Luồng trên đường đi ..................................................................................66 6.2.2. Luồng trên chu trình...................................................................................68 6.2.3. Cây tăng trưởng và rừng tăng trưởng.........................................................69 6.2.4. Các cấu trúc rừng tăng trưởng và các điều kiện tối ưu ..............................71 6.3. Xác định các khả năng và luồng cho một cấu trúc rừng tăng trưởng ........73 6.3.1. Xác định khả năng của đỉnh cho một cấu trúc rừng tăng trưởng...............73 6.3.2. Xác định luồng cho một cấu trúc rừng tăng trưởng ...................................75 6.4. Tóm tắt chương 6 .............................................................................................80 CHƯƠNG 7 : XÂY DỰNG ỨNG DỤNG DISTRIBUTION........................81 7.1. Yêu cầu thực tế và lý do xây dựng ứng dụng ................................................81 7.2. Mục tiêu của ứng dụng ....................................................................................81 7.3. Tiếp cận bài toán..............................................................................................82 7.3.1. Phát biểu bài toán.......................................................................................82 7.3.2. Mô hình toán học .......................................................................................82 7.3.3. Nhận xét .....................................................................................................83 7.3.4. Hướng tiếp cận của luận văn......................................................................83 7.4. Phân tích ...........................................................................................................89 7.4.1. Yêu cầu chức năng.....................................................................................89 KH OA C NT T – Đ H KH TN 7.4.2. Mô hình Use Case......................................................................................90 7.5. Thiết kế .............................................................................................................97 7.5.1. Thiết kế dữ liệu ..........................................................................................97 7.5.2. Thiết kế xử lý ...........................................................................................102 7.5.3. Thiết kế giao diện.....................................................................................105 7.6. Biểu đồ tương tác ...........................................................................................111 7.6.1. Xem thông tin các đại lý ..........................................................................111 7.6.2. Thay đổi nhu cầu của các đại lý...............................................................113 7.6.3. Xem thông tin các phương tiện................................................................115 7.6.4. Thay đổi thông tin về các phương tiện ....................................................117 7.6.5. Tìm phương pháp vận chuyển tối ưu .......................................................119 7.6.6. Tìm đường đi ngắn nhất từ nhà cung cấp đến các đại lý .........................121 7.6.7. Xuất lịch giao hàng ..................................................................................122 7.7. Cài đặt .............................................................................................................123 7.8. Hướng dẫn sử dụng .......................................................................................124 7.8.1. Di chuyển bản đồ đến vị trí khác : ...........................................................124 7.8.2. Phóng to, thu nhỏ bản đồ : .......................................................................124 7.8.3. Để tìm đường đi ngắn nhất từ nhà cung cấp đến các đại lý:....................125 Để tìm đường đi ngắn nhất từ nhà cung cấp đến 1 đại lý nào đó:.....................125 7.8.4. Để tính toán các đường đi có chi phí thấp nhất thỏa mãn nhu cầu của các đại lý: 126 7.8.5. Xem thông tin và cập nhật nhu cầu của tất cả các đại lý .........................127 7.8.6. Xem, cập nhật thông tin hoặc thêm các phương tiện chuyên chở mới: ...129 7.8.7. Xem lịch giao hàng trong ngày của các phương tiện...............................130 7.9. Tổng kết ..........................................................................................................132 7.9.1. Kết luận....................................................................................................132 7.9.2. Hướng phát triển ......................................................................................132 KH OA C NT T – Đ H KH TN DANH SÁCH CÁC ĐỊNH LÝ, TÍNH CHẤT, MỆNH ĐỀ Tính chất 3.1. .....................................................................................................................11 Tính chất 3.2 ......................................................................................................................11 Định lý 3.3: định lý Ford – Fullkerson về lát cắt nhỏ nhất ................................................14 Định lý 3.4: định lý về đường tăng trưởng ........................................................................14 Định lý 3.5: định lý về tính nguyên ...................................................................................14 Định lý 3.6: Định lý lát cắt nhỏ nhất mở rộng ...................................................................16 Định lý 3.7: điều kiện tồn tại luồng khả thi trên mạng lưu thông......................................19 Định lý 3.8 .........................................................................................................................19 Tính chất 3.9 ......................................................................................................................21 Tính chất 3.10 ...................................................................................................................21 Định lý 4.1: Các điều kiện tối ưu về chu trình âm.............................................................29 Tính chất 4.2 .....................................................................................................................30 Định lý 4.3: Các điều kiện tối ưu với chi phí rút gọn ........................................................30 Định lý 4.4 :Các điều kiện tối ưu bổ sung .........................................................................31 Định lý 4.5: Tính chất nguyên ...........................................................................................35 Bổ đề 4.6 ...........................................................................................................................36 Bổ đề 4.7 ............................................................................................................................36 Định lý 5.1: định lý về đường tăng trưởng ........................................................................49 Tính chất 5.2 ......................................................................................................................50 Tính chất 5.3 ......................................................................................................................58 Tính chầt 5.4 ......................................................................................................................59 Bổ đề 5.5 ............................................................................................................................64 Tính chất 6.1 ......................................................................................................................67 Tính chất 6.2 ...............................................................................................