›
›

Bài giảng Toán rời rạc 2 - Chương 5: Cây và cây khung đồ thị

Download
CHꢀꢁNG 5. CÂY VÀ CÂY KHUNG Đꢂ THꢃ  
NꢄI DUNG:  
Định nghĩa và tính chất  
Xây dựng cây khung của đồ thị  
Bài toán tìm cây khung nhỏ nhất  
 
 
1
5.1 Đꢅnh nghĩa và các tính chất cꢆ bản  
1. Cây tự do  
- Cây tự do (không gốc) T là đồ thị vô hứng liên thông v̀ không ć chu tr̀nh đơn.  
- Đồ thị F là một rừng mỗi thành phần liên thông của F là một cây.  
- Đồ thị F là một rừng F không có chu trình đơn.  
2
Cây tự do (không gốc)  
3
Đꢅnh lý 1:  
T= (V, E) là một đồ thị vô hứng có n đỉnh.  
Các mệnh đề sau là tương đương:  
(1) T là cây;  
(2) T không chứa chu trình và có n-1 cạnh;  
(3) T liên thông và có n-1 cạnh;  
(4) T liên thông và mỗi cạnh của T là cầu ;  
(5) Hai đỉnh bất kỳ của T có duy nhất một đường đi nối đến nhau ;  
(6) T không chứa chu trình nhưng nếu thêm 1 cạnh thì thu được đúng 1 chu trình.  
4
2. Cây có gꢇc  
Đꢅnh nghĩa 1: Cây là tập hợp hữu hạn các nút thỏa mãn:  
- Có một nút gọi là gốc  
- Có quan hệ phân cấp “cha-con” giữa các nút.  
Đꢅnh nghĩa 2 (đệ qui): - Nếu T chỉ gồm 1 nút T là một cây v́i gốc l̀ chính nút đ́  
- Nếu T1, …, Tn (n 1) là các cây có gốc tương ứng r1, …, rn T là cây v́i gốc r được tạo thành  
bằng cách cho r thành nút cha của các nút r1, …, rn.  
5
Các mức của cây  
Cây có gốc tam phân  
Các ví dụ về cây:  
- Mục lục của một cuốn sách  
- Cấu trúc thư mục trên đĩa máy tính.  
- Dùng cây để biểu diễn biểu thức số học.  
6
Mꢈt sꢇ khái niệm:  
- Nút gꢇc: là nút của cây T không có cha.  
- Nút cha: Nút r là cha của các nút r1, ..., rn Nút gốc là nút không có nút cha.  
- Nút con: Các nút r1, …, rn gọi là nút con của r  
- Bậc của mꢈt nút: là số các nút con của nút đ́.  
- Bậc của mꢈt cây T: là bậc ĺn nhất của các nút T. T có bậc m T gọi là cây m-phân.  
Nút lá: l̀ nút ć bậc = 0 nút lá không có nút con.  
Nút nhánh (nút trong hay nút trung gian): l̀ nút vừa ć con vừa ć cha.  
T là cây m-phơn đầy đủ mỗi nút nhánh ć đúng m con.  
7
- Cây con: Mꢉi cây có gꢇc tại nút a T là mꢈt cây con của T.  
- Đꢊờng đi: Dãy các đỉnh r1, …, rk, trong đ́ ri là cha của ri+1 gọi l̀ đường đi từ r1 đến rk. Độ dài  
của đường đi l̀ số nút trên đường đi -1 (Đường đi trên ć độ dài k-1).  
- Mức của nút: l̀ độ d̀i đường đi từ gốc đến nút (độ cao của nút) Nút gốc có mức 0.  
- Chiều cao của cây: là mức ĺn nhất của các nút T.  
- Cơy đꢊợc sắp thứ tự: là cây mà mỗi cây con được sắp theo một thứ tự ǹo đ́.  
- Cây gán nhãn: là cây mà mỗi đỉnh được gắn v́i một giá trị (nhãn).  
Cây nhꢅ phân:  
Cây nhị phân là cây mà mỗi nút có không quá 2 con. Phân biệt cây con bên trái và cây con bên  
phải.  
8
3. Đꢅnh nghĩa cơy khung  
Đꢅnh nghĩa 1. Cho G l̀ một đơn đồ thị.  
Một cây T gọi l̀ cây khung của G T l̀ đồ thị con của G v̀ chứa tất cả các đỉnh của G.  
Một cây khung T của G  
Đồ thị G  
9
Đꢅnh ĺ 2. Một đơn đồ thị l̀ liên thông nếu v̀ chỉ nếu ń ć cây khung.  
Ch́ng minh. Giả s̉ đồ thị G ć cây khung T chứa tất cả các đỉnh của G và ć đường đi trong T  
giữa hai đỉnh bất kỳ ć đường đi trong G giữa hai đỉnh bất kỳ của ń G l̀ liên thông.  
Giả s̉ G l̀ liên thông. Nếu G không phải l̀ cây th̀ G ć chu tr̀nh đơn. X́a đi một cạnh trong  
các chu tr̀nh đơn ǹy. Đồ thị nhận được chứa một số cạnh ít hơn nhưng ṽn c̀n chứa tất cả các  
đỉnh của G v̀ liên thông. Nếu đồ thị con ǹy không phải l̀ cây th̀ ń chứa chu tr̀nh đơn. C̃ng  
giống như trên, x́a đi một cạnh của chu tr̀nh đơn. Ḷp lại quá tr̀nh ǹy cho đến khi không c̀n  
chu tr̀nh đơn. Điều ǹy ć thể v̀ chỉ ć hữu hạn cạnh trong đồ thị. Đồ thị con cuối cùng sau khi  
x́a đi các cạnh của các chu tr̀nh l̀ cây khung.  
10  
5.2 Bài toán tìm cây khung  
1) Đặt bƠi toán:  
Input: Đồ thị G gồm n đỉnh cho bởi danh sách kề; Đỉnh u;  
Output: Cây khung T của G bắt đầu từ đỉnh u;  
11  
2. Xơy dựng cây khung bằng thuật toán DFS  
Thuật toán TreeDfs(u):  
- Tạo cây T bằng thuật toán DFS bắt đầu từ đỉnh u;  
- Nếu số đỉnh của T bằng n th̀ xuất kết quả T;  
- Nếu số đỉnh của T nhỏ hơn n th̀ xuất thông báo: Không có cây khung.;  
Đꢈ phức tạp tính toán: Giải thuật t̀m cây khung ć độ phức tạp O(n).  
12  
Ví dụ: T̀m cây khung của đồ thị G cho dứi đây:  
- Tìm kiếm theo chiều sâu bắt đầu từ 1:  
T = {(1, 3), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 11), (8, 10)}.  
- Tìm kiếm theo chiều rộng bắt đầu từ 1:  
T = {(1, 3), (2, 3), (3,4), (4, 5), (4, 6), (6, 7), (6, 8), (8, 9), (8, 10), (9, 11)}.  
Ghi chú: - Cây khung T tìm kiếm theo chiều rộng bắt đầu từ 1 gồm các đường đi ngắn nhất xuất  
phát từ 1 đến các đỉnh khác.  
- Đồ thị đầy đủ Kn có nn-2 cây khung khác nhau.  
13  
3. Xơy dựng cây khung bằng thuật toán BFS  
Thuật toán TreeBfs(u):  
- Tạo cây T bằng thuật toán BFS bắt đầu từ đỉnh 1.  
- Nếu số đỉnh của T bằng n th̀ xuất kết quả T.  
- Nếu số đỉnh của T nhỏ hơn n th̀ xuất thông báo: Không ć cây khung.  
Đꢈ phức tạp tính toán: Giải thuật t̀m cây khung ć độ phức tạp O(n).  
14  
5.3 BƠi toán tìm cơy khung nhỏ nhất  
1. Cơy khung nhỏ nhất  
Cho đồ thị vô hứng ć trọng số G = (V, E).  
Gọi T l̀ một câu khung của G. Trọng số WT của T l̀ t̉ng trọng số các cạnh thuộc cây.  
Cây khung T là cây khung nh̉ nh́t WT có giá trị nhỏ nhất.  
2. Điều kiện:  
G ć cây khung nhỏ nhất G liên thông;  
15  
3. Thuật toán tìm cơy khung nhỏ nhất:  
Thuật toán 1. Thuật toán Prim  
Input: Đồ thị G = (V, E) gồm n đỉnh cho bởi ma trận trọng số a[i][j];  
Đỉnh s G;  
Output: Cây khung nhỏ nhất T v̀ WT;  
Khởi tạo: T= ; VT = {s}; WT= 0;  
while (V\VT ≠) {  
<Tìm e = (u, v) ć trọng số nhỏ nhất, u VT, v V\VT>;  
if (T̀m được e) {T = T e;  
WT= WT + trọng số của e;  
VT = VT {v};  
}
else return (G không có cây khung); }  
return (T và WT);  
16  
Ví dụ 1. Dùng thuật toán Prim, hãy t̀m cây khung nhỏ nhất của đồ thị G bắt đầu từ s = b;  
Gỉi.  
Khởi tạo T = ; VT = {b}; WT = 0;  
Cây khung nhỏ nhất được xây dựng bằng thuật toán Prim được thể hiện ở bảng sau:  
17  
Bꢊ́c cḥn  
Cạnh đꢊợc cḥn  
Tṛng sꢇ  
WT  
1
1
2
b,f  
a,b  
f,j  
1
2
2
3
3
2
1
3
3
3
1
3
3
5
4
a,e  
f,g  
c,g  
c,d  
g,h  
h,l  
i,j  
8
5
11  
13  
14  
17  
20  
23  
24  
6
7
8
9
10  
11  
k,l  
Kết luận: T = { (b,f), (a,b), (f,j), (a,e), (f,g), (c,g), (c,d), (g,h), (i,j). (h,l), (k,l) }  
WT = 24  
18  
CƠi đặt:  
int n, a[100][100], s;  
if (v==0)  
{cout << “Khong co cay khung”; return;}  
int vt[100], d[100], t[100];  
void Prim()  
vt[v]= 1; wt= wt + a[v][t[v]];  
for (i= 1; i<= n; i++)  
if (vt[i]==0 && d[i]) > a[v][i])  
{d[i]= a[v][i]; t[i]= v; }  
}
{for (int i= 1; i<= n, i++)  
{vt[i]= 0; d[i]= a[s][i]; t[i]= s};  
vt[s]= 1; d[s]= 0; t[s]= 0;  
int wt= 0;  
int m = 1;  
cout << wt << endl;  
while (m < n) { int v = 0;  
int min = 30000;  
for (i= 1; i<= n; i++)  
if (t[i] !=0) cout << i << “ “ << t[i] << endl;  
return;  
for (i = 1; i<= n; i++)  
if (vt[i]==0 && d[i] < min) {min= d[i]; v= i;} }  
19  
Chứng minh tính đúng đắn của thuật toán Prim:  
Xét G l̀ đồ thị liên thông ć trọng số.  
Giả s̉ các cạnh lần lượt được chọn theo thuật toán Prim l̀ e1, e2,..., en-1.  
Gọi S l̀ cây v́i các cạnh e1, e2,..., en-1;  
Sk l̀ cây v́i các cạnh e1, e2,..., ek;  
T l̀ cây khung nhỏ nhất của G ć chứa các cạnh e1, e2,..., ek.  
Giả s̉ k l̀ số nguyên ĺn nhất thỏa mãn điều kiện trên.  
Định ĺ được chứng minh nếu ta chỉ ra rằng S = T.  
Giả s̉ S T, v́i k < n-1 T chứa e1, e2,..., ek nhưng không chứa ek+1.  
X́t đồ thị T’ = Tek+1. T’ liên thông v̀ ć n cạnh T’ ć một chu tr̀nh đơn.  
Chu tr̀nh chứa ek+1 v̀ trong T không ć chu tr̀nh.  
Chu tr̀nh phải ć một cạnh không thuộc Sk+1 v̀ Sk+1 l̀ cây.  
20  
Tải về để xem bản đầy đủ
pdf 25 trang myanh 20260 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 2 - Chương 5: Cây và cây khung đồ thị", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_toan_roi_rac_2_chuong_5_cay_va_cay_khung_do_thi.pdf