Cây bao trùm ngắn nhất

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ùm củ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:

Có 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 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.

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 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.

(* 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.