Phần 3
Cây - CÂy khung ngắn nhất
I / Định nghĩa :
Cây là đồ thị hữu hạn , vô hớng , liên thông , không có chu trình , có ít nhất 2
đỉnh .
II / Tính chất :
1 - Định lý 1 :
Nếu H là cây có N đỉnh thì H có các tính chất sau đây :
a) Thêm vào H một cạnh nối 2 đỉnh bất kỳ không kề nhau , H sẽ xuất hiện chu trình .
b) Bớt đi 1 cạnh trong H thì H không liên thông
c) Giữa 2 đỉnh bất kỳ của H luôn tồn tại 1 đờng đi duy nhất ( vậy H là đồ thị đơn)
d) H có N-1 cạnh
2 - Định lý 2 :
Nêú đồ thị G liên thông có N đỉnh và N-1 cạnh thì G là cây .
Vậy cây là đồ thị liên thông có chu số bằng 0 ( suy từ công thức Ơle )
3 - Ghi chú :
Từ 1 đồ thị có thể hình thành nhiều cây khác nhau ( gọi là các cây khung của đồ
thị ) . Trong số các cây khung của đồ thị , có 1 cây đợc tạo ra một cách đơn giản nh sau :
nối 1 đỉnh với n-1 đỉnh còn lại !
Số cây khung của 1 đồ thị đầy đủ là N
n-2
( N số đỉnh )
Số cây khung của một đồ thị có hữu hạn đỉnh là một số hữu hạn ,nên luôn tìm đợc ít nhất
1 cây khung có tổng độ dài nhỏ nhất ( nguyên lý biên ). Ta gọi cây khung này là cây
khung ngắn nhất .
Bài toán tìm cây khung ngắn nhất là một bài toán gặp trong thực tế :
Thí dụ : Xây dựng mạng dây điện thoại nối N thành phố sao cho 2 thành phố bất kỳ
liên lạc đợc với nhau và tổng đờng dây điện ngắn nhất .Đó là bài toán tìm cây khung
ngắn nhất . Ngợc lại : Xây dựng mạng dây điện thoại nối N thành phố sao cho 2 thành
phố bất kỳ liên lạc đợc với nhau và tổng độ tin cậy trên các đờng dây điện là lớn nhất
.Đó là bài toán tìm cây khung dài nhất .

- là
đỉnh vừa đợc kết nạp vào tập đỉnh ở bớc 3 - ta sửa lại nhãn của k theo nguyên tắc sau :
Gọi độ dài cung (i
0
,k ) là e
Nếu d > e thì đỉnh k có nhãn mới là k( i
0
, e )
Thí dụ :
File dữ liệu vào : PRIM.INT i
e=15
i
0Nhãn mới
k
(i
0
,15)
+) i
0
: vừa kết nạp vào Đ , k : không thuộc Đ

12
16 3 13 5
12 10

Var A : Array[1 Max,1 Max] of Byte;
D : Array[1 Max] of Boolean;
C : Array[0 Max] of record x1,x2 : Byte; end;
Nh : Array[1 Max] of record truoc,giatri : Byte; end;
N,dd,socanh : Byte;
{canh : Integer;}
{ }
Procedure DocF;
Var f : Text;
i,j : Byte;
Begin
Assign(f,fi);
Reset(f);
Readln(f,n);
For i:=1 to n do
Begin
For j:=1 to n do read(f,a[i,j]);
Readln(f);
End;
Close(f);
End;
{ }
Procedure Napdinh1;
_____________________________
PhÇn 3 : C©y - C©y khung ng¾n nhÊt TDH 9/7/2014 9/7/2014
50
Begin
Fillchar(d,sizeof(d),False);
d[1] := True;
dd := 1;

nh[xj].truoc := 0;
nh[xj].giatri:= 255;
End;
End;
End;
{ }
Procedure Ketnapthem;
Var p,j,xj : Byte;
Begin
p := 255;
For j:=1 to n do
If not d[j] then
Begin
If (nh[j].giatri<p) then
Begin
51
Tµi liÖu 11 Chuyªn Tin Hµ T©y
xj := j;
p := nh[j].giatri;
End;
End;
d[xj] := True;
Inc(socanh);
c[socanh].x1 := nh[xj].truoc;
c[socanh].x2 := xj;
dd := xj;
End;
{ }
Procedure Suanhan;
Var xj : Byte;

SoCanh := 0;
Fillchar(nh,sizeof(nh),0);
Napdinh1;
Gannhan;
Ok := False;
Repeat
_____________________________
PhÇn 3 : C©y - C©y khung ng¾n nhÊt TDH 9/7/2014 9/7/2014
52
Ketnapthem;
If Socanh=N-1 then Ok:= True
Else Suanhan;
Until Ok;
Hiencanh;
End;
{ }
BEGIN
Clrscr;
DocF;
TT_Prim
END.
PhÇn 4
T×m ®êng ®i ng¾n nhÊt
53