Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
NGHIÊN cứu một số vấn đề của LÝTHUYẾT đồ THỊ ỨNG DỤNG TRONG GIẢIQUYẾT một số bài TOÁN THỰC tế
Nội dung xem thử
Mô tả chi tiết
KHOA CNTT – ĐH KHTN
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
KHOA CNTT – ĐH KHTN
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ĂN 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
KHOA CNTT – ĐH KHTN
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
KHOA CNTT – ĐH KHTN
NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
KHOA CNTT – ĐH KHTN
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
KHOA CNTT – ĐH KHTN
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
KHOA CNTT – ĐH KHTN
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 ......................................................................................................................68
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
KHOA CNTT – ĐH KHTN
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
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ình 5-4 Phát triển 1 cây xen kẽ........................................................................................52
Hình 5-5 Hai vì dụ về hoa..................................................................................................58
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ì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
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
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
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
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
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ì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
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
KHOA CNTT – ĐH KHTN
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
Hình 7-36 Lịch giao hàng dưới dạng văn bản .................................................................131
KHOA CNTT – ĐH KHTN
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ẽ
Assigment Sự phân công
Augmented forest structures Các cấu trúc rừng tăng trưởng
Augmenting path algorithm Thuật toán đường tăng trưởng
Bucket Ngăn
Capacity Độ thông qua
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
Feasible flow Luồng khả thi
Feasible solution Lời giải khả thi
Flower and blossom Hoa và nụ
Flows with lower bound Luồng có chặn dưới
Generalized flow Luồng tổng quát
Label-correcting algorithm Thuật toán hiệu chỉnh nhãn
Label-setting algorithm Thuật toán gán nhãn
Matching Sự bắt cặp
Network flows Luồng trên mạng
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
KHOA CNTT – ĐH KHTN
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
∆ -scaling phase Pha tỉ lệ ∆
Symmetric difference Sự khác biệt đối xứng
KHOA CNTT – ĐH KHTN
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
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
tìm ra ngày càng nhiều của các định lý, công thức và thuật toán.
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à
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
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
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à
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
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
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
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.
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