Bài toán luồng trên mạng và ứng dụng

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

i

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NÔNG THỊ LÝ

BÀI TOÁN LUỒNG TRÊN MẠNG VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái nguyên - 2015

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

ii

LỜI CAM ĐOAN

Tôi “ Bài toán

luồng trên mạng và ứng dụng” là công trình nghiên cứu thực sự của

thân dƣới

sự hƣớng dẫn khoa học của Tiến sĩ Trƣơng Hà Hải,Trƣờng Đại học Công

nghệ Thông tin và Truyền thông- Đại học Thái Nguyên.

Tôi .

9 năm 2015

Nông Thị Lý

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

iii

LỜI CẢM ƠN

Để hoàn thành luận văn, t xin chân thành cảm ơn Trƣờng Đại học

Công nghệ Thông tin và Truyền thông–Đại học Thái Nguyên, Phòng Đào tạo,

các thầy, cô giáo giảng dạy lớp cao học Khoa học máy tính K12E đã quan

tâm, tạo điều kiện thuận lợi, tận tình giảng dạy và giúp đỡ trong thời

gian theo học tại trƣờng.

Đặc biệt, t xin bày tỏ lòng biết ơn sâu sắc đến TS.

Trƣơng Hà Hải

văn.

xin cảm ơn các cán bộ, giảng viên đồng nghiệp Trƣờng Đại

học Hùng Vƣơng đã

.

.

Xin trân trọng cảm ơn.

9năm 2015

Nông Thị Lý

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

iv

MỤC LỤC

LỜI CAM ĐOAN.......................................................................................................II

LỜI CẢM ƠN........................................................................................................... III

MỤC LỤC................................................................................................................IV

DANH MỤC CÁC BẢNG.......................................................................................VI

DANH MỤC CÁC HÌNH VẼ.................................................................................VII

MỞ ĐẦU .................................................................................................................... 1

CHƢƠNG 1................................................................................................................ 3

MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ................................ 3

1.1. .............................................................................. 3

1.1.1. Định nghĩa đồ thị .......................................................................................... 3

1.1.2. Các loại đồ thị............................................................................................... 4

1.1.3. Các khái niệm liên quan ................................................................................... 6

1.2. Biểu diễn đồ thị trên máy tính ........................................................................... 10

1.2.1. Biểu diễn bằng ma trận kề .......................................................................... 10

1.2.2. Biểu diễn bằng ma trận liên thuộc.............................................................. 11

1.2.3. Danh sách cạnh........................................................................................... 12

1.2.4. Danh sách kề............................................................................................... 13

1.2.5. Đồ thị trọng số ............................................................................................ 14

1.3. ...................................................................... 14

1.3.1. Các bài toán kinh điển ................................................................................ 14

1.3.2. Các bài toán NP-khó................................................................................... 16

1.4. Kết luận chƣơng 1 ............................................................................................. 20

CHƢƠNG 2: BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNGVÀ CÁC THUẬT

TOÁN ....................................................................................................................... 22

2.1. Phát biểu bài toán .............................................................................................. 22

2.1.1. Mạng và luồng trên mạng............................................................................... 22

2.1.2. Bài toán luồng cực đại trên mạng................................................................... 24

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

v

2.1.3. Lát cắt, định lý Ford – Fulkerson ................................................................... 24

2.2. Các thuật toán giải bài toán luồng trên mạng.................................................... 25

2.2.1. Các thuật toán hiện có .................................................................................... 25

2.2.2. Thuật toán Ford – Fulkerson .......................................................................... 26

2.2.3. Thuật toán Edmonds–Karp............................................................................. 32

2.2.4. Thuật toán Dinits............................................................................................ 32

2.2.5. Các thuật toán khác ........................................................................................ 33

2.3. Một số ứng dụng thực tế của bài toán ............................................................... 33

2.3.1. Bài toán tìm công suất bơm dầu ..................................................................... 33

