BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2

THẨM HỮU HIỀN

TÌM LUỒNG CỰC ĐẠI VÀ THỨ CẤP,
ỨNG DỤNG GIẢI BÀI TOÁN TÌM ĐƢỜNG CONG TRONG
GIAO THÔNG

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

HÀ NỘI, 2016


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2

THẨM HỮU HIỀN

TÌM LUỒNG CỰC ĐẠI VÀ THỨ CẤP,
ỨNG DỤNG GIẢI BÀI TOÁN TÌM ĐƢỜNG CONG TRONG
GIAO THÔNG

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

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

Ngƣời hƣớng dẫn khoa học: PGS.TS. Lê Huy Thập

HÀ NỘI, 2016


Thẩm Hữu Hiền


iii

MỤC LỤC
MỞ ĐẦU .......................................................................................................... 1
CHƢƠNG 1: CƠ SỞ LÝ THUYẾT .............................................................. 3
1.1. Tổng quan mạng vận tải ....................................................................... 3
1.1.1. Phương pháp quản lý mạng xe buýt ................................................. 3
1.1.2. Phương pháp quản lý mạng xe khách ............................................... 3
1.2. Tổng quan đơn đồ thị, hữu hạn và vô hƣớng ..................................... 6
1.2.1. Bậc của Đỉnh trong đồ thị ................................................................. 9
1.2.2. Đường đi, chu trình ......................................................................... 12
1.2.3. Cây .................................................................................................. 14
CHƢƠNG 2: MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ .......................... 17
2.1. Giới thiệu một số thuật toán trên đồ thị ........................................... 17
2.1.1. Tìm đường đi giữa hai đỉnh của đồ thị ........................................... 17
2.1.2. Duyệt các cạnh cầu của đồ thị ........................................................ 22
2.1.3. Duyệt các đỉnh trụ của đồ thị .......................................................... 27
2.1.4. Xác định tinh liên thông................................................................. 34
2.1.5. Thuật toán tìm luồng cực đại trong mạng....................................... 38
2.2. Phát biểu và thuật toán tìm luồng cực đại ........................................ 39
2.2.1. Bài toán ........................................................................................... 39
2.2.2. Thuật toán giải bài toán tìm luồng cực đại và cực đại thứ cấp ....... 40
CHƢƠNG 3:TÌM LUỒNG CỰC ĐẠI VÀ THỨ CẤP MẠNG VẬN TẢI47
3.1. Giới thiệu công ty cần quản lý mạng vận tải. ................................... 47
3.2. Mục đích và nhiệm vụ giải bài toán. ................................................. 47
3.3. Các giao diện và kết quả chạy chƣơng trình demo.......................... 48



Độ tin cậy (confidence)



Phép giao



Phép hợp



Tập rỗng



Tập hợp con của tập



Thuộc về



không thuộc

∑


Hình 1.7: Đường đi trên đồ thị ....................................................................... 13
Hình 1.8: Rừng có 3 cây ................................................................................. 14
Hình 2.1: Chỉ số của các đỉnh………………………………..……… .......... 33
Hình 2.2: Ví dụ tồi tệ đối với thuật toán Ford_Fulkerson. ............................. 45
Hình 2.3: Tăng luồng dọc theo đường tăng .................................................... 46
Hình 3.1: Giao diện màn hình chính……………………………… .............. 52
Hình 3.2: Nhập danh sách các loại xe ............................................................ 52
Hình 3.3: Nhập Danh sách lái xe. ................................................................... 53
Hình 3.4: Nhập tuyến và thông lượng. ............................................................ 53
Hình 3.5: Nhập các hành trình. ...................................................................... 54
Hình 3.6: Sửa danh sách các loại xe. ............................................................. 55


vi

DANH MỤC BẢNG
Bảng 2.1 . Kiểm nghiệm thuật toán duyệt các cạnh cầu của đồ thị................ 24
Bảng 2.2. Kiểm nghiệm thuật toán duyệt các đỉnh trụ của đồ thị .................. 29
Bảng 2.3. Kiểm nghiệm thuật toán kiểm tra tính liên thông mạnh ................. 36


1

