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ế

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

KHOA CNTT – ĐH KHTN

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

KHOA CNTT – ĐH KHTN

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