Sáng kiến kinh nghiệm Bài toán tìm cây khung trên đồ thị vô hướng

 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM 
 Độc lập - Tự do - Hạnh phúc 
TÊN ĐỀ TÀI: 
 BÀI TOÁN TÌM CÂY KHUNG TRÊN ĐỒ 
 THỊ VÔ HƯỚNG 
 Đồng Hới, tháng 01 năm 2019 
 1 
 1. PHẦN MỞ ĐẦU 
1.1. Lý do chọn đề tài 
 Như ta đã biết, muốn giải một bài toán trong Tin học thì việc tìm ra ý tưởng giải 
thuật là một điều bắt buộc phải làm, không kém quan trọng và đi kèm với việc đó là 
phải biết lựa chọn cấu trúc dữ liệu phù hợp với ý tưởng giải thuật đó nhằm tối ưu hóa 
bài toán. 
 Chuyên đề về đồ thị là một trong những chuyên đề cơ bản khi giảng dạy cho học 
sinh ở lớp chuyên Tin. Với rất nhiều bài toán trên thực tế ta có thể mô hình hóa, đưa 
về cấu trúc trên đồ thị để giải quyết. Đồ 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ột mạng lưới 
giao thông; Lập lịch sửa chữa các tuyến đường sao cho vẫn đảm bảo lưu thông giữa 
các khu dân cư, Lâp kế hoạch lắp đặt hệ thống điện sao cho tiết kiệm chi phí nhất ... 
Để khai thác các tính chất của đồ thị trong việc giải quyết một số bài toán thực tế, thì 
các bài toán có thể giải dựa trên tính chất liên thông của đồ thị là một lĩnh vực rất quan 
trọng. Trong các bài toán đó có bài toán “Tìm cây khung của một đồ thị vô hướng liên 
thông” được lựa chọn và đưa vào giảng dạy cho khối lớp chuyên Tin của trường 
THPT Chuyên Võ Nguyên Giáp. 
 Đó là lí do tôi chọn đề tài: “Bài toán tìm cây khung trên đồ thị vô hướng” làm 
đề tài nghiên cứu cho sáng kiến kinh nghiệm của mình. 
1.2. Điểm mới của đề tài 
 “Bài toán tìm cây khung trên đồ thị vô hướng” là một trong những chuyên đề 
cơ bản và quan trọng khi bồi dưỡng học sinh giỏi Tin học trong nhà trường là 
chuyên đề về lý thuyết đồ thị và các thuật toán trên đồ thị. Có nhiều dạng đồ thị, 
nhiều dạng bài toán và thuật toán trên đồ thị. Một bài toán tối ưu và nổi tiếng về đồ 
thị là bài toán tìm cây khung, cây khung cực tiểu. 
 Giải pháp được đặt ra là sử dụng thuật toán tìm cây khung, cây khung cực tiểu 
để giải các bài toán đặc trưng của nó đồng thời áp dụng thuật toán cho lớp bài toán 
cơ bản nhất như kiểm tra tính liên thông của đồ thị, đếm số thành phần liên thông 
của đồ thị. Khi sử dụng thuật toán này để quay trở lại giải quyết các bài toán cơ 
bản nói trên sẽ cho học sinh có định hướng tốt trong việc phân tích, lựa chọn thuật 
toán phù hợp, tốt nhất để thiết kế, cài đặt cho mỗi bài toán. 
 3 
 2.2. Một số định nghĩa liên quan đến lý thuyết đồ thị 
 Định nghĩa đơn đồ thị vô hướng 
 Đơn đồ 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ác nhau của V gọi là các cạnh. 
 1 2 
 3 
 5 4 
 Định nghĩa các đỉnh và cạnh của đồ thị vô hướng 
 Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u, v) là cạnh 
của đồ thị G. Nếu e=(u, v) là cạnh của đồ thị thì ta nói cạnh này liên thuộc với hai đỉnh 
u và v, hoặc cũng nói là cạnh e là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ 
được gọi là các đỉnh đầu của cạnh (u, v). 
 Định nghĩa bậc của một đỉnh trong đồ thị vô hướng 
 Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ 
ký hiệu là deg(v). 
 6 1 2 
 3 
 5 4 
 Định nghĩa đường đi trong đồ thị vô hướng 
 Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n nguyên dương, trên đồ thị vô 
hướng G = (V, E) là dãy x0, x1, x2, ..., xn-1, xn trong đó: 
 u = x0, v = xn, (xi, xi+1) € E, i = 0, 1, 2, 3 ... n-1 
