CHƯƠNG 3: MỘT SỐ ỨNG DỤNG CỦA BÀI TOÁN CÂY KHUNG GIẢI QUYẾT VẤN ĐỀ THỰC TẾ
3.1 BÀI TOÁN CÁP MẠNG
Một hệ thống mạng bao gồm N máy tính đƣợc đánh số từ 1 đến N đƣợc nối với nhau thành mạng bằng cáp mạng là một loại dây truyền tin đắt tiền. Trong mạng này, hai máy tính bất kỳ đều có thể liên lạc đƣợc trực tiếp với nhau hoặc thông qua một vài máy tính trung gian. Ta gọi tính chất này là tính liên thông của mạng máy tính. Chi phí để xây dựng một đường mạng trực tiếp nối từ máy tính i đến máy tính j bằng aij=aji≥0 với mọi i,j (aii=0). Hai đường dây mạng khác nhau không cắt nhau tại điểm không là đầu mút. Hiện đã xây dựng được K đường mạng.
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
thông đƣợc với nhau.
Phân tích bài toán :
Bài toán đƣợc đƣa về dạng tìm cây khung cực tiểu hay còn gọi là cây bao trùm ngắn nhất. Ta coi toàn bộ hệ thống mạng máy tính là một đồ thị, mỗi máy tính trong mạng máy tính là một nút, việc bỏ bớt một số dây nối trong hệ thống mạng máy tính chính là việc bỏ đi một số cạnh của đồ thị. Việc tìm ra mạng tối thiểu cho hệ thống máy tính này chính là tìm ra một cây bao trùm ngắn nhất của mạng ban đầu.
Input: tệp văn bản tên DOTHI_min.INP
- Dòng đầu tiên ghi hai số tự nhiên n và m cách nhau qua dấu cách, biểu thị số đỉnh (n) và số cạnh (m) của đồ thị.
- Mỗi dòng thứ i=1,2,...,m trong số m dòng tiếp theo ghi ba giá trị x,y và d cách nhau qua dấu cách với ý nghĩa cạnh (x,y) của đồ thị có chiều dài d.
Output: tệp văn bản tên DOTHI.OUT
- Danh sách các cạnh đƣợc chọn.
- Dòng cuối ghi tổng chiều dài tìm đƣợc.
Thuật toán:
Ta dùng giải thuật Kruskal với kỹ thuật nhƣ sau:
- Duyệt các cạnh từ chiều dài nhỏ đến lớn.
- Cạnh đƣợc chọn sẽ là cạnh không tạo thành chu trình khi ghép nó vào đồ thị kết quả.
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
với một điểm khác biệt duy nhất là duyệt các cạnh theo trật tự tăng dần của trọng số.
Bước 1. Sắp các cạnh tăng theo trọng số;
Bước 2. Khởi trị với cây khung rỗng;
Bước 3. Duyệt các cạnh theo trật tự đã sắp: nếu cạnh (u,v) không tạo thành chu trình với cây khung thì nạp (u,v) vào cây khung.
- Điều kiện để cạnh (u,v) không tạo thành chu trình với cây khung là Union(u,v) = 0.
- Tùy theo các ứng dụng, ta có thể sử dụng trọng số để biểu thị độ dài đường đi giữa hai đỉnh hoặc chi phí phải trả khi đi từ đỉnh này đến đỉnh kia.
- Ta sử dụng mảng c với mỗi phần tử là một bản ghi gồm 3 trường nguyên x, y và p dùng để chứa các cạnh, trong đó x và y là số hiệu các đỉnh đầu mút của cạnh và p là trọng số của cạnh (x,y) đó.
- Ngoài ra, ta sử dụng mảng một chiều khung dùng để chứa chỉ số của các cạnh đƣợc chọn vào cây khung.
Ta minh họa bài toán bằng ví dụ dưới đây với số lượng đỉnh và cạnh giới hạn ( n=8, m= 17).
1
5 6
4 8
8
6 1 2
7 9 5 5
1 6
7 8 1
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
DOTHI.INP 8 17 1 2 8 1 3 4 1 4 6 1 5 1 1 6 2 2 3 2 2 4 7 3 4 9 3 7 4 3 8 3 4 5 5 4 6 5 4 8 1 5 6 6 6 7 8 6 8 7 7 8 1
Ý nghĩa:
Đồ thị có 8 đỉnh và 17 cạnh.
Cạnh (1,2) dài 8, Cạnh (1,3) dài 4, Cạnh (1,4) dài 6,..., Cạnh (7,8) dài 1 đơn vị.
DOTHI.OUT 1 5
4 8 7 8 2 3 1 6 3 8 1 3
Ý nghĩa: Cây bao trùm ngắn nhất của đồ thị đã cho gồm 8 đỉnh và 7 cạnh là ( chiều dài mỗi cạnh đƣợc ghi sau dấu hai chấm ):
Cạnh 1. (1,5): 1 Cạnh 2. (4,8): 1 Cạnh 3. (7,8): 1 Cạnh 4. (2,3): 2 Cạnh 5. (1,6): 2 3
2
7 4
2
4 3
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
Lưu ý rằng đồ thị kết quả thu được ở các bước trung gian có thể không liên thông mà bao gồm nhiều mảnh liên thông ( cây con ). Loại đồ thị này đƣợc gọi là rừng. Kết quả cuối cùng sẽ là cây vì nó liên thông và đƣợc tạo thành từ n-1 cạnh. Ta vận dụng tổ chức find-union cho các tập đỉnh rời nhau để quản lý các tập đỉnh đƣợc chọn nhằm phát hiện chu trình. Cạnh (x,y) khi đƣợc ghép vào đồ thị trung gian sẽ tạo thành chu trình khi và chỉ khi các đỉnh x và y cùng nằm trong một cây của đồ thị ( rừng ) trung gian đó.
Nhƣ vậy mỗi cây con của đồ thị trung gian đƣợc quản lý nhƣ một tập con của tập các đỉnh 1..n của đồ thị ban đầu. Tập con này có phần tử đại diện chính là gốc của cây tương ứng. Phần tử này được chọn theo mã số nhỏ nhất. Các đỉnh còn lại của cây con đều trỏ đến gốc đó.
Dễ thấy cây bao trùm luôn luôn có n đỉnh và n-1 cạnh.
Chương trình mô phỏng thuật toán:
struct canh { int x, y, p; } c[MN];
int khung[MN]; // MN la so luong toi da cac canh void CayKhungMin(){
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
int t = 0; // tong trong so ifstream f(inf); // mo input file
f >> n >> m; // doc so dinh n, so canh m // doc cac canh vao mang c
for(i = 1; i <= m; ++i)
f >> c[i].x >> c[i].y >> c[i].p;
f.close();
Sort(1,m);// sap tang cac canh theo trong so p Initd(); n1 = n-1;
j = 0;// dem so canh cua cay khung for (i = 1; i <= m; ++i){
if (Union(c[i].x,c[i].y)){
++j; // nap canh i vao cay khung
khung[j] = i; // Danh dau canh da chon vao cay khung if (j == n1) break;
} }
// Giai trinh ket qua
cout << "\n Cay Khung cuc tieu gom " << n << " dinh, "
<< j << " canh:";
for (i = 1; i <= j; ++i) {
cout << endl << c[khung[i]].x << " " << c[khung[i]].y;
t += c[khung[i]].p;
}
cout << "\n Tong trong so min: " << t;
}
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
QUÂN SỰ
Theo thông tin tình báo của ta thu được một sơ đồ mạng lưới căn cứ quân sự của địch bao gồm N căn cứ có tên đƣợc đánh bí số từ 1 đến N. Chi phí để xây dựng một đường hai chiều trực tiếp nối từ căn cứ i đến căn cứ j bằng aij=aji≥0 với mọi i,j (aii=0).
Bài toán đặt ra là : Hãy tìm ra một số tuyến đường quan trọng nhất trong toàn bộ mạng lưới quân sự nối giữa các cứ điểm nào đó sao cho:
Chỉ cần ta đánh vào các tuyến đường này sẽ làm cắt đứt mối liên hệ của toàn bộ hệ thống liên lạc giữa các cứ điểm địch chứ không cần phải đánh vào tất cả các tuyến đường , việc này nhằm giảm bớt thiệt hại về người và của cũng như thời gian, công sức của quân ta.
Phân tích bài toán :
Bài toán đƣợc đƣa về dạng tìm cầu hay cạnh trọng yếu của đồ thị. Ta coi cả hệ thống quân sự của địch là một đồ thị, mỗi cứ điểm trong hệ thống quân sự của địch là một nút thì việc tìm ra các tuyến đường trọng yếu trong hệ thống quân sự này chính là việc tìm ra cầu hay cạnh trọng yếu của đồ thị.
Input: tệp văn bản tên CAU.INP
- Dòng đầu tiên ghi hai số tự nhiên n và m cách nhau qua dấu cách, biểu thị số đỉnh (n) và số cạnh (m) của đồ thị.
- Mỗi dòng thứ i=1,2,...,m trong số m dòng tiếp theo ghi ba giá trị x,y và d cách nhau qua dấu cách với ý nghĩa cạnh (x,y) của đồ thị có chiều dài d.
Output: tệp văn bản tên DOTHI.OUT
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
- Liệt kê các cầu.
Ta minh họa bài toán bằng ví dụ dưới đây với số lượng đỉnh và cạnh giới hạn ( n=12, m= 16).
1
2
12
3
8
4
11
1
7
10
2
6 5
9
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
DOTHI.INP 12 16 1 2 1 3 1 7 1 11 2 3 3 4 3 7 3 8 3 11 4 5 4 7 4 9 5 10 6 7 6 9 8 12
Ý nghĩa:
Đồ thị có 12 đỉnh và 16 cạnh.
Cạnh (1,2) Cạnh (1,3) Cạnh (1,7) ,..., Cạnh (8,12)
DOTHI.OUT 3
3 8 4 5 5 10
Ý NGHĨA:
Mạng có 3 cầu (3,8)
(4,5) (5,10)
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
Thuật toán:
Nhận xét: Mọi cầu phải là cạnh khung, nghĩa là phải thuộc một cây hoặc rừng khung.
Thật vậy, nếu cạnh (x,y) không là cạnh khung thì khi xét cạnh đó trong thủ tục tìm cây khung ta phải có Union(x,y) = 0. Thế tức là đồ thị có chu trình chứa cạnh (x,y) này. Khi bỏ cạnh (x,y) trong chu trình ta thấy các đỉnh nằm trên chu trình này vẫn liên thông với nhau, do đó số thành phần liên thông là không đổi. Điều này cho thấy (x,y) không thể là cầu.
Chú ý rằng mệnh đề đảo của mệnh đề trên không đúng. Cạnh 3-4 của hình trong thí dụ có thể nằm trong rừng khung nhƣng 3-4 không phải là cầu.
Nhận xét trên cho phép ta chỉ kiểm tra những cạnh khung để phát hiện cầu.
Bước 1. Tìm tập các cạnh khung bằng kỹ thuật Find-Union và ghi nhận các giá trị sau đây:
- số lƣợng cạnh khung vào biến soCanh;
- số mảnh liên thông vào biến soManh ; - mảng khung chứa các số hiệu cạnh khung.
void CanhKhung(int& soCanhKhung, int& soManh){
int i;
ifstream f(inf); // mo input file
f >> n >> m; // Doc so dinh n, so canh m Initd();
soCanhKhung = 0; soManh = n; // so manh lien thong for (i = 1; i <= m; ++i){ // doc, duyet cac canh
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
if (Union(c[i].x,c[i].y) == 1){
--soManh;
khung[++soCanhKhung] = i; // nap canh i vao khung }
}
f.close(); // dong input file }
Bước 2. Duyệt các cạnh khung (x,y) theo kỹ thuật Find-Union. Nếu thử bỏ cạnh (x,y) mà số thành phần liên thông tăng lên thì (x,y) là cầu, ta đƣa cạnh này vào mảng cau.
soCau = 0;
for (i = 1; i <= soCanhKhung; ++i) if (FU(khung[i]) > soManh)
cau[++soCau] = khung[i];
Hàm FU(i) vận dụng kỹ thuật Find Union để xác định số thành phần liên thông của đồ thị khuyết cạnh thứ i.
3.3 CÀI ĐẶT CHƯƠNG TRÌNH
Chương trình của bài tập ứng dụng được viết bằng ngôn ngữ lập trình C++, đã đƣợc lập trình và chạy thử nghiệm tốt cho đƣợc các kết quả tối ƣu.
Kết luận : Có nhiều bài toán ứng dụng, nếu đƣợc mô hình tốt bằng đồ thị thì sẽ dễ dàng giải quyết đƣợc trên máy tính. Ứng dụng các thuật toán của cây khung rất thực tiễn và quan trọng giúp cho việc nhận dạng và định hướng được một số bài toán có tính chất đồ thị. Việc nghiên cứu lý
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
dụng của nó góp phần phát triển các kỹ thuật Tin học.
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Lý thuyết đồ thị là một mảng rất rộng. Nếu đi hết tất cả các vấn đề của lý thuyết đồ thị thì đó là một khối lƣợng kiến thức rất khổng lồ, các vấn đề ứng dụng của đồ thị cũng rất nhiều, rất phong phú và đa dạng. Trong luận văn đ ã nghiên cứu và trình bày những kiến thức cơ bản về lý thuyết đồ thị nói chung và lý thuyết về cây khung nói riêng. Đồng thời luận văn cũng đã nhận dạng và phân loại một số dạng bài toán ứng dụng cây khung vào trong thực tiễn. Qua đó luận văn đã đạt đƣợc một số kết quả nhƣ sau :
Về lý thuyết :
Luận văn đã nghiên cứu đƣợc các kiến thức cơ bản nhất về lý thuyết đồ thị nói chung và lý thuyết về cây khung nói riêng. Luận văn cũng đã phân tích kỹ một số thuật toán về cây khung và một vài ứng dụng cây khung áp dụng trong thực tiễn.
Về ứng dụng :
Luận văn đã phân tích và cài đặt một số thuật toán của cây khung ứng dụng trong thực tiễn.
- Bài toán cáp mạng.
- Bài toán tuyến đường quan trọng trong quân sự.
Phạm vi và khả năng áp dụng :
Luận văn là một tài liệu tham khảo tốt cho giáo viên dạy bộ môn Tin học ở các trường THPT và các trường chuyên nghiệp, những bạn sinh viên muốn tìm hiểu các khái niệm cơ bản về lý thuyết đồ thị cũng nhƣ lý