2.3.2. Bài toán xét ứng cử viên vô địch.................................................................... 34

2.3.3. Bài toán tìm luồng giao thông cực đại............................................................ 35

2.4. Kết luận chƣơng 2 ............................................................................................. 36

CHƢƠNG 3:

.................................................................................................................. 37

3.1. Vấn đề tính toán số lƣợt du khách về thăm đền Hùng trong dịp lễ hội............. 37

3.2. ............................................................................................... 39

3.3. M ............................. 40

3.4. Xây dựng chƣơng trình...................................................................................... 50

3.4.1. Môi trƣờng cài đặt .......................................................................................... 50

3.4.2. Giao diện chƣơng trình................................................................................... 51

3.5. Kết quả thực nghiệm tính số lƣợt ngƣời về thăm đền Hùng năm 2015 ............ 52

3.5.1. Thực nghiệm 1: Tính toán trong ngày thứ nhất (06/03 âm lịch).................... 53

3.5.2. Thực nghiệm 2: Tính toán trong ngày thứ hai (10/03 âm lịch)...................... 56

3.5.3. Tổng hợp các kết quả thử nghiệm .................................................................. 59

3.6. Kết luận chƣơng 3 ............................................................................................. 60

KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU.............................................................. 61

TÀI LIỆU THAM KHẢO........................................................................................ 63

PHỤ LỤC

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

vi

DANH MỤC CÁC BẢNG

Bảng 2.1. Các thuật toán giải bài toán luồng cực đại.................................... 31

Bảng 3.1. Bảng chỉ số các tỉnh thành trên bản đồ......................................... 46

Bảng 3.2. So sánh kết quả tính toán và dữ liệu thực tế ................................. 71

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

vii

DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Bài toán bảy cây cầu ở Konigsberg...............................................4

Hình 1.2. Các loại đồ thị ...............................................................................6

Hình 1.3. Các dạng đồ thị đặc biệt................................................................7

Hình 1.4. Minh họa các khái niệm liên quan đến đồ thị ...............................7

Hình 1.5. Minh họa đỉnh rẽ nhánh và cầu.....................................................9

Hình 1.6. Minh họa đồ thị con và đồ thị đẳng cấu..................................... 10

Hình 1.7. Biểu diễn đồ thị bằng ma trận kề ............................................... 11

Hình 1.8. Biểu diễn đồ thị bằng ma trận liên thuộc ................................... 12

Hình 1.9. Biểu diễn đồ thị bằng danh sách cạnh........................................ 13

Hình 1.10. Biểu diễn đồ thị bằng danh sách kề.......................................... 14

Hình 2.1. Mạng và luồng trên mạng .......................................................... 23

Hình 2.2. Luồng cực đại trên mạng............................................................ 24

Hình 2.3. Lát cắt hẹp nhất mạng ................................................................ 25

Hình 2.4 Mạng ban đầu.............................................................................. 28

Hình 2.5. Khởi tạo luồng bằng 0................................................................ 28

Hình 2.6. Xây dựng mạng còn dƣ .............................................................. 29

Hình 2.7. Tăng luồng theo đƣờng ................................................... 29

Hình 2.8. Tăng luồng theo đƣờng ......................................................... 30

Hình 2.9. Tăng luồng theo đƣờng ......................................................... 30

Hình 2.10. Tính toán luồng cực đại từ mạng đã tăng luồng cực đại.......... 31

Hình 2.11. Bài toán tìm công suất bơm dầu............................................... 33

Hình 2.12. Bài toán loại bỏ ứng cử viên vô địch ....................................... 34

Hình 2.13. Bài toán tìm luồng giao thông cực đại ........................................3

Hình 3.1. Bài toán tính số lƣợt du khách tới thăm Đền Hùng - Phú Thọ .. 40

Hình 3.2. Mạng của bộ dữ liệu #1.............................................................. 42

Hình 3.3.Khởi tạo luồng bằng 0 của bộ dữ liệu #1 .................................... 43