MỞ ĐẦU
1. Lý do chọn đề tài
Mạng Vận Tải hết sức quan trọng đối với nền kinh tế của một quốc gia
trong đó có Việt Nam chúng ta. Mạng Vận Tải là cốt lõi cho sự phát triển giao
thương kinh tế - xã hội . Hiện nay Việt Nam đang xây dựng những cơ s hạ
tầng vận tải hiện đại, để thúc đẩy giao thông phát triển đi đôi với việc hiệu
quả đáp ứng tối đa mà mạng vận tải đem lại.

4. Đối tƣợng và phạm vi nghiên cứu
- Đối tượng nghiên cứu: Luồng cực đại và thứ cấp.
- Phạm vi nghiên cứu: Ứng dụng giải bài toán tìm đường trong mạng
giao thông.
5. Phƣơng pháp nghiên cứu
- Phương pháp lấy ý kiến chuyên gia về luồng cực đại và thứ cấp để có
thể thiết kế được chương trình phù hợp với yêu cầu thực tiễn.
- Phương pháp nghiêm cứu lý luận qua tài liệu liên quan đến luồng
cực đại và thức cấp, nhằm xây dựng cơ s lý thuyết để giải quyết các vấn đề
của luận văn.
- Phương pháp thực nghiệm thông qua quan sát thực tế, yêu cầu của cơ
s , những lý luận được nghiên cứu và kết quả đạt được qua những phương
pháp trên.
6. Dự kiến kết quả đạt đƣợc
- Xác định luồng cực đại và thứ cấp trong mạng vận tải, ứng dụng giải bài
toán tìm đường trong giao thông.
- Xây dựng được chương trình demo hỗ trợ tìm đường đi trong mạng vận tải
của công ty TNHH Hồng Thịnh.


3

CHƢƠNG 1: CƠ SỞ LÝ THUYẾT
1.1. Tổng quan mạng vận tải
1.1.1. Phương pháp quản lý mạng xe buýt
* Giám sát hành trình và lợi ích mang lại:
- Lắp đặt thiết bị giám sát hành trình hộp đen lên xe, có thể quản lý,
giám sát, điều hành phương tiện của bạn

bất kì nơi đâu, bất kì khi nào.

oanh nghiệp quản lý được vị trí, tốc độ, số km hành trình của

phương tiện tại mọi thời điểm bằng nhiều báo cáo chi tiết, đa dạng giúp nhà
quản lý nhanh chóng tổng hợp tình hình.
- Trích xuất các báo cáo chi tiết nhằm giúp doanh nghiệp lên kế hoạch,
hành trình hợp lý cho đội xe, kịp thời điều chỉnh, tính toán định mức nguồn
nhiên liệu, nhân lực, thời gian…
* Tính năng quản lý:
- Quản lý đóng m cửa (Áp dụng với xe khách).
- Xem lại lộ trình xe trong quá khứ.
- Báo cáo dừng đỗ: Biển số; thông tin lái xe; thời gian dừng/đỗ; vị trí
dừng đỗ.
- Báo cáo nhiên liệu hiện có trên xe.
- Báo cáo tổng hợp tình trạng hoạt động.
- Quản lý ra vào trạm kiểm soát.
- ảnh báo xe mất tín hiệu GPS, GPRS.
- Tìm kiếm xe theo bán kính.
- Tính km đường GPS trên bản đồ.
- Tìm kiếm địa chỉ trên bản đồ.
- Báo cáo đóng m cửa: Biển số; thông tin lái xe; thời điểm đóng m
cửa; vị trí.
- Giám sát vị trí và lộ trình xe theo thời gian thực trên nền bản đồ và
bản đồ vệ tinh.
- Thu thập được thông tin vị trí, tốc độ, thời gian lái xe, số km hành
trình…


5

-


6

