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ế

Chia sẻ: Nguyen Bao Ngoc | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

362
lượt xem 67
download

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

Với sự hướng dẫn của Tiến sĩ Dương Anh Đức, chúng em đã tập trung thực hiện đề tài “NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG VIỆC GIẢI QUYẾT BÀI TOÁN THỰC TẾ” nhằm tìm hiểu, thử nghiệm và ứng dụng các thuật toán của bài toán luồng trên mạng, nhất là bài toán luồng có chi phí cực tiểu, dạng tổng quát nhất của bài toán luồng trên mạng, trong đó bao gồm việc xây dựng ứng dụng Distribution phục vụ cho việc lập kế hoạch giao hàng của nhà phân phối...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ế

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 TN H TẠ TRƯỜNG ĐỨC ANH - NGUYỄN NHẬT QUỲNH K H Đ NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ – THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG GIẢI TT QUYẾT MỘT SỐ BÀI TOÁN THỰC TẾ N C A O LUẬN VĂN CỬ NHÂN TIN HỌC H K TP.HỒ CHÍ MINH, 2004
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 TN TẠ TRƯỜNG ĐỨC ANH _0012007 NGUYỄN NHẬT QUỲNH_0012082 H K NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ H Đ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG GIẢI QUYẾT MỘT SỐ BÀI TOÁN THỰC TẾ – TT LUẬN VĂN CỬ NHÂN TIN HỌC N C GIÁO VIÊN HƯỚNG DẪN A T.S DƯƠNG ANH ĐỨC O H K NIÊN KHÓA 2000 - 2004
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… TN …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… H …………………………………………………………………………………… K …………………………………………………………………………………… …………………………………………………………………………………… H …………………………………………………………………………………… …………………………………………………………………………………… Đ …………………………………………………………………………………… – …………………………………………………………………………………… …………………………………………………………………………………… TT …………………………………………………………………………………… …………………………………………………………………………………… N …………………………………………………………………………………… …………………………………………………………………………………… C …………………………………………………………………………………… …………………………………………………………………………………… A …………………………………………………………………………………… O …………………………………………………………………………………… H …………………………………………………………………………………… …………………………………………………………………………………… K …………………………………………………………………………………… …………………………………………………………………………………… ……………………………………………………………………………………
NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… TN …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… H …………………………………………………………………………………… K …………………………………………………………………………………… …………………………………………………………………………………… H …………………………………………………………………………………… …………………………………………………………………………………… Đ …………………………………………………………………………………… – …………………………………………………………………………………… …………………………………………………………………………………… TT …………………………………………………………………………………… …………………………………………………………………………………… N …………………………………………………………………………………… …………………………………………………………………………………… C …………………………………………………………………………………… …………………………………………………………………………………… A …………………………………………………………………………………… O …………………………………………………………………………………… H …………………………………………………………………………………… …………………………………………………………………………………… K …………………………………………………………………………………… …………………………………………………………………………………… ……………………………………………………………………………………
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à TN 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, H 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 K 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 H 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 TT 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. N C Tp.HCM, 7/2004 A Nhóm sinh viên thực hiện Tạ Trường Đức Anh O Nguyễn Nhật Quynh H K
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 TN 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 H 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 K 2.4. Tóm tắt chương 2 ...............................................................................................7 CHƯƠNG 3 : LUỒNG CỰC ĐẠI ....................................................................8 H 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 TT 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 N 3.5. Luồng có chặn dưới .........................................................................................15 3.5.1. Xác định luồng cực đại ..............................................................................16 C 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 A 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 O 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 H 3.7. Tóm tắt chương 3 .............................................................................................27 CHƯƠNG 4 : LUỒNG VỚI CHI PHÍ CỰC TIỂU ......................................28 K 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
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 TN 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 H 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 K 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 H 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 TT 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 N 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 C 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 A 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 O 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 H CHƯƠNG 7 : XÂY DỰNG ỨNG DỤNG DISTRIBUTION........................81 K 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
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 TN 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 H 7.8. Hướng dẫn sử dụng .......................................................................................124 7.8.1. Di chuyển bản đồ đến vị trí khác : ...........................................................124 K 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 H 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 TT 7.9.2. Hướng phát triển ......................................................................................132 N C A O H K
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 TN 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 H Đị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 K Định lý 4.5: Tính chất nguyên ...........................................................................................35 Bổ đề 4.6 ...........................................................................................................................36 Bổ đề 4.7 ............................................................................................................................36 H Đị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 ......................................................................................................................68 TT Tính chất 6.3 ......................................................................................................................69 Tính chất 6.4 ......................................................................................................................69 Định lý 6.5: Các điều kiện tối ưu về luồng tổng quát ........................................................71 Tính chất 6.6: Các điều kiện tối ưu về cấu trúc rừng tăng trưởng .....................................72 N C A O H K
DANH SÁCH CÁC HÌNH Hình 2-1 ...............................................................................................................................6 Hình 3-1 Mô tả mạng thặng dư ............................................................................................9 Hình 3-2 Ví dụ về một lát cắt s – t .....................................................................................10 Hình 3-3 Ví dụ về một mạng tăng trưởng ....................................................................11 Hình 3-4: Bài toán luồng cực đại không có luồng tương thích..........................................15 Hình 3-5 Minh họa đồ thị thặng dư ...................................................................................22 Hình 4-1 Minh họa thuật toán Khử chu trình âm..............................................................34 Hình 4-2 Minh họa thuật toán đường đi ngắn nhất liên tiếp ..............................................39 TN Hình 4-3 Minh họa thuật toán Primal - dual ......................................................................42 Hình 5-1 Minh họa sự bắt cặp gồm 2 phần tử ...................................................................48 Hình 5-2 Minh họa sự bắt cặp gồm 3 phần tử ...................................................................49 Hình 5-3: Chuyển đổi bài toán bắt cặp các thành phần thành bài toán luồng cực đại .......51 H Hình 5-4 Phát triển 1 cây xen kẽ ........................................................................................52 Hình 5-5 Hai vì dụ về hoa ..................................................................................................58 K Hình 5-6 Sự thu gọn hoa ....................................................................................................59 Hình 5-7 Xác định 1 luồng tăng trưởng trong mạng thu gọn ............................................63 Hình 5-8 Xác định 1 đường tăng trưởng trong mạng ban đầu ...........................................64 H Hình 6-1: Luồng trên đường đi trong 1 đồ thị tổng quát ...................................................67 Hình 6-2 Ví dụ về cây tăng trưởng và luồng tăng trưởng ..................................................70 Hình 6-3 Minh họa tính toán các khả năng của đỉnh .........................................................75 Đ Hình 6-4 Tính luồng trên các cung thuộc cây ....................................................................76 Hình 6-5 Minh họa quá trình tính luồng cho 1 cây tăng trưởng ........................................78 – Hình 7-1 Mô hình bài toán phân phối hàng .......................................................................85 Hình 7-2 Biểu đồ Use Case................................................................................................90 TT Hình 7-3 Sơ đồ các lớp dữ liệu ..........................................................................................97 Hình 7-4 Mô tả dữ liệu tính toán .....................................................................................102 Hình 7-5 Sơ đồ lớp sử lý ..................................................................................................102 Hình 7-6 Sơ đồ các màn hình ..........................................................................................105 N Hình 7-7 Thực đơn của ứng dụng ....................................................................................105 Hình 7-8 Thanh công cụ của ứng dụng ............................................................................106 C Hình 7-9 Màn hình chính .................................................................................................108 Hình 7-10 Màn hình thay đổi nhu cầu của một đại lý .....................................................108 Hình 7-11 Màn hình thay đổi nhu cầu của tất cả các đại lý .............................................109 A Hình 7-12 Màn hình xem thông tin, cập nhật thêm mới phương tiện .............................110 Hình 7-13 Màn hình xem lịch giao hàng tối ưu về chi phí ..............................................110 O Hình 7-14 Sequence Diagram: Xem thông tin các đại lý ................................................111 Hình 7-15 Collaboration Diagram: Xem thông tin các đại lý..........................................112 H Hình 7-16 Sequence Diagram: Thay đổi nhu cầu của các đại lý .....................................113 Hình 7-17 Collaboration Diagram: Thay đổi nhu cầu của các đại lý ..............................114 K Hình 7-18 Sequence Diagram: Xem thông tin các phương tiện ......................................115 Hình 7-19 Collaboration Diagram: Xem thông tin các phương tiện ...............................116 Hình 7-20 Sequence Diagram: Thay đổi thông tin về các phương tiện ...........................117 Hình 7-21 Collaboration Diagram: Thay đổi thông tin về các phương tiện ....................118 Hình 7-22 Sequence Diagram: Tìm phương pháp vận chuyển tối ưu .............................119 Hình 7-23 Collaboration Diagram: Tìm phương pháp vận chuyển tối ưu .......................120 Hình 7-24 Sequence Diagram: Tìm đường đi ngắn nhất từ nhà cung cấp đến các đại lý 121 Hình 7-25 Collaboration Diagram: Tìm đường đi ngắn nhất từ nhà cung cấp đến các đại lý ......................................................................................................................................121
Hình 7-26 Sequence Diagram: Xuất lịch giao hàng ........................................................122 Hình 7-27 Collaboration Diagram: Xuất lịch giao hàng..................................................123 Hình 7-28 Màn hình chính ..............................................................................................124 Hình 7-29 Đường đi ngắn nhất từ nhà cung cấp đến các đại lý .......................................125 Hình 7-30 Đường đi ngắn nhất từ nhà cung cấp đến một đại lý ......................................126 Hình 7-31 Đường đi có chi phí thấp nhất ........................................................................127 Hình 7-32 Màn hình cập nhật thông tin các đại lý...........................................................128 Hình 7-33 Màn hình cập nhật nhu cầu cho 1 đại lý .........................................................129 Hình 7-34 Màn hình thêm mới, cập nhật thông tin cho các phương tiện ........................130 Hình 7-35 Màn hình hiển thị lịch giao hàng ....................................................................131 TN Hình 7-36 Lịch giao hàng dưới dạng văn bản .................................................................131 H K H Đ – TT N C A O H K
BẢNG TỪ ANH_VIỆT Tiếng Anh Tiếng Việt Admissible path Đường đi có thể chấp nhận Advance Tiến tới Alternating Xen kẽ Alternating tree Cây xen kẽ TN Assigment Sự phân công Augmented forest structures Các cấu trúc rừng tăng trưởng H Augmenting path algorithm Thuật toán đường tăng trưởng Bucket Ngăn K Capacity Độ thông qua H Composite cost Chi phí kết hợp Cut Lát cắt Đ Cycle-canceling Khử chu trình – Decomposition Sự phân rã Distance label Nhãn khoảng cách TT Feasible flow Luồng khả thi Feasible solution Lời giải khả thi N Flower and blossom Hoa và nụ C Flows with lower bound Luồng có chặn dưới Generalized flow Luồng tổng quát A Label-correcting algorithm Thuật toán hiệu chỉnh nhãn O Label-setting algorithm Thuật toán gán nhãn H Matching Sự bắt cặp Network flows Luồng trên mạng K Nonsaturating Chưa bão hòa NP-complete NP-đầy đủ ε -optimal flows Luồng tối ưu ε Priority list Danh sách ưu tiên
Pseudoflow Luồng giả Reduced cost Chi phí rút gọn Residual capacity Độ thông qua thặng dư Residual network Mạng thặng dư Retreat Quay lui Saturating Bão hòa TN ∆ -scaling phase Pha tỉ lệ ∆ Symmetric difference Sự khác biệt đối xứng H K H Đ – TT N C A O H K
CHƯƠNG 1: MỞ ĐẦU CHƯƠNG 1 : MỞ ĐẦU 1.1. Ý nghĩa và mục tiêu của đề tài Lý thuyết đồ thị là ngành khoa học xuất hiện từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi nhà toán học Thụy Sĩ Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán cây cầu TN Konigsberg nổi tiếng. Từ đó lý thuyết đồ thị ngày càng khẳng định được vị trí quan trọng của mình trong việc áp dụng để giải các bài toán thực tế nhờ vào việc H tìm ra ngày càng nhiều của các định lý, công thức và thuật toán. K Một bộ phận quan trọng của lý thuyết đồ thị là dạng bài toán luồng trên mạng, xuất hiện từ những nghiên cứu của Gustav Kirchhoff, và được những nhà H nghiên cứu tiên phong như Lester Ford và Ray Fulkerson phát triển thành một lĩnh vực khoa học độc lập. Bài toán này có nhiều biến thể như: bài toán luồng có chi Đ phí cực tiểu, bài toán đường đi ngắn nhất, bài toán luồng cực đại, bài toán vận – chuyển, bài toán luồng tổng quát, bài toán luồng nhiều mặt hàng… Với sự xuất hiện ngày càng nhiều của các hệ thống mạng như: hệ thống TT mạng điện, mạng sản xuất và phân phối hàng hóa, mạng giao thông …, và phổ biến nhất hiện nay là mạng internet đã làm nảy sinh ra nhu cầu vận chuyển các N chất liệu trên các mạng này sao cho đạt hiệu quả cao nhất; chất liệu ở đây có thể là C dòng điện, dữ liệu, hàng hóa…; hiệu quả ở đây có thể xét theo tiêu chuẩn về thời gian, độ dài quãng đường, chi phí tiền bạc, mức độ an toàn…, bài toán luồng trên A mạng ngày càng khẳng định được tính quan trọng của nó trong các ngành khoa học O hiện đại. Sự phát triển mạnh mẽ của ngành công nghệ thông tin cùng với khả năng H tính toán rất nhanh của máy tính đã giúp việc giải quyết các bài toán luồng trên mạng hiệu quả hơn và đem lại nhiều ứng dụng thực tiễn hơn. K Với sự hướng dẫn của Tiến sĩ Dương Anh Đức, chúng em đã tập trung thực hiện đề tài “NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG VIỆC GIẢI QUYẾT BÀI TOÁN THỰC TẾ” nhằm tìm hiểu, thử nghiệm và ứng dụng các thuật toán của bài toán luồng trên mạng, nhất là bài toán luồng có chi phí cực tiểu, dạng tổng quát nhất của bài toán luồng trên 1
CHƯƠNG 1: MỞ ĐẦU mạng, trong đó bao gồm việc xây dựng ứng dụng Distribution phục vụ cho việc lập kế hoạch giao hàng của nhà phân phối đến các đại lý với chi phí tối thiểu. 1.2. Nội dung của luận văn Luận văn gồm 7 chương: Chương 1: Mở đầu giới thiệu tổng quan về đề tài. Chương 2: Tổng quan về lý thuyết đồ thị giới thiệu một số khái niệm, TN phép biến đổi được sử dụng trong bài toán luồng trên mạng và một số lớp bài toán luồng trên mạng cùng ứng dụng của chúng. H Chương 3: Bài toán luồng cực đại mô tả bài toán luồng cực đại, giới thiệu khái niệm lát cắt cùng với thuật toán tổng quát, và đưa ra một số thuật toán cải tiến K để giải bài toán này. H Chương 4: Bài toán luồng có chi phí cực tiểu định nghĩa bài toán luồng có chi phí cực tiểu, các điều kiện tối ưu của bài toán, các thuật giải tổng quát và Đ một số cải tiến nhằm tối ưu hóa thời gian chạy của thuật toán. – Chương 5: Bài toán phân công và bắt cặp giới thiệu 3 dạng tiêu biểu là bài toán bắt cặp lớn nhất trên đồ thị phân đôi, bài toán bắt cặp có trọng số trên đồ TT thị phân đôi, bài toán bắt cặp trên đồ thị tổng quát. Chương này cũng đưa ra một ví dụ và các thuật toán để giải các bài toán này. N Chương 6: Luồng tổng quát tập trung vào các cấu trúc cây tăng trưởng và C rừng tăng trưởng, cách xác định khả năng và luồng cho một cấu trúc rừng tăng trưởng. A Chương 7: Xây dựng ứng dụng Distribution trình bày về thuật toán cơ O bản để xây dựng nên chương trình, cơ sở dữ liệu, hướng dẫn sử dụng chương trình. H K 2
CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ CHƯƠNG 2 : TỔNG QUAN VỀ BÀI TOÁN LUỒNG TRÊN MẠNG 2.1. Một số khái niệm Trong phần này, chúng ta liệt kê một số khái niệm cơ bản và các phép biến TN đổi đồ thị sẽ được sử dụng trong luận văn: 2.1.1. Đồ thị H Đồ thị có hướng và vô hướng. K Đỉnh đầu và đỉnh cuối. Bậc của đỉnh. H Đường đi. Đ Chu trình. Sự liên thông. – Lát cắt. TT Cây. Mạng thặng dư. N 2.1.2. Các phép biến đổi đồ thị C Một số phép biến đổi đồ thị được sử dụng nhằm biến đổi một đồ thị tổng quát thành một đồ thị đơn giản, nhờ đó, ta có thể áp dụng các thuật toán vào những A đồ thị này. Đó là các phép biến đổi: O Loại bỏ chặn dưới khác 0 của cạnh. H Loại bỏ chặn trên của cạnh. Đảo cạnh. K Tách nút. 3
CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ 2.2. Các bài toán luồng trên mạng Các bài toán thuộc lớp bài toán luồng trên mạng: Bài toán luồng có chi phí cực tiểu (minimum cost flow problem). Bài toán đường đi ngắn nhất (shortest path problem). Bài toán luồng cực đại (maximum flow problem). TN Bài toán phân công (assignment problem). Bài toán vận tải (transportation problem). H Bài toán lưu thông (circulation problem). Bài toán luồng đa hàng hóa (multicommodity flow problem). K Bài toán cây khung tối tiểu (minimum spanning tree H problem). Bài toán cặp ghép (matching problem). Đ 2.3. Một số ứng dụng cho bài toán luồng trên mạng – Bài toán luồng trên mạng có rất nhiều ứng dụng trong thực tế. Có những bài toán TT ta dễ dàng nhận thấy sự hiện diện của mạng, nhưng cũng có những bài toán mạng bị che khuất bởi phát biểu của nó. Để áp dụng được các thuật toán luồng trên mạng ta phải thiết lập được mô hình mạng cho các bài toán này. Sau đây là một số ứng dụng thực tế, được trình bày theo các lớp bài toán luồng trên mạng. N 2.3.1. Đường đi ngắn nhất C Bài toán chở hàng trên tàu. A Lập lịch cho tổng đài viên. O Xếp sách trong thư viện. Bài toán đổi tiền (có thể ứng dụng với máy bán hàng tự động). H 2.3.2. Luồng cực đại K 2.3.2.1. Ứng dụng 1 : Luồng khả thi Bài toán luồng khả thi là bài toán xác định một luồng trên mạng thỏa mãn các ràng buộc sau : ∑ ∑ xij = b(i)∀i ∈ N xij − (2.1) { j:(i , j )∈A} { j:( j ,i )∈A} 4
CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ 0 ≤ xij ≤ u ij ∀(i, j ) ∈ A (2.2) ∑ b(i) = 0 Trong đó : i∈N Ta có thể giải bài toán luồng khả thi bằng cách tìm luồng cực đại trên một mạng G’ như sau: ta thêm vào hai nút mới, một nút nguồn s và một nút đích t. Với mỗi nút có b(i) > 0, ta thêm vào cung (s,i) với độ thông qua là b(i), và với mỗi nút b(i) có b(i) < 0, ta thêm vào cung (i,t) với độ thông qua là –b(i). Sau đó giải bài TN toán luồng cực đại truyền từ s đến t trên mạng này. Nếu tất cả các cung (s,i) và (j,t) đều bão hoà (nghĩa là xsi = usi và xjt = ujt ) thì bài toán có luồng khả thi, ngược lại là H không có luồng khả thi. Bài toán luồng khả thi có một số ứng dụng thực tế, chẳng hạn: ứng dụng về K phân phối hàng hoá. Trên một mạng lưới các hải cảng một số cảng có hàng hoá H khác mà những cảng khác cần. Ta biết lượng hàng có tại các cảng, biết nhu cầu về các loại hàng hoá này cũng như biết khả năng vận chuyển tối đa trên mỗi tuyến Đ đường. Ta cần biết liệu có thể đáp ứng được mọi nhu cầu dựa trên các nguồn cung – cấp trong mạng hay không. TT 2.3.2.2. Ứng dụng 2 : Bài toán bầu chọn đại biểu Một thị trấn có r cư dân : R1 , R2 , …, Rr; q câu lạc bộ : C1 , C2 ,…, Cq; và p N đảng phái chính trị : P1 , P2 , …, Pp. Mỗi người dân tham gia ít nhất 1 CLB và theo duy nhất một đảng. Mỗi C CLB phải chọn 1 trong số các thành viên của nó làm đại diện cho hội đồng thị trấn A sao cho số thành viên hội đồng của một đảng Pk không quá uk người. O Bài toán đặt ra nhằm trả lời: có thể tìm đựơc một hội đồng đáp ứng được yêu cầu trên hay không? H Giả sử r = 7 , q = 4 , p = 3 . K Ta biểu diễn bài toán trên như sau : 5
CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ TN H K H Đ Hình 2-1 – Ri biểu diễn cho cư dân i TT Cj biểu diễn cho câu lạc bộ j Pk biểu diễn cho tổ chức chính trị k Cạnh (Ci, Rj) cho biết cư dân Rj là thành viên của câu lạc bộ Cj. N Cạnh (Rj, Pk) cho biết cư dân Rj tham gia đảng Pk. C Cạnh (Pk, t) có trọng lượng là uk đơn vị . A Các cạnh còn lại có trọng lượng 1 đơn vị . Bài toán trên giải bằng cách giải bài toán luồng cực đại từ đỉnh s đến đỉnh t. O Nếu luồng cực đại có giá trị bằng q thì ta có lời giải tối ưu . H 2.3.3. Luồng có chi phí cực tiểu K Ứng dụng của bài toán luồng có chi phí cực tiểu là bài toán giao hàng từ một nhà phân phối đến các đại lý sẽ được mô tả chi tiết trong phần chương trình ứng dụng. 6
CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ 2.3.4. Phân công và xếp cặp Trong một số trường hợp, chúng ta muốn phân bổ con người với các công việc, phòng ở hoặc với một người khác. Mỗi sự phân công này đều được đánh giá mức độ hợp lý và chúng ta mong muốn phân công sao cho đạt được mức đánh giá cao nhất. Sau đây là một số ứng dụng về phân công nhân sự. Ví dụ: Một công ty cần thuê n nhân viên cho n chỗ làm dựa trên các cuộc kiểm tra TN về khả năng , điểm tốt nghiệp và thư giới thiệu. Dùng chỉ số uij biểu diễn sự phân công nhân viên i vào công việc j. Giá trị của uij là sự đánh giá cho sự phân công này. Mục tiêu của chúng ta là xác định một cách phân công sao cho tổng chỉ số uij H là lớn nhất. K Một huấn luyện viên bơi lội phải lựa chọn từ 8 vận động viên xuất sắc nhất một đội bơi tiếp sức gồm 4 người. Mỗi người sẽ bơi một kiểu (bơi sấp, bơi ngửa, H bơi bướm, bơi tự do). Huấn luyện viên biết rõ thời gian cho mỗi vận động viên Đ thực hiện kiểu bơi của mình. Vấn đề đặt ra là phải tìm ra một đội với các vận động viên và thứ tự bơi phù hợp sao cho tổng thời gian tiếp sức giữa hai kiểu bơi là ít – nhất. Nhận thấy bài toán phân công này có |N1|>|N2|. Tuy nhiên, chúng ta có thể TT thêm vào một số các nút giả nhằm làm cho |N1| = |N2| . 2.4. Tóm tắt chương 2 N Trong chương 2, chúng em liệt kê một số khái niệm, và một số phép biến C đổi đồ thị mà chúng em sẽ dùng trong luận văn này. Ngoài ra, chúng em cũng mô tả sơ lược về một số ứng dụng của bài toán luồng trên mạng trong thực tế. Các A thuật toán để giải các bài toán này sẽ được chúng em trình bày trong các chương O sau. H K 7