Đường đi nói trên còn có thể biểu diễn dưới dạng dãy cạnh: 
 (x0, x1), (x1, x2), (x2, x3), ..., (xn-2, xn-1), (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 gọi là đơn nếu như không có cạnh nào bị lặp lại. 
 Định nghĩa chu trình trong đồ thị vô hướng 
 Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n nguyên dương, trên đồ thị vô 
hướng G = (V, E) là dãy x0, x1, x2, ..., xn-1, xn trong đó: 
 u = x0, v = xn, (xi, xi+1) E , i = 0, 1, 2, 3 ... n-1. 
 5 
 Yêu cầu: Hãy giúp Chủ đầu tư lập kế hoạch xây dựng một số cầu ít nhất nhưng vẫn 
đảm bảo người dân ở một đảo có thể đến được các đảo còn lại. 
Dữ liệu vào: Cho trong file BRIDGE.INP có cấu trúc: 
- Dòng 1: Ghi số nguyên dương n, là số lượng đảo trong đặc khu (2 ≤ n ≤ 100). 
- Dòng thứ i trong n dòng tiếp theo: Mỗi dòng ghi n số 0 hoặc 1, số thứ j = 1 thể hiện 
có thể xây được cầu nối trực tiếp giữa đảo i với đảo j (1 ≤ i, j ≤ n). 
Dữ liệu ra: Ghi ra file văn bản BRIDGE.OUT theo cấu trúc: 
- Dòng 1: Ghi số nguyên dương k, là số cầu cần phải xây dựng 
- k dòng tiếp theo: Mỗi dòng ghi 2 số p, q thể hiện việc cần xây dựng cầu nối giữa đảo 
p với đảo q. Hai số được ghi cách nhau một dấu cách. 
Ví dụ: 
 BRIDGE.INP BRIDGE.OUT 
 6 5 
 0 1 0 1 1 1 1 2 
 1 0 1 1 0 0 1 4 
 0 1 0 0 0 0 4 5 
 1 1 0 0 1 0 2 3 
 1 0 0 1 0 0 1 6 
 1 0 0 0 0 0 
2.3.2. Đưa bài toán về mô hình đồ thị 
 Với bài toán thực tế ở trên, ta có thể mô hình hóa về đồ thị vô hướng như sau: 
- Gọi mỗi đảo là một đỉnh của đồ thị. 
- Gọi mỗi cây cầu nối trực tiếp giữa hai đảo là một cạnh của đồ thị. 
Từ ví dụ cụ thể đã cho ở trên ta có đồ thị G = (V, E) sau đây: 
 6 1 2 
 3 
 5 4 
 Tập các đỉnh: V = {1,2,3, 4,5,6} 
 Tập các cạnh: E = {(1,2);(1,4);(1,5);(1,6);(2,3);(2, 4);(4,5)} 
2.3.3. Thuật toán 
 7 
 Begin 
 Nạp q vào Stack, đánh dấu đã thăm q; 
 End; 
 If p = v then 
 Begin 
 BFS:= False; 
 Exit; 
 End; 
 End; 
 End; 
2.3.4. Chương trình 
* Cấu trúc dữ liệu: 
 - Dùng hai mảng P, Q: Array[0..100] of Integer là danh sách kề chứa các cạnh 
của đồ thị G, e = (Q[i], P[i]) là một cạnh của đồ thị. 
 - Dùng mảng B: array[1..100, 1..100] of Integer là ma trận kề để chứa các cạnh 
của cây khung T tìm được. 
 - Dùng mảng Free: array[1..max] of Boolean để đánh dấu các đỉnh đã thăm 
trong cây T để kiểm chu trình khi muốn nạp thêm một cạnh e = (Q[i], P[i]) vào cây 
khung T. 
 - Dùng mảng Stack: array[1..max] of Integer để sử dụng thuật toán DFS trong 
việc kiểm tra chu trình khi muốn nạp thêm một cạnh e = (Q[i], P[i]) vào cây khung T. 
* Chương trình: 
Program Thuat_toan_DFS_tim_cay_khung; 
Const 
 Max = 1000; 
 fi='BRIDGE.INP'; 
 fo='BRIDGE.OUT'; 
Type mmci=Array[0..Max] of Integer; 
Var f:text; 
 P,Q:mmci; 
 B: array[1..Max, 1..Max] of Integer; 
 Free: array[1..Max] of Boolean; 
 Stack: array[1..Max] of Integer; 
 n, S, Last,Sl: Integer; 
Procedure Init; 
Begin 
 9 
 Begin 
 DFS:=True; 
 Fillchar(Free,Sizeof(Free),True); 
 FillChar(Stack, sizeof(Stack), 0); 
 Last := 0; 
 SPush(u); Free[u]:=False; 
 While Last > 0 do 
 Begin 
 i:=SPop; 
 For j:=1 to N do 
 if (B[i,j] = 1) And Free[j] then 
 Begin 
 SPush(j); 
 Free[j]:=False; 
 End; 
 if i = v then 
 Begin 
 DFS:= False; 
 Exit; 
 End; 
 End; 
End; 
Procedure Solution; 
Var u,v,i:Integer; 
Begin 
 For i:=1 to Sl do 
 Begin 
 u:=P[i]; 
 v:=Q[i]; 
 if DFS(u,v) then 
 Begin 
 B[u,v]:=1; 
 B[v,u]:=1; 
 End; 
 End; 
End; 
Procedure Write_Data; 
Var i,j:Integer; 
 11 
 2.4.1. Bài toán thực tế 
Bài toán Cắm trại CAMP.??? 
 Tỉnh đoàn Q tổ chức cắm trại nhân dịp kỹ niệm ngày thành lập đoàn 26-3. Theo 
kế hoạch sẽ có n trại tham gia gồm một trại trung tâm của Ban tổ chức và trại của các 
đơn vị, tất cả các trại được đánh số thứ tự từ 1, 2, ..., n. Ban tổ chức đã chọn được địa 
điểm, khảo sát và lập bản đồ bố trí các trại, trong bản đồ có ghi rõ khoảng cách trực 
tiếp giữa các trại để lắp đặt hệ thống dây điện. Khoảng cách giữa các trại được thể 
hiện trong ma trận A kích thước n×n, trong đó A[i, j] là khoảng cách từ trại i đến trại j. 
 Vấn đề đặt ra là Ban tổ chức muốn lắp đặt hệ thống dây điện đảm bảo an toàn 
và tiết kiệm chi phí nhất. 
Yêu cầu: Hãy lập kế hoạch lắp đặt hệ thống dây điện từ trại trung tâm đến các trại sao 
cho đảm bảo các trại đều có nguồn điện đến tận trại mình và tổng chiều dài dây điện 
cần lắp đặt là nhỏ nhất. 
Dữ liệu vào: Cho trong file CAMP.INP có cấu trúc: 
- Dòng 1: Ghi số nguyên dương n, là số lượng trại tham gia (2 ≤ n ≤ 100). 
- Dòng thứ i trong n dòng tiếp theo: Mỗi dòng ghi n số nguyên, số thứ j có giá trị là k 
thể hiện giữa trại i với trại j có thể nối dây điện trực tiếp với nhau và độ dài dây nối là 
k, nếu k = 0 tức là không thể nối dây điện trực tiếp giữa trị i với trại j (1 ≤ i, j ≤ n; 0 ≤ k 
≤ 32000). 
Dữ liệu ra: Ghi ra file văn bản CAMP.OUT theo cấu trúc: 
- Dòng 1: Ghi số nguyên dương d, là tổng độ dài dây điện cần lắp đặt. 
- d dòng tiếp theo: Mỗi dòng ghi 3 số p, q, k thể hiện việc cần nối dây điện trực tiếp 
giữa trại p với trại q và độ dài dây nối là k. Các số được ghi cách nhau một dấu cách. 
Ví dụ: 
 CAMP.INP CAMP.OUT 
 8 61 
 0 20 0 8 17 0 0 0 1 4 8 
 20 0 11 5 0 0 0 0 2 3 11 
 0 11 0 0 19 15 0 0 2 4 5 
 8 5 0 0 6 0 0 0 3 6 15 
 17 0 19 6 0 0 0 0 4 5 6 
 0 0 15 0 0 0 12 7 6 8 7 
 0 0 0 0 0 0 0 9 7 8 9 
 0 0 0 0 12 0 0 0 
 0 0 0 0 7 9 0 0 
 13 
 E: E \{} e ; 
 If F{ e }mà không tạo chu trình then 
 F: F  {} e ; 
 End; 
 If ( F n 1) then Đồ thị G không liên thông; 
 End; 
2.4.4. Chương trình 
*. Chương trình sử dụng thuật toán DFS kiểm tra việc tạo thành chu trình: 
Program CAMP_Kruskal_DFS; 
Const 
 max = 1000; 
 fi='CAMP.INP'; 
 fo='CAMP.OUT'; 
Type mmci=Array[0..max] of Integer; 
Var 
 f:text; 
 P,Q,L:mmci; 
 B: array[1..max, 1..max] of Integer; 
 Free: array[1..max] of Boolean; 
 Stack: array[1..max] of Integer; 
 n, S, Last,Sl: Integer; 
Procedure Init; 
 Begin 
 FillChar(P, SizeOf(P), 0); 
 FillChar(Q, SizeOf(Q), 0); 
 FillChar(B, SizeOf(B),0); 
 Sl:=0; 
 End; 
Procedure Read_Data; 
 Var i,j,u: Integer; 
 Begin 
 Assign(f,fi);Reset(f); 
 Readln(f,N); 
 For i:=1 to n do 
 Begin 
 15