- Giúp mình đoán cho các tài xế ô tô trong trường hợp xảy va chạm
giao thông.
- Giải quyết các khiếu kiện giữa tài xế và hành khách.
- Tăng chất lượng và niềm tin với khách quan, giám sát và làm cơ s
để nâng cao chất lượng phục vụ hành khách.
- Bảo vệ các tình trạng an ninh trong công tác quản lý vận chuyển hành
khách: trộm cướp, móc túi, mất mát.
- Cung cấp hình ảnh chụp luân phiên theo 3 phút/ 5 phút/ 10 phút.
- Gắn quay vào trong có thể thấy được các trạng thái hành khách, số
lượng, khuôn mặt rõ nét; gắn quay ra ngoài có thể thấy được hình ảnh phía trước
xe đang chạy, ghi nhận tình trạng: Đóng phạt, kẹt xe, đường, quang cảnh.
- Hình ảnh có thể lưu lại trong thời gian 60 ngày, phục vụ bất cứ quá
trình điều tra với chứng cứ khách quan trung thực.
1.2. Tổng quan đơn đồ thị hữu hạn và vô hƣớng
- Định ngh a về đồ thị
Đồ thị là một cấu trúc dữ liệu (hay là một bức tranh) rời rạc bao gồm
các đỉnh và các cạnh nối các đỉnh này.
ác loại đồ thị đồ thị được phân biệt b i kiểu và số lượng cạnh nối
hai đỉnh nào đó của đồ thị.
Để có thể hình dung được tại sao lại cần đến các loại đồ thị khác nhau,
chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả một mạng máy tính. Giả sử ta
có một mạng gồm các máy tính và các kênh điện thoại (gọi tắt là kênh thoại)
nối các máy tính này.

húng ta có thể biểu diễn các vị trí đặt náy tính b i

các điểm và các kênh thoại nối chúng b i các đoạn nối.

Hình 1.3: Sơ đồ mạng máy tính với kênh thoại thông báo
Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị
nào cũng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh
nối một cặp đỉnh nào đó.
Trong mạng máy tính có thể có những kênh thoại nối một náy
nào đó với chính nó (chẳng hạn vời mục đính thông báo). Mạng như vậy được
cho trong hình 3. Khi đó đa đồ thị không thể mô tả được mạng như vậy, b i vì
có những khuyên (cạnh nối một đỉnh với chính nó). Trong trường hợp
nàychúng ta cần sử dụng đến khái niệm giả đồ thị vô hướng, được định nghĩa
như sau:
Định ngh a 1.3
Giả đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh và E là tập
các cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau)
của V gọi là cạnh. ạnh e được gọi là khuyên nếu nó có dạng e = (u, u).


9

Hình 1.4: Mạng máy tính với kênh thoại một chiều
ác kênh thoại trong mạng máy tính có thể chỉ cho phép truyền tin theo
một chiều. hẳng hạn, trong hình 4 máy chủ
các máy

Hà Nội chỉ có thể nhận tin từ

địa phương, có một số máy chỉ có thể gửi tin đi, còn các kênh thoại

cho phép truyền tin theo cả hai chiều được thay thế b i hai cạnh có hướng
ngược chiều nhau.
Định ngh a 1.4

deg(d) = 1, deg(e) = 3, deg(g) = 0
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Trong
ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính
chất sau:
Định lý 1. Giả sử G = (V, E) là đồ thị vô hướng với m cạnh.
Khi đó tông bậc của tất cả các đỉnh bằng hai lần số cung.
Chứng minh. Rõ ràng mỗi cạnh e = (u, v) được tính một lần
trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của
các đỉnh bằng hai lần số cạnh.
Ví dụ 2 . Đồ thị với n đỉnh có bậc là 6 có bao nhiêu cạnh
Giải: Theo định lý 1 ta có 2m = 6n. Từ đó suy ra tổng các cạnh của đồ
thị là 3n.


11

Hệ quả. Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ)
là một số chẵn.
Chứng minh. Thực vậy, gọi O và U tương ứng là tập đỉnh bậc lẻ và
tập đỉnh bậc chẵn của đồ thị. Ta có
2m=∑deg(v)+∑deg(v) ,V ϵ U , vϵ O
Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ nhất

trên là số

chẵn. Từ đó suy ra tổng thứ hai (chính là tổng bậc của các đỉnh bậc lẻ) cũng
phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm
một số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn.
Ta xét các thuật ngữ tương tự cho đồ thị vô hướng.
Định ngh a 1.8.

Đường đi là độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên
dương, trên đồ thị vô hướng G = (V, E) là dãy x0, x1,…, xn-1, xn
trong đó u = x0 , v = xn , (xi , xi+1) ϵ E, i = 0, 1, 2,…, n-1.
Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh:
(x0, x1), (x1, x2), …, (xn-1, xn)
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối
của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được
gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có
cạnh nào bị lặp lại.
Ví dụ 4. Trên đồ thị vô hướng cho trong hình 1.7: a, d, c, f, e
là đường đi đơn độ dài 4.

