Đề cương Toán rời rạc

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN 
KHOA CÔNG NGHỆ THÔNG TIN 
ĐỀ CƯƠNG 
TOÁN RỜI RẠC 
Trình độ đào tạo 
 Hệ đào tạo 
: 
: 
Đại học 
Chính quy/Liên thông 
Trang 2 
Mở đầu 
Lý thuyết đồ thị là một lĩnh vực đã có từ lâu và có nhiều ứng dụng hiện đại. 
Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế 
kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sỹ Lenhard Eurler. Chính ông là người đã 
sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thành phố Konigsberg. 
Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng 
hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. 
Chúng ta có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức 
phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xác định hai 
máy tính trong mạng có thể trao đổi thông tin được với nhau hay không nhờ mô hình 
đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các 
bài toán như: Tìm đường đi ngắn nhất giữa hai thành phố trong mạng giao thông. 
Chúng ta cũng còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khóa biểu, và 
phân bố tần số cho các trạm phát thanh và truyền hình. 
Bộ môn Công nghệ Phần mềm 
Khoa Công nghệ Thông tin 
Trường Đại học Sư phạm Kỹ thuật Hưng Yên 
Trang 3 
Mục lục 
Bài 1 Các khái niệm cơ bản của Lý thuyết đồ thị ................................................................. 7 
1.1. Định nghĩa cơ bản về đồ thị ............................................................................................. 7 
1.2. Đường đi - chu trình - Đồ thị liên thông .......................................................................... 9 
1.3. Phân loại đồ thị .............................................................................................................. 13 
1.3.1. Đồ thị vô hướng liên thông ..................................................................................... 13 
1.3.2. Đồ thị có hướng liên thông ..................................................................................... 14 
1.4. Một số loại đồ thị đặc biệt ............................................................................................. 15 
Bài 2 Biểu diễn đồ thị trên máy tính ................................................................................... 20 
2.1. Một số phương pháp biểu diễn đồ thị trên máy tính...................................................... 20 
2.2.1. Ma trận kề - Ma trận trọng số ................................................................................. 20 
2.2.2. Danh sách cạnh (cung) ........................................................................................... 22 
2.2.3. Danh sách kề ........................................................................................................... 22 
Bài 3 Đồ thị Euler ................................................................................................................ 24 
3.1. Định nghĩa ..................................................................................................................... 24 
3.2. Các ví dụ ........................................................................................................................ 24 
3.3. Định lý Euler và thuật toán Flor .................................................................................... 25 
Bài 4 Đồ thị Hamilton ......................................................................................................... 28 
4.1 Định nghĩa ...................................................................................................................... 29 
4.2. Định lý và thuật toán liệt kê tất cả các chu trình Hamilton ........................................... 29 
Bài 5 Thảo luận cài đặt đồ thị, các thuật toán liệt kê chu trình Euler và Hamilton. ............ 33 
5.1. Cài đặt biểu diễn đồ thị trên máy tính ........................................................................... 33 
5.2. Cài đặt thuật toán liệt kê chu trình Euler ....................................................................... 33 
5.3. Cài đặt thuật toán liệt kê chu trình Hamilton................................................................. 35 
5.4. Thảo luận các bài tập trong giáo trình bài tập ............................................................... 35 
Bài 6 Thuật toán tìm kiếm trên đồ thị và ứng dụng ............................................................. 36 
6.1. Duyệt đồ thị theo chiều rộng (BFS)............................................................................... 36 
6.2. Duyệt đồ thị theo chiều sâu (DFS) ................................................................................ 39 
6.3. Thảo luận ....................................................................................................................... 42 
Bài 7 Cây và cây khung ....................................................................................................... 45 
7.1. Cây và cây khung .......................................................................................................... 45 
7.1.1. Cây .......................................................................................................................... 45 
7.1.2. Cây khung của đồ thị .............................................................................................. 46 
7.2. Bài toán cây khung nhỏ nhất ......................................................................................... 48 
7.3 Xây dựng tập các chu trình cơ bản của đồ thị ................................................................ 49 
7.4. Thuật toán Prim ............................................................................................................. 51 
7.5 Thuật toán Kruskal ......................................................................................................... 54 
Bài 8 Thảo luận về cài đặt thuật toán tìm cây khung nhỏ nhất trên đồ thị .......................... 57 
8.1. Cài đặt xây dựng tập các chu trình cơ bản của đồ thị .................................................... 57 
8.2. Cài đặt thuật toán Prim .................................................................................................. 59 
8.3. Cài đặt thuật toán Kruskal ............................................................................................. 60 
8.4. Một số thuật toán xây dựng cây khung(*) ..................................................................... 61 
Bài 9 Bài toán tìm đường đi ngắn nhất ................................................................................ 63 
9.1. Các khái niệm mở đầu ................................................................................................... 63 
9.2. Đường đi ngắn nhất xuất phát từ một đỉnh. Thuật toán ford-Bellman .......................... 64 
9.3. Trường hợp ma trận trọng số không âm. Thuật toán Dijkstra ....................................... 66 
Bài 10 Bài toán tìm đường đi ngắn nhất (tiếp) ...................................................................... 69 
10.1 Đường đi trong đồ thị không có chu trình .................................................................... 69 
Trang 4 
10.2 Đường đi ngắn nhất giữa tất cả các cặp đỉnh ............................................................... 73 
10.3 Cài đặt thuật toán Dijkstra ........................................................................................... 75 
Bài 11 Bài toán luồng cực đại trong mạng ........................................................................... 76 
11.1. Mạng - Luồng trong mạng .......................................................................................... 76 
11.2. Bài toán luồng cực đại ................................................................................................ 77 
11.3. Lát cắt. đường tăng luồng. Định lý ford_fulkerson .................................................... 77 
11.4. Thuật toán tìm luồng cực đại ...................................................................................... 80 
Bài 12 Lý thuyết đồ thị và ứng dụng ................................................................................. 90 
12.1. Các bài toán liên quan tới đồ thị ................................................................................. 90 
12.1.1 Các bài toán liên quan tới bậc của đồ thị .............................................................. 90 
12.1.2 Các bài toán liên quan đến tính liên thông của đồ thị ........................................... 92 
12.1.3 Các bài toán liên quan tới chu trình ...................................................................... 93 
12.1.4 Các bài toán có liên quan đến đường đi và chu trình Hamilton ........................... 94 
12.1.5 Các bài toán liên quan đến đồ thị tô màu .............................................................. 99 
12.1.6 Bài toán về cây .................................................................................................... 108 
12.1.7 Bài toán về ghép cặp ........................................................................................... 109 
12.1.8 Đồ thị Euler ......................................................................................................... 109 
12.1.9 Các bài toán có tính tổng hợp ............................................................................. 110 
12.2 Sự liên hệ giữa các tập đặc biệt trên đồ thị với các bài toán trên bàn cờ ................... 112 
12.3 Duyệt rộng trên mảng hai chiều ................................................................................. 116 
Bài 13 Một số ứng dụng trong đồ thị .............................................................................. 118 
13.1 Bài toán đám cưới vùng quê ..................................................................................... 118 
13.2 Bài toán về hệ thống đại diện chung .......................................................................... 119 
13.3 Bài toán tối ưu rời rạc ................................................................................................ 119 
Bài toán phân nhóm sinh hoạt ........................................................................................ 120 
Bài toán lập lịch cho hội nghị ........................................................................................ 120 
13.4 Một số bài toán liên quan đến việc tổ chức mạng vận chuyển bưu chính. ................ 121 
Mô hình định tuyến mạng đường thư cấp 1 ................................................................... 121 
Bài toán lập kế hoạch vận chuyển bưu gửi .................................................................... 122 
Mô hình mạng đường thư trong thành phố .................................................................... 124 
TÀI LIỆU THAM KHẢO ...................................................................................................... 127 
Trang 5 
Danh mục các hình vẽ 
Hình 1.1 Sơ đồ mạng máy tính. .................................................................................................. 7 
Hình 1.2 Sơ đồ mạng máy tính với đa kênh thoại. ..................................................................... 8 
Hình 1.3 Sơ đồ mạng máy tính với kênh thoại thông báo. ......................................................... 8 
Hình 1.4 Mạng máy tính với kênh thoại một chiều. ................................................................... 9 
Hình 1.5 Đường đi trên đồ thị .................................................................................................. 10 
Hình 1.6 Đồ thị G và H. .......................................................................................................... 11 
Hình 1.7 Đồ thị liên thông mạnh G và đồ thị liên thông yếu H. .............................................. 12 
Hình 1.8 Đồ thị vô hướng ......................................................................................................... 13 
Hình 1.9 Đồ thị có hướng ......................................................................................................... 15 
Hình 1.10 Đồ thị đầy đủ ........................................................................................................... 16 
Hình 1.11 Đồ thị vòng C3, C4, C5, C6 ....................................................................................... 16 
Hình 1.12 Đồ thị bánh xe W3, W4, W5, W6 .............................................................................. 16 
Hình 1.13 Đồ thị lập phương Q1, Q2, Q3 .................................................................................. 17 
Hình 1.14 Đồ thị hai phía ......................................................................................................... 17 
Hình 1.15 Đồ thị K4 là đồ thị phẳng ......................................................................................... 18 
Hình 1.16 Các miền tương ứng với biểu diễn phẳng của đồ thị ............................................... 19 
Hình 2.1 Đồ thị vô hướng G và Đồ thị có hướng G1 ................................................................ 21 
Hình 3.1 Mô hình 7 cây cầu ở Konigsberg ............................................................................... 24 
Hình 3.2 Đồ thị G1, G2, G3 ....................................................................................................... 25 
Hình 3.3 Đồ thị H1, H2, H3 ....................................................................................................... 25 
Hình 3.4 Minh hoạ cho chứng minh Định lý 3.1 ...................................................................... 26 
Hình 4.1 Du lịch 20 thành phố ................................................................................................. 28 
Hình 4.2 Đồ thị Hamilton G3, nửa Hamilton G2, và G1 ........................................................... 29 
Hình 4.3 Đồ thị đấu loại D5, đấu loại liên thông mạnh D6 ....................................................... 30 
Hình 4.4 Đồ thị và cây liệt kê chu trình Hamilton của nó theo thuật toán quay lui ................. 32 
Hình 5.1 Đồ thị và cây liệt kê chu trình Hamilton của nó theo thuật toán quay lui ................. 35 
Hình 6.1 Đồ thị vô hướng ......................................................................................................... 37 
Hình 6.2 Đồ thị vô hướng ......................................................................................................... 43 
Hình 7.1 Cây và rừng ............................................................................................................... 45 
Hình 7.2 Đồ thị và các cây khung của nó. ................................................................................ 47 
Hình 7.3 Đồ thị và cây khung nhỏ nhất. ................................................................................... 53 
Hình 8.1 Hệ chu trình độc lập cho đồ thị vô hướng G ................................................. ...  vậy. 
13.1 Bài toán đám cưới vùng quê 
Có m chàng trai ở một vùng quê nọ. Đối với mỗi chàng trai ta biết các cô gái 
mà anh ta vừa ý. Hỏi khi nào thì có thể tổ chức các đám cưới trong đó chàng trai nào 
cũng sánh duyên với các cô gái mà mình vừa ý. 
Ta có thể xây dựng đồ thị với các đỉnh biểu thị các chàng trai và các cô gái, còn 
các cung biểu thị sự vừa ý của các chàng trai với các cô gái. Khi đó ta thu được một đồ 
thị hai phía. 
Ví dụ 14.1 Có 4 chàng trai { T1, T2, T3,T4} và 5 cô gái { G1, G2, G3,G4, G5} . Sự vừa ý 
cho trong bảng sau 
Chàng trai Các cô gái mà chàng trai ưng ý 
T1 G1, G4, G5 
T2 G2 
T3 G2, G3,G4 
T4 G2, G4 
Đồ thị tương ứng được cho trong hình 14.1. 
Hình 13.1 Mạng tương ứng với bài toán đám cưới vùng quê. 
Trang 119 
Đưa vào điểm phát s và điểm thu t. Nối s với tất cả các đỉnh biểu thị các chàng 
trai, và nối t với tất cả các đỉnh biểu thị các cô gái. Tất cả các cung của đồ thị đều có 
khả năng thông qua bằng 1. Bắt đầu từ luồng 0, ta tìm luồng cực đại trong mạng xây 
dựng được theo thuật toán ford-Fulkerson. Từ định lý về tính nguyên, luồng trên các 
cung là các số hoặc 1. Rõ ràng là nếu luồng cực đại trong đồ thị có giá trị Vmax = m, thì 
bài toán có lời giải, và các cung với luồng bằng 1 sẽ chỉ ra cách tổ chức đám cưới thoả 
mãn điều kiện đặt ra. Ngược lại, nếu bài toán có lời giải thì Vmax = m. Bài toán về đám 
cưới vùng quê là một trường hợp riêng của bài toán về cặp ghép trên đồ thị hai phía 
mà để giải nó có thể xây dựng thuật toán hiệu quả hơn. 
13.2 Bài toán về hệ thống đại diện chung 
Cho tập m phần tử X={ z1, z2, . . . ,zm} . Giả sử và <B1, B2, . . 
., Bn> là hai dãy các tập con của X. Dãy gồm n phần tử khác nhau của X: <a1, a2, . . . 
,an> được gọi là hệ thống các đại diện chung của hai dãy đã cho nếu như tìm được một 
hoán vị s của tập {1, 2,. . .,n} sao cho là hệ thống các đại diện phân 
biệt của hai dãy và , tức là điều kiện sau được 
thoả mãn: ai Ai  Bs (i), i = 1, 2, . . ,n. Xây dựng mạng G = (V, E) với tập đỉnh 
V = { s, t}  { x1, x2, . . . ,xn}  {u1, u2, . . . ,un}  { v1, v2, . . . ,vn}  { y1, y2, . . . ,yn} 
. 
trong đó đỉnh xi tương ứng với tập Ai, đỉnh yi tương ứng với tập Bi, các phần tử uj, yj 
tương ứng với phần tử zj. Tập các cung của mạng G được xác định như sau 
 E = { (s, xi): 1≤i≤n}  { (xi,uj): với zj Ai, 1≤i≤n, 1≤j≤m}  
 { (uj,vj):1≤j≤m}  {(vj, yi): với zj Bi, 1≤i≤n, 1≤j≤m}  { (yi, t): 1≤i≤n} 
