Tài liệu HSG Pascal Phần 3

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 .

III / Thuật toán Prim tìm cây khung nhỏ nhất :

Bước 1 : Khởi trị - Lấy 1 đỉnh i tuỳ ý đưa vào tập đỉnh của cây . Khi đó tập đỉnh của cây là Đ = {i }. Tập cạnh của cây là C = ( ( Tập rỗng )
Bước 2 : Gán nhãn - Với mỗi đỉnh k không thuộc Đ , ta gán cho nó nhãn k(i ,d ) trong đó i là tên đỉnh thuộc Đ ,kề với k , gần k nhất , còn d là khoảng cách giữa i và k . Nếu trong Đ không tìm được đỉnh i kề với k thì gán cho k nhãn k( 0 ,( ) .

Bước 3 : Kết nap - Chọn đỉnh k không thuộc tập Đ , có nhãn d nhỏ nhất , kết nạp k vào Đ .Vậy Đ = Đ + { k } . Nhãn của k là k( i ,d ) thì kết nạp cạnh ( i , k ) vào tập cạnh C . Vậy C = C + { cạnh ( i , k ) } . Gọi đỉnh k vừa kết nạp là i0 .
Nếu số đỉnh của Đ bằng N thì kết thúc , còn không chuyển sang bước 4

Bước 4 : Sửa nhãn - Với mọi đỉnh k chưa thuộc Đ có