òn d, e, c, a không là đường đi, do (c,e) không

phải là cạnh của đồ thị. ãy b, c, f, e, b là chu trình độ dài 4. Đường đi a, b, e,


13

d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong
nó 2 lần.

Hình 1.7: Đường đi trên đồ thị
Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa
hoàn toàn tương tự như trong trường hợp đồ thị vô hướng, chỉ khác là ta có
chú ý đến hướng trên các cung.
- Định ngh a chu trình :
Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó, n là số nguyên
dương, trên đồ thị có hướng G = (V, ) là dãy
x0, x1,…, xn-1, xn

d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong
nó 2 lần.


14

Xét một mạng máy tính. Một câu hỏi đặt ra là hai máy tính bất kỳ trong
mạng này có thể trao đổi thông tin được với nhau hoặc là trực tiếp qua kênh
nối chúng hoặc thông qua một hoặc vài máy tính trung gian trong mạng. Nếu
sử dụng đồ thị để biểu diễn mạng máy tính này (trong đó các đỉnh của đồ thị
tương ứng với các máy tính, còn các cạnh tương ứng với các kênh nối) câu
hỏi đó được phát biểu trong ngôn ngữ đồ thị như sau: Tồn tại hay
không đường đi giữa mọi cặp đỉnh của đồ thị.
1.2.3. Cây
Định ngh a 1.9
Cây là đồ thị vô hướng liên thông không có chu trình. Nhóm nhiều hơn
một cây được gọi là rừng.
Ví dụ 6. Trong hình 1 là một rừng gồm 3 cây T1, T2, T3.

Hình 1.8: Rừng có 3 cây
Định lý 3. Giả sử G = (V,E) là đồ thị vô hướng với |V| = n. Khi đó các
mệnh đề sau đây là tương đương:
(1) T là cây;
(2) T không chứa chu trình và có n-1 cạnh;
(3) T liên thông và có n-1 cạnh;
(4) T liên thông và mỗi cạnh của nó điều là cầu;
(5) Hai đỉnh bất kỳ của T được nối với nhau b i đúng
một đường đi đơn;
(6) T không chứa chu trình nhưng hễ cứ thêm vào một cạnh ta
thu được đúng một chu trình.

nhau b i một đường đi đơn. Nếu có cặp đỉnh nào của T có hai đường đi đơn


16

khác nhau nối chúng, thì từ đó suy ra đồ thị chứa chu trình, và vì thế các cạnh
trên chu trình này không phải là cầu.
(5)  (6) T không chứa chu trình, b i vì thế nếu có chu trình thì hoá ra
tìm được cặp đỉnh của T được nối với nhau b i hai đường đi đơn. Bây giờ,
nếu thêm vào T một cạnh e nối hai đỉnh u và v nào đó của T. Khi đó cạnh này
cùng với đường đi đơn nối u với v sẽ tạo thành chu trình trong T.

hu trình

thu được này là duy nhất, vì nếu thu được nhiều hơn một chu trình thì suy ra
trong T trước đó phải có sẵn chu trình.
(6) (1) Giả sử T không liên thông. Khi đó gồm ít ra là 2 thành phần
liên thông. Vì vậy, nếu thêm vào T một cạnh nối hai đỉnh thuộc hai thành
phần liên thông khác nhau ta không thu được thêm một chu trình nào
cả. Điều đó mâu thuẫn với giả thiết (6). Định lý được chứng minh.
ết luận chƣơng
Mạng Vận Tải hết sức quan trọng đối với nền kinh tế là cốt lõi cho sự
phát triển giao thương kinh tế - xã hội . Hiện nay Việt Nam đang xây dựng
những cơ s hạ tầng vận tải hiện đại, để thúc đẩy giao thông phát triển đi đôi
với việc hiệu quả đáp ứng tối đa mà mạng vận tải đem lại.
Vấn đề đăt ra

đây là bài toán mạng vận tải khi được sử dụng tối ưu

hóa về mặt khoảng cách, tìm ra những đoạn đường ngắn nhất rút ngắn được

dưới đây mô tả thuật toán tìm đường đi từ đỉnh s đến đỉnh t trên đồ thị bằng
thuât toán DFS. Hình dưới đây mô tả thuật toán tìm đường đi từ đỉnh s đến
đỉnh t trên đồ thị bằng thuât toán BFS.