Khả năng thông qua của tất cả các cung được đặt bằng 1. Dễ dàng thấy rằng hệ 
thống đại diện chung của hai dãy và tồn tại khi và chỉ khi trong mạng G=(V,E) tìm 
được luồng với giá trị n. Để xét sự tồn tại của luồng như vậy có thể sử dụng thuật toán 
tìm luồng cực đại từ s đến t trong mạng G=(V, E). 
13.3 Bài toán tối ưu rời rạc 
Trong mục này ta sẽ trình bày thuật toán được xây dựng dựa trên thuật toán tìm 
luồng cực đại để giải một bài toán tối ưu rời rạc là mô hình toán học cho một số bài 
toán tối ưu tổ hợp. 
Xét bài toán tối ưu rời rạc: 
Trang 120 
với điều kiện 
(2) 
(3) 
trong đó aij { 0,1}, i = 1, 2, . . ., m; j=1, 2, . . . n, pi –nguyên dương, i = 1, 2, . . .,m. 
Bài toán (1)-(3) là mô hình toán học cho nhiều bài toán tối ưu tổ hợp thực tế. 
Dưới đây ta dẫn ra một vài ví dụ điển hình. 
Bài toán phân nhóm sinh hoạt. Có m sinh viên và n nhóm sinh hoạt chuyên 
đề. Với mỗi sinh viên i, biết 
+ aij =1, nếu sinh viên i có nguyện vọng tham gia vào nhóm j, 
+ aij =0, nếu ngược lại, 
+ và pij là số lượng nhóm chuyên đề mà sinh viên i phải tham dự, 
i = 1, 2, . . . ,m; j=1, 2,. . . ,n. 
Trong số các cách phân các sinh viên vào nhóm chuyên đề mà họ có nguyện 
vọng tham gia và đảm bảo mỗi sinh viên i phải tham gia đúng pi nhóm, hãy tìm cách 
phân phối với số người trong nhóm có nhiều sinh viên tham gia nhất là nhỏ nhất có thể 
được. 
Đưa vào biến số 
xij = 1, nếu sinh viên i tham gia vào nhóm j, 
xij = 0, nếu ngược lại, 
i = 1, 2, . . .,m, j=1, 2,. . .,n, khi đó dễ thấy mô hình toán học cho bài toán đặt ra chính 
là bài toán (1)-(3). 
Bài toán lập lịch cho hội nghị. Một hội nghị có m tiểu ban, mỗi tiểu ban cần 
sinh hoạt trong một ngày tại phòng họp phù hợp với nó. Có n phòng họp dành cho việc 
sinh hoạt của các tiểu ban. Biết 
aij = 1, nếu phòng họp i là thích hợp với tiểu ban j, 
aij=0, nếu ngược lại, 
f(x1,x2,...,xn) = (1) 
Trang 121 
i = 1, 2, . . .,m, j =1, 2,. . .,n. Hãy bố trí các phòng họp cho các tiểu ban sao cho hội 
nghị kết thúc sau ít ngày làm việc nhất. 
Đưa vào biến số 
xij = 1, nếu bố trí tiểu ban i làm việc ở phòng j, 
xij =0, nếu ngược lại, 
i =1, 2, . . .,m, j =1, 2,. . .,n, khi đó dễ thấy mô hình toán học cho bài toán đặt ra chính 
là bài toán (1)-(3), trong đó pi=1, i =1, 2, . . .,m. 
13.4 Một số bài toán liên quan đến việc tổ chức mạng vận chuyển bưu 
chính. 
Các bài toán tối ưu trên mạng, một phần của lý thuyết đồ thị hữu hạn là một lý 
thuyết toán học được ứng dụng rộng rãi trong kinh tế, quân sự. 
Người đặt nền móng đầu tiên cho lý thuyết đồ thị là nhà toán học Euler, với 
“bài toán bảy cái cầu” nổi tiếng vào năm 1736. 
Trong quá trình khai thác các khía cạnh khác nhau của bài toán, các nhà toán 
học đã dần dần đặt cơ sở lý luận cho một lý thuyết toán học mới ra đời, đó là lý thuyết 
đồ thị hữu hạn (lý thuyết Graph). 
Đến nay lý thuyết đồ thị hữu hạn đã được nghiên cứu ứng dụng trong hầu hết 
các lĩnh vực của hoạt động kinh tế xã hội, là công cụ toán học sắc bén trong nghiên 
cứu các hệ thống kỹ thuật -công nghệ, hệ thống kinh tế -xã hội, hệ thống quân sự, hệ 
thống bưu chính viễn thông v.v... 
Trong những năm gần đây nhờ sự hỗ trợ của công nghệ thông tin và máy tính 
điện tử, lý thuyết graph càng trở thành công cụ hiệu quả, năng động giải quyết nhiều 
bài toán liên quan đến nghiên cứu phân tích hệ thống. 
Mô hình định tuyến mạng đường thư cấp 1 
Mạng đường thư cấp một thực chất là một đồ thị có các đỉnh là các nút trung 
tâm Bưu chính và các Bưu điện trung tâm. Vận chuyển giữa các nút mạng có thể qua 
đường trực tiếp hoặc qua các nút trung gian. Do vậy xuất hiện bài toán lựa chọn tuyến 
đường vận chuyển. Tức là phải chỉ ra cách vận chuyển từ một nút bất kỳ tới một nút 
bất kỳ khác cần phải qua nút trung gian nào. Giữa 2 đỉnh sẽ có cung liên kết nếu chúng 
có đường vận chuyển trực tiếp với nhau. 
Để giải bài toán xác định đường vận chuyển bưu chính cần có các khái niệm sau: 
Trang 122 
1. Lưu lượng (luồng) vận chuyển bưu gửi: Số lượng bưu gửi xuất hiện tại một nút 
mạng bất kỳ cần phải chuyển tới một nút mạng khác. Đại lượng này tính trong một 
đơn vị thời gian (giờ, ngày, tuần, tháng), được gọi là tải trọng. Do đặc điểm không 
đồng đều của tải trọng theo ngày trong tuần và tháng trong năm nên ta chỉ xét tải trọng 
trung bình ngày để lập kế hoạch vận chuyển (thống kê một tháng tiêu biểu và chia 
trung bình cho một ngày). Trong mô hình, tải trọng giữa các nút mạng được biểu diễn 
dưới dạng ma trận mà phần tử (ij) được hiểu là tải trọng trong một ngày từ nút mạng i 
tới nút mạng j. 
2. Khả năng lưu thoát của nút mạng là số lượng bưu gửi có thể được khai thác tại một 
nút mạng trong một ngày. Khả năng lưu thoát phụ thuộc vào nhiều yếu tố như diện 
tích mặt bằng, mức độ cơ giới hoá, tự động hoá, tổ chức sản xuất, mức độ không đồng 
đều của tải trọng, tần số và thời gian khởi hành của các phương tiện vận chuyển... 
3. Giá trị của các cung (chiều dài các cung) là giá thành vận chuyển một đơn vị sản 
phẩm theo từng cung liên kết, hoặc thời gian vận chuyển giữa các nút mạng. Đơn vị 
sản phẩm có thể là một túi thư, một container hoặc một bưu kiện tuỳ vào bài toán cụ 
thể. Giá thành vận chuyển một đơn vị sản phẩm được biểu diễn qua chiều dài cung 
hoặc thời gian vận chuyển giữa các nút mạng. 
Bài toán lập kế hoạch vận chuyển bưu gửi 
Trước tiên, xét hai nút mạng cần trao đổi bưu gửi, một nút mạng là nguồn ws, 
một nút là đích wt, luồng tải trọng từ nguồn tới đích sẽ là: (x1 ,...,xj ,...,xn) 
các cung dj với xj > 0 tạo thành tuyến vận chuyển tải trọng xj từ nguồn ws tới đích wt, 
tuyến vận chuyển này được xác định là một tập hợp các nút mạng (hay tập hợp các 
cung) tham gia vào tuyến vận chuyển này. 
Như vậy, bài toán định tuyến mạng vận chuyển bưu gửi là cần xác định luồng 
bưu gửi từ một nút mạng tới một nút mạng khác cần phải qua các nút trung gian nào 
để tối thiểu hoá chi phí vận chuyển của toàn bộ mạng, đồng thời việc lựa chọn tuyến 
đường cần thoả mãn các điều kiện ràng buộc về thời gian toàn trình và khả năng lưu 
thoát của từng nút mạng. 
Trong mạng vận chuyển bưu chính, trên mạng đồng thời thực hiện nhiều luồng 
trao đổi, mỗi một luồng có nút khởi đầu và nút kết thúc. Do vậy, cần đưa vào ký hiệu 
từng luồng là véc tơ xq: 
xq =(xq1,..., xqj,...,xqn) 
Xq cần thoả mãn điều kiện không âm và điều kiện bảo toàn luồng nghĩa là: 
Trang 123 
AXq =Vq Xq ≥ 0 
Trong đó: 
Vq: véctơ tất cả các phần tử đều bằng 0, ngoại trừ hai phần tử tương ứng với nút mạng 
khởi đầu và nút kết thúc có giá trị là -vq và Vq (vR là lưu lượng cần vận chuyển của mỗi 
luồng); 
A: Ma trận liên kết cung nút chứa m dòng và n cột trong đó m là số nút mạng và n là 
số cung. Ma trận A chính là mô hình định tuyến mạng vận chuyển của từng luồng cần 
xác định. 
Ma trận liên kết cung nút của graph G = (W,D), ký hiệu A=[aij] có kích thước m 
x n với các phần tử được xác định như sau: 
aij = 
 1, nếu wi là đỉnh đầu của cung dj 
−1, nếu wi là đỉnh cuối của cung dj 
 0, nếu wi không là đỉnh đầu hoặc cuối của cung dj 
Ngoài ra luồng Xq còn phải thoả mãn điều kiện ràng buộc không được vượt quá 
khả năng khai thác của từng nút mạng wi. 
Xét véc tơ Pi (Pi1, Pi2, ... Pin) trong đó Pi = l nếu dj hướng tới đỉnh wi và Pi = 0 nếu 
ngược lại. Véc tơ Pi chính là dòng i của ma trận liên kết cung nút A mà trong đó tất cả 
các phần tử -l được thay bằng 0. 
Như vậy, điều kiện ràng buộc về khả năng lưu thoát của các nút mạng là: 
Trong đó: 
hi: Khả năng Lưu thoát của nút mạng W 
r: Số đôi nút mạng trong mạng có trao đổi bưu gửi 
Tiêu chí tối ưu của bài toán vận chuyển bưu gửi như sau: 
Giả sử C (C1,C2,... Cn) là Véctơ chi phí vận chuyển trong đó Cj là cước vận 
chuyển l đơn vị sản phẩm qua cung dj (chiều dài cung dj). Khi đó chi phí vận chuyển 
sẽ là: 
Z = CX1 + ... + CXq + ... + CXr 
 = C(X1 + ... + Xq + ... + Xr ) → min 
Vậy mô hình vận chuyển tối ưu là: 
Trang 124 
min[Z = C(X1 + ... + Xq + ... + Xr)] 
P1(X1 + ... + Xq + ... + Xr) ≤ h1 
.................................................. 
Pm(X1 + ... + Xq + ... + Xr) ≤ hm 
AX1 = V1 
AXq = Vq 
AXr = Vr 
Trong trường hợp không có điều kiện hạn chế về khả năng lưu thoát của các nút 
mạng, bài toán định tuyến mạng bưu chính chỉ đơn giản là bài toán tìm đường đi ngắn 
nhất giữa từng đôi nút mạng. Bài toán tìm đường ngắn nhất được giải bằng thuật toán 
dán nhãn của Dijkstra. 
Mô hình mạng đường thư trong thành phố 
Mạng đường thư trong thành phố là một đồ thị đỉnh của nó là các bưu cục. Hai 
đỉnh của đồ thị sẽ được nối kết với nhau bằng cung liên kết nếu giữa chúng có tuyến 
đường đi. Trong thành phố giữa các bưu cục bao giờ cũng có các đường thư, nên đồ 
thị được kết nối theo kiểu điểm nối điểm. Đồ thị mạng đường thư trong thành phố là 
một đồ thị có hướng vì khoảng cách i tới j và j tới i có thể không trùng nhau (đường 
một chiều). Giá trị của cung được biểu diễn bằng khoảng cách hoặc thời gian vận 
chuyển giữa các nút mạng hoặc chi phí vận chuyển giữa các nút mạng. 
Ta có chi phí vận chuyển giữa các nút mạng là: 
cịj = krij 
rij: Khoảng cách giữa các nút i và nút j (cần được xác định theo khoảng cách thực tế và 
phải lựa chọn rij là đường ngắn nhất, tức là phải thoả mãn điều kiện rij ≤ rik + rkj do một 
cạnh tam giác nhỏ hơn tổng 2 cạnh còn lại). 
k: Chi phí vận chuyển l km bằng ô tô. 
Thời gian vận chuyển trên cung ij 
Vij: Vận tốc vận chuyển ô tô từ nút i tới nút j. 
t0j: Thời gian trao đổi tại nút mạng j. 
Trang 125 
Khi tổ chức mạng đường thư có thể sử dụng phương thức đường thẳng, đường 
vòng hoặc hỗn hợp. 
Mạng đường vòng có ưu điểm là sử dụng các phương tiện vận chuyển hiệu quả 
hơn. Do vậy trong thành phố thường sử dụng đường vòng do tính kinh tế của nó. 
Bài toán 
Bài toán tổ chức mạng đường thư trong thành phố là xác định hành trình của 
từng chiếc ô tô phải qua các nút mạng nào, theo trình tự nào để đảm bảo chi phí vận 
chuyển toàn mạng là nhỏ nhất (hoặc tổng quãng đường hay tổng thời gian vận chuyển 
nhỏ nhất) đồng thời thoả mãn các ràng buộc về thời gian vận chuyển của từng ô tô và 
dung lượng vận chuyển của từng ô tô. 
Trong hệ thống khai thác tập trung tồn tại một Bưu điện trung tâm duy nhất. 
Nếu chia các nút mạng ra làm hai loại nguồn và đích, nút mạng trung tâm sẽ là nguồn, 
các nút mạng còn lại sẽ là đích hoặc ngược lại. 
Trong mô hình vận chuyển bưu gửi trong thành phố, các đỉnh đồ thị được đặc 
trưng bởi số lượng bưu gửi mà nó cần nhận được từ qi hoặc ngược lại cần gửi đi ri. 
Trong đó: 
0: nút nguồn. 
i = l ÷ N: đích 
Trong hệ thống khai thác phân tán khi đó đồ thị sẽ được chia thành các đồ thị 
con, mỗi một đồ thị chỉ có một nút mạng nguồn duy nhất và việc giải bài toán thực tế 
là giải từng bài toán con. 
Nếu mạng vận chuyển trong thành phố chủ yếu bằng ô tô, ta giả sử: 
M: số ô tô toàn mạng 
Qj - dung lượng của j ô tô, phụ thuộc vào loại ô tô 
T - thời gian vận chuyển tối đa cho phép trên một đường thư. 
T được xác định dựa trên các định mức (T = 2 giờ). 
Qj = min (Pj / b, Vj / d) 
Trong đó Pj: tải trọng của ô tô; 
Vj: thể tích vận chuyển của ô tô; 
Trang 126 
b: Khối lượng trung bình của túi thư; 
d: thể tích trung bình của túi thư. 
Mô hình toán học 
Giả sử gọi xijk là ẩn cần tìm, xijk = 1 nếu trong tuyên vòng k, đỉnh j sẽ được tới 
ngay sau đỉnh i, Xijk = 0 trong trường hợp ngược lại, khi đó mô hình toán học của bài 
toán mạng đường thư trong thành phố là: 
Biến Xijk cần thoả mãn các ràng buộc sau: 
j = 0 ÷ N (1) 
k = 1 ÷ M, p = 0 ÷ N (2) 
k = 1 ÷ M (3) 
k = 1 ÷ M (4) 
Trong đó t0i: thời gian trao đổi tại nút mạng i. 
(l): Do mỗi đỉnh đồ thị chỉ thuộc một tuyến đường vòng; 
(2): Đối với mỗi một đỉnh, số lượng các cung đi vào và đi ra phải bằng nhau tại một 
đỉnh; 
(3): Ràng buộc về dung lượng của ô tô; 
(4): Ràng buộc về thời hạn vận chuyển của từng ô tô. 
Đây là bài toán tổng quát về mạng vận chuyển thư trong thành phố. Bài toán 
tìm hành trình của bưu tá qua n điểm là trường hợp riêng khi chỉ có 1 tuyến đường 
vòng qua n điểm (M=1), còn bài toán này cần xác định M tuyến đường cho M ô tô và 
cần thoả mãn các hạn chế (ràng buộc) về chỉ tiêu thời gian và dung lượng vận chuyển 
của ô tô. 
Trang 127 
TÀI LIỆU THAM KHẢO 
 [1] Lý thuyết tổ hợp và đồ thị, Ngô Đắc Tân, Viện Toán Học, NXB Đại 
học Quốc Gia Hà Nội, 2003. 
[2] Toán rời rạc, Nguyễn Đức Nghĩa, Nguyễn Tô Thành, NXB Giáo 
dục, Hà nội 1997. 
[3] Lý thuyết đồ thị, Đặng Huy Ruận, NXB ĐHQG, 1997. 
[4] Discrete Mathematics && Its Applications, 6th Edition, Kenneth H. 
Rosen, McGraw Hill, 2007. 
[5] Handbook of Discrete && Combinatorial Mathematics, Kenneth 
H.Rosen (chief of editor), CRC Press, 2000.