6.4. MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ
6.4.2. Bài toán tìm cây khung nhỏ nhất
Trong đồ thị liên thông G, nếu loại bỏ cạnh nằm trên chu trình nào đó thì cũng sẽ được đồ thị liên thông. Nếu cứ loại bỏ các cạnh ở các chu trình khác cho đến khi nào đồ thị
116 không còn chu trình (vẫn liên thông) thì thu được một cây nối các đỉnh của G. Cây đó gọi là cây khung hay cây bao trùm của đồ thị G.
Định nghĩa 6.8: Giả sử G = (V, E) là đồ thị vô hướng liên thông, cây T = (V, F) với F E được gọi là cây khung của đồ thị G.
Ví dụ 6.12: Hình 6.13 thể hiện đồ thị và các cây khung của nó
Hình 6.13: Cây khung của đồ thị.
Bài toán cây khung nhỏ nhất: Tìm cây khung nhỏ nhất của đồ thị là một trong số các bài toán tối ưu trên đồ thị được ứng dụng trong nhiều lĩnh vực khác nhau. Nội dung của bài toán được phát biểu như sau:
Cho G = (V, E) là đồ thị vô hướng liên thông có trọng số, mỗi cạnh e E có trọng số m(e)
0. Giả sử T = (VT, ET) là cây khung của đồ thị G (VT = V), gọi độ dài m(T) của cây khung là tổng trọng số các cạnh của T:
m(T) =
ET
) (
e
e m .
Bài toán: trong số các cây khung của G, tìm cây khung có độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị.
Bài toán cây khung nhỏ nhất có nhiều ứng dụng thực tế, dưới đây sẽ trình bày 2 mô hình tiêu biểu cho nó.
Bài toán xây dựng hệ thống đường sắt: Giả sử muốn xây dựng hệ thống đường sắt nối n thành phố sao cho hành khách có thể đi từ bất cứ một thành phố nào đến bất kỳ một trong số các thành phố còn lại. Mặt khác, trên quan điểm kinh tế đòi hỏi chi phí về xây dựng hệ thống đường phải nhỏ nhất. Rõ ràng đồ thị có đỉnh là các thành phố, còn các cạnh là các tuyến đường sắt nối các thành phố tương ứng. Vì vậy, bài toán đặt ra dẫn về bài toán tìm
b
c d a
b
c d a
b
c d a
117 cây khung nhỏ nhất trên đồ thị đầy đủ n đỉnh, mỗi đỉnh tương ứng với một thành phố và cạnh chính là chi phí xây dựng hệ thống đường sắt.
Bài toán nối mạng máy tính: Cần nối mạng một hệ thống gồm n máy tính đánh số từ 1 đến n. Biết chi phí nối máy i với máy j là m(i, j) (thông thường chi phí này phụ thuộc vào độ dài cáp nối cần sử dụng). Tìm cách nối mạng sao cho tổng chi phí là nhỏ nhất. Bài toán này cũng dẫn về bài toán tìm cây khung nhỏ nhất.
Có nhiều giải thuật để giải bài toán tìm cây khung nhỏ nhất, sau đây chúng ta sẽ xét hai trong số các thuật toán đó: thuật toán Kruskal và thuật toán Prim.
6.4.2.1. Thuật toán Kruskal
Thuật toán này xây dựng tập cạnh ET của cây khung nhỏ nhất T = (VT, ET) theo từng bước. Trước hết sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của trọng số. Bắt đầu từ ET = , ở mỗi bước lần lượt duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn để tìm ra cạnh phù hợp bổ sung vào tập ET sao cho không tạo thành chu trình. Thuật toán sẽ kết thúc khi thu được tập ET gồm n−1 cạnh.
Cụ thể, thuật toán có thể mô tả như sau:
1. Bắt đầu từ đồ thị rỗng T có n đỉnh.
2. Sắp xếp các cạnh của G theo thứ tự không giảm của trọng số.
3. Thêm dần các cạnh của dãy đã được xếp vào T theo nguyên tắc cạnh thêm vào không được tạo thành chu trình trong T.
4. Lặp lại Bước 3 cho đến khi số cạnh trong T bằng n−1 sẽ thu được cây khung nhỏ nhất cần tìm.
Ví dụ 6.13: Tìm cây khung nhỏ nhất của đồ thị cho trong hình 6.12.
Hình 6.14: Tìm cây khung nhỏ nhất.
v2
v3
v1
v4
v5
v6 v1
v2
v3
v4
v5
v6
33 17
18 16
4
9
8 14 20
118 Bước 1: Bắt đầu từ đồ thị rỗng T có 6 đỉnh.
Bước 2: Sắp xếp các cạnh của đồ thị theo thứ tự không giảm của trọng số:
{(v3, v5), (v4, v6), (v4, v5), (v5, v6), (v3, v4), (v1, v3), (v2, v3), (v2, v4), (v1, v2)}.
Bước 3: Thêm các cạnh (v3, v5), (v4, v6), (v4, v5) vào đồ thị T.
- Loại cạnh (v5, v6) vì khi thêm (v5, v6) vào sẽ tạo thành chu trình trong T. Tình huống tương tự cũng xãy ra đối với cạnh (v3, v4).
- Tiếp tục bổ sung cạnh (v1, v3), (v2, v3) vào T và thu dược tập ET gồm 5 cạnh:
{(v3, v5), (v4, v6), (v4, v5), (v1, v3), (v2, v3)}.
Thuật toán Kruskal có độ phức tạp là O(n2), với n là số cạnh của G.
6.4.2.2. Thuật toán Prim
Đối với những đồ thị dày (số cạnh m n(n − 1)/2) thuật toán Kruskal làm việc kém hiệu quả, ngược lại thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được gọi là phương pháp lân cận gần nhất.
Đầu vào: Đồ thị G=(V, E) đơn, liên thông, có trọng số a(u, v), u, v V, v*là đỉnh khởi đầu.
Đầu ra: Cây khung nhỏ nhất T = (VT, ET).
Bước 1: Khởi tạo
VT = {v*}, trong đó v* là đỉnh tuỳ ý của đồ thị G.
ET = .
Bước 2:
- Tìm đỉnh wj VT sao cho a(wj, vj) = min a(xi, vj) = j | xiVT dùng j để ghi nhận độ dài của cạnh có độ dài ngắn nhất trong số các cạnh nối đỉnh v với các đỉnh đang có của cây khung.
- Gán cho đỉnh vj nhãn [wj, j] (hiểu là đỉnh vj kề với đỉnh wj của cây khung nhất và có độ dài là j). Nếu không tìm đuợc wj như vậy (tức khi vj không kề với bất cứ đỉnh nào trong VT) thì gán vj nhãn [0, ].
119 Bước 3:
Trong khi (| VT | < n):
- Bước 3.1: Chọn đỉnh vj* sao cho
j* = min j | vj VT
VT = VT {vj*}, ET = ET {(wj*, vj*)}.
- Bước 3.2:
Nếu |VT| = n thì thuật toán dừng và (VT, ET) là cây khung nhỏ nhất.
Ngược lại thì chuyển sang Bước 3.3.
- Bước 3.3: Với các đỉnh vj VT kề với vj*, ta thay đổi nhãn của chúng như sau:
Nếu j > a(vj*, vj): đặt j = a(vj*, vj) và nhãn của vj là [vj*, j].
Ngược lại, giữ nguyên nhãn của vj.
Ví dụ 6.14: Xét đồ thị cho trong hình 6.14 ở trên, tìm cây khung nhỏ nhất của đồ thị theo thuật toán Prim.
Từ hình 6.14, ta có ma trận trọng số của đồ thị như sau:
Các bước lặp của thuật toán được thể hiện theo bảng 6.1, trong đó, các đỉnh đánh dấu * là đỉnh được chọn để bổ sung vào cây khung (khi đó nhãn của nó không biến đổi trong các
0 33 17
33 0 18 20
17 18 0 16 4
20 16 0 9 8
4 9 0 14
8 14 0
1 2 3 4
5
6 1
2 3 4
5
6
120 bước lặp tiếp theo, ta dùng dấu – để ghi nhận điều này), các nhãn của mỗi đỉnh i được ghi dưới dạng [u, d(u)], u là đỉnh cây khung và kề với đỉnh i và d(u) = a[u, i].
Bảng 6.1: Kết quả các bước khi thực hiện thuật toán Prim.
Bước lặp
Đỉnh 1
Đỉnh 2
Đỉnh 3
Đỉnh 4
Đỉnh 5
Đỉnh
6 VT ET
Khởi
tạo [1,0] [1,33] [1,17]
* [1, ] [1, ] [1, ] 1
1 - [3,18] - [3,16] [3,4]* [1, ] 1, 3 (1, 3) 2 - [3,18] - [5,9]* - [5,14] 1, 3, 5 (1, 3), (3,5)
3 - [3,18] - - - [4,8]* 1, 3, 5, 4 (1, 3), (3,5), (4, 5)
4 - [3,18]
* - - - - 1, 3, 5,
4, 6
(1, 3), (3,5), (4, 5), (4, 6)
5 - - - 1, 3, 5,
4, 6, 2
(1, 3), (3,5), (4, 5), (4, 6),
(2,3)
Vậy cây khung nhỏ nhất có được là T = {(1, 3), (3, 5), (4, 5), (4, 6), (2, 3)} với độ dài là 17 + 4 + 9 + 8 + 18 = 56.
BÀI TẬP CHƯƠNG 6
1. Vẽ đồ thị được cho bởi ma trận trọng số sau:
a)
1 2 3 2 0 4 3 4 0
b)
1 2 0 1 2 0 3 0 0 3 1 1 1 0 1 0
c)
0 1 3 0 4 1 2 1 3 0 3 1 1 0 1 0 3 0 0 2 4 0 1 2 3
.
2. Tìm ma trận kề biểu diễn đồ thị cho sau đây:
121 3. Với đồ thị cho sau đây, tìm đường đi ngắn nhất từ đỉnh A đến đỉnh D.
4. Tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh còn lại trong đồ thị sau:
5. Tìm cây khung nhỏ nhất của đồ thị sau đây theo 2 thuật toán Kruskal và Prim:
5. Viết chương trình đếm số thành phần liên thông của một đồ thị vô hướng có n đỉnh.
1 2 3
4 5 6 7
8 9 10
B C
F
A D
E 3
1
20 2
3
8 5
13 4
6
8
c b
e d
k
h
a g
4
4
3 2
2
2
7
5 3 4
7 11
12 5
a b
c d e f
g h
42 10 14 4
3 1 11
3
15 5 7
20 9
122 6. Viết chương trình cài đặt thuật toán tìm đường đi ngắn nhất giữa 2 đỉnh cho trước trong đồ thị vô hướng có n đỉnh.
7. Viết chương trình cài đặt thuật toán tìm cây khung nhỏ nhất của đồ thị vô hướng có n đỉnh.
123