Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Friday, January 17, 2014



Bài 5.4. Cây bao trùm ngắn nhất
           Cho một đồ thị liên thông G vô hướng bao gồm n đỉnh, mã số từ 1 đến n, và m cạnh nối hai đỉnh với nhau. Mỗi cạnh có chiều dài cho trước. Tính liên thông của đồ thị cho biết với hai đỉnh cho trước tuỳ ý ta luôn tìm được các cạnh gối đầu nhau để đi từ đỉnh này đến đỉnh kia. Hãy chỉ ra một phần P của đồ thị thoả các tính chất sau:
(i)      P chứa tất cả các đỉnh của G;
(ii)     P chứa một số ít nhất các cạnh của G;
(iii)   P là đồ thị liên thông;
(iv)    Tổng chiều dài các cạnh của P là ngắn nhất.
Đồ thị P thoả ba tính chất (i), (ii) và (iii) được gọi là cây bao trùmcủa đồ thị G. Nếu P thoả thêm tính chất (iv) thì P được gọi là cây bao trùm ngắn nhất của G. Một số tài liệu dùng thuật ngữ cây khung thay cho cây bao trùm và cây khung cực tiểu thay cho cây bao trùm ngắn nhất.
Bài toán trên có nhiều ứng dụng thực tiễn. Một trong số ứng dụng đó được mô tả thông qua thí dụ sau:
n máy tính được nối với nhau thành mạng bằng cáp quang 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 với nhau trực tiếp hoặc thông qua một vài máy 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. Hãy bỏ bớt một số dây nối để n máy tính trên vẫn liên thông được với nhau. Mạng tối thiểu thu được chính là một cây bao trùm ngắn nhất của mạng ban đầu.
Dữ liệu vào: tệp văn bản tên DOTHI.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 yd 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.
Dữ liệu ra: tệp văn bản tên DOTHI.OUT bao gồm:
-          Danh sách các cạnh được chọn.
-          Dòng cuối cùng ghi tổng chiều dài tìm được.
Thuật toán
Ta dùng thuật giải 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ả.
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
14

Ý 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
cạnh 6. (3, 8): 3
cạnh 7. (1, 3): 4
Tổng chiều dài 7 cạnh đã chọn là: 14.

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 xy 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 n - 1 cạnh.
(* Pascal  *)
(*---------------------------------
 DOTHI.PAS Cay bao trum ngan nhat
      (thuat giai Kruskal)
---------------------------------*)
program DoThi;
uses crt;
const
MN = 100; bl = #32; {dau cach}
fn = 'DoThi.inp'; gn = 'DoThi.out';
nl = #13#10; {xuong dong}
type { Mo ta mot canh cua do thi }
CANH = record
    x,y: integer; {canh (x,y) }
    len: integer; { do dai canh }
 end;
var
a: array[0..MN] of CANH; { Mang cac canh }
d: array[1..MN] of integer;{dung cho find-union }
n: integer; {n: so dinh }
m: integer; {so canh }
f,g: text;
procedure Doc; (* Doc du lieu *)
var i: integer;
begin
assign(f,fn); reset(f);
read(f,n,m);
for i :=  1 to m do
    read(f,a[i].x,a[i].y,a[i].len);
close(f);
end;
(* Sap canh tang theo len *)
procedure qsort(d,c: integer);
var
      i,j,m: integer;
      t: CANH;
begin
i := d;
j := c;
m := a[(i+j) div 2].len; {diem giua}
while (i<=j) do
begin
while a[i].len < m do i := i+1;
while a[j].len > m do j := j-1;
if i<=j then
    begin
  t :=  a[i];
  a[i] :=  a[j];
  a[j] :=  t;
  i := i+1; j := j-1;
    end;
end;
    if d < j then qsort(d,j);
    if i < c then qsort(i,c);
end;
{Tim dai dien cua tap chua x }
function Find(x: integer): integer;
begin
while x <> d[x] do x :=  d[x];
Find :=  x;
end;
{--------------------------------
Hop nhat 2 tap dinh: tap chua dinh x va tap chua dinh y.
Union = false: Neu canh (x,y) tao   thanh chu trinh.
Union = true: Neu (x,y) khong tao   thanh chu trinh.
----------------------------------}
function Union(x,y: integer): Boolean;
begin
Union := false;
x := Find(x);
y := Find(y);
if x = y then exit;
if x < y then d[y] := x
else d[x] := y;
Union := true;
end;
procedure CBTNN;(* Cay bao trum ngan nhat *)
var
i, t: integer;
k: integer;
begin
assign(g,gn); rewrite(g);
for i :=  1 to n do d[i] :=  i; {Khoi tri }
k :=  0;
t :=  0; {tong chieu dai cac canh}
for i := 1 to m do
{duyet cac canh theo chieu dai tang dan } 
if Union(a[i].x,a[i].y) then
begin
    writeln(g,a[i].x,bl,a[i].y);
    t :=  t + a[i].len;
    inc(k);
           if k=n-1 then break;{chon duoc n-1 canh la du }
end;
writeln(g,t);
close(g);
end;
BEGIN
Doc; qsort(1,m);
CBTNN; readln;
END.      

0 comments:

Post a Comment

Popular Posts