Bài giảng Toán rời rạc 2 - Chương 5: Cây và Cây khung của đồ thị - Ngô Xuân Bách
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 2
Cây và Cây khung của đồ thị
Ngô Xuân Bách
Nội dung
Cây và các tính chất của cây
Cây khung của đồ thị
Bài toán cây khung nhỏ nhất
2
Định nghĩa và ví dụ
Định nghĩa 1: Ta gọi cây là một đồ thị vô hướng, liên
thông, không có chu trình
Định nghĩa 2: Ta gọi rừng là một đồ thị vô hướng,
không có chu trình
o Như vậy rừng là một đồ thị mà mỗi thành phần liên thông của nó
là một cây
Ví dụ: một rừng có 3 cây
(Phương ND, 2013)
3
Các tính chất của cây
Định lý: Giả sử 푇 =< 푉, 퐸 > là đồ thị vô hướng 푛 đỉnh,
khi đó những khẳng định sau là tương đương:
1) 푇 là một cây
2) 푇 không có chu trình và có 푛 − 1 cạnh
3) 푇 liên thông và có đúng 푛 − 1 cạnh
4) 푇 liên thông và mỗi cạnh của nó đều là cầu
5) Giữa hai đỉnh bất kỳ của 푇 được nối với nhau bởi đúng một
đường đi đơn
6) 푇 không chứa chu trình nhưng hễ cứ thêm vào nó một cạnh ta
thu được đúng một chu trình
Chứng minh: Theo sơ đồ
(1) ⇒ (2) ⇒ (3) ⇒ (4) ⇒ (5) ⇒ (6) ⇒ (1)
4
Nội dung
Cây và các tính chất của cây
Cây khung của đồ thị
Bài toán cây khung nhỏ nhất
5
Định nghĩa và ví dụ
Định nghĩa 3: Cho 퐺 là đồ thị vô hướng liên thông. Ta
gọi đồ thị con 푇 của 퐺 là một cây khung của 퐺 (Cây bao
trùm) nếu 푇 thoả mãn hai điều kiện:
o 푇 là một cây
o Tập đỉnh của 푇 bằng tập đỉnh của 퐺
Ví dụ:
6
Xây dựng cây khung của đồ thị
Bài toán: Cho đồ thị vô hướng 퐺 =< 푉, 퐸 >. Hãy xây
dựng một cây khung của đồ thị bắt đầu tại đỉnh 푢 ∈ 푉.
Cách làm
o Sử dụng thuật toán duyệt DFS hoặc BFS
o Mỗi khi ta đến được đỉnh 푣 tức (푐ℎ푢푎푥푒푡,푣- = 푡푟푢푒) từ đỉnh 푢 thì
cạnh (푢, 푣) được kết nạp vào cây khung
7
Xây dựng cây khung của đồ thị
sử dụng thuật toán DFS (1/2)
Thuật toán tạo cây khung từ một đỉnh 풖
Tree-DFS(푢){
cℎ푢푎푥푒푡,푢- = 푓푎푙푠푒; //đánh dấu đỉnh 푢 đã duyệt
for(푣 ∈ 퐾푒(푢)){
if( 푐ℎ푢푎푥푒푡,푣-){ //nếu 푣 chưa được duyệt
푇 = 푇 ∪ * 푢, 푣 +; //hợp cạnh (u, 푣) vào cây khung
Tree-DFS(푣); //duyệt theo chiều sâu từ 푣
}
}
}
8
Xây dựng cây khung của đồ thị
sử dụng thuật toán DFS (2/2)
Thuật toán xây dựng cây khung
Tree-Graph-DFS( ){
//Khởi tạo các đỉnh đều chưa xét
for(푢 ∈ 푉)
cℎ푢푎푥푒푡,푢- = 푡푟푢푒;
푟표표푡 = < đỉ푛ℎ 푏ấ푡 푘ỳ 푐ủ푎 đồ 푡ℎị >; //Lấy một đỉnh bất kỳ làm gốc
푇 = ∅; //Cây ban đầu chưa có cạnh nào
Tree-DFS(root); //Gọi thuật toán tạo cây khung từ một đỉnh
if( 푇 < 푛 − 1)
<đồ thị không liên thông>;
else
<ghi nhận tập cạnh của cây khung 푇>;
}
9
Kiểm nghiệm thuật toán (1/2)
Cho đồ thị vô hướng
được biểu diễn bằng ma
trận kề như hình bên.
Áp dụng thuật toán xây
dựng cây khung của đồ
thị sử dụng DFS cho đồ
thị trên bắt đầu từ đỉnh
푢 = 1.
(Phương ND, 2013)
10
Kiểm nghiệm thuật toán (2/2)
Bước Ngăn xếp đỉnh theo thứ tự gọiTree-DFS(u)
푻
0 1
푇 = ∅
1 1, 2
2 1, 2, 3
3 1, 2, 3, 4
푇 = 푇 ∪ *(1,2)+
푇 = 푇 ∪ *(2,3)+
푇 = 푇 ∪ *(3,4)+
4 1, 2, 3
5 1, 2, 3, 5
6 1, 2, 3, 5, 6
푇 = 푇 ∪ *(3,5)+
푇 = 푇 ∪ *(5,6)+
푇 = 푇 ∪ *(6,7)+
푇 = 푇 ∪ *(7,8)+
푇 = 푇 ∪ *(8,9)+
푇 = 푇 ∪ *(9,10)+
푇 = 푇 ∪ *(10,11)+
푇 = 푇 ∪ *(11,12)+
푇 = 푇 ∪ *(12,13)+
7 1, 2, 3, 5, 6, 7
8 1, 2, 3, 5, 6, 7, 8
9 1, 2, 3, 5, 6, 7, 8, 9
10 1, 2, 3, 5, 6, 7, 8, 9, 10
11 1, 2, 3, 5, 6, 7, 8, 9, 10, 11
12 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12
13 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13
Không thêm được cạnh nào nữa vào 푇
푇 = * 1,2 , 2,3 , 3,4 , 3,5 , 5,6 , 6,7 , 7,8 , 8,9 ,
9,10 , 10,11 , (11,12, (12,13))+
11
Xây dựng cây khung của đồ thị
sử dụng thuật toán BFS
Tree-BFS(푢){
Bước 1: Khởi tạo
T = ∅; 푞푢푒푢푒 = ∅; p푢푠ℎ(푞푢푒푢푒, 푢); 푐ℎ푢푎푥푒푡,푢- = 푓푎푙푠푒;
Bước 2: Lặp
while(푞푢푒푢푒 ≠ ∅){
푠 = p표푝(푞푢푒푢푒);
for(푡 ∈ 퐾푒(푠)){
if( 푐ℎ푢푎푥푒푡,푡-){
p푢푠ℎ(푞푢푒푢푒, 푡);
T = T ∪ * 푠, 푡 +;
푐ℎ푢푎푥푒푡,푡- = 푓푎푙푠푒;
}
}
}
Bước 3: Trả lại kết quả
if( 푇 < 푛 − 1) <đồ thị không liên thông>;
else <ghi nhận tập cạnh của cây khung 푇>;
}
12
Kiểm nghiệm thuật toán (1/2)
Cho đồ thị vô hướng
được biểu diễn bằng ma
trận kề như hình bên.
Áp dụng thuật toán xây
dựng cây khung của đồ
thị sử dụng BFS cho đồ
thị trên bắt đầu từ đỉnh
푢 = 1.
(Phương ND, 2013)
13
Kiểm nghiệm thuật toán (2/2)
Bước Trạng thái hàng đợi
푻
0 1
푇 = ∅
1 2, 3, 4
2 3, 4
3 4, 5
4 5
푇 = 푇 ∪ * 1,2 , 1,3 , (1,4)+
푇 = 푇 ∪ *(3,5)+
5 6, 7, 8, 9
6 7, 8, 9
7 8, 9
8 9
푇 = 푇 ∪ * 5,6 , 5,7 , 5,8 , (5,9)+
9 10
푇 = 푇 ∪ *(9,10)+
10 11, 12, 13
11 12, 13
12 13
푇 = 푇 ∪ * 10,11 , 10,12 , (10,13)+
13 ∅
푇 = * 1,2 , 1,3 , 1,4 , 3,5 , 5,6 , 5,7 , 5,8 , 5,9 ,
9,10 , 10,11 , (10,12, (10,13))+
14
Nội dung
Cây và các tính chất của cây
Cây khung của đồ thị
Bài toán cây khung nhỏ nhất
15
Phát biểu bài toán
Cho 퐺 =< 푉, 퐸 > là đồ thị vô hướng liên thông với tập
đỉnh 푉 và tập cạnh 퐸. Mỗi cạnh 푒 của đồ thị được gán
với một số không âm 푐(푒) được gọi là độ dài cạnh.
Giả sử 퐻 =< 푉, 푇 > là một cây khung của đồ thị 퐺. Ta gọi
độ dài 푐(퐻) của cây khung 퐻 là tổng độ dài các cạnh:
푐 퐻 = 푒∈푇 푐(푒)
Bài toán: Trong số các cây khung của đồ thị hãy tìm cây
khung có độ dài nhỏ nhất.
16
Ví dụ
Bài toán nối mạng máy tính
o Một mạng máy tính gồm 푛 máy tính được đánh số từ 1, 2, . . . , 푛.
Biết chi phí nối máy 푖 với máy 푗 là 푐,푖, 푗-, 푖, 푗 = 1, 2, . . . , 푛. Hãy tìm
cách nối mạng sao cho chi phí là nhỏ nhất.
Bài toán xây dựng hệ thống cáp
o Giả sử ta muốn xây dựng một hệ thống cáp điện thoại nối 푛 điểm
của một mạng viễn thông sao cho điểm bất kỳ nào trong mạng
đều có đường truyền tin tới các điểm khác. Biết chi phí xây dựng
hệ thống cáp từ điểm 푖 đến điểm 푗 là 푐,푖, 푗-. Hãy tìm cách xây
dựng hệ thống mạng cáp sao cho chi phí là nhỏ nhất.
17
Thuật toán Kruskal (1/2)
Thêm dần từng cạnh vào cây khung
Mỗi bước chọn cạnh có trọng số nhỏ nhất chưa nằm
trong cây khung
o Nếu việc thêm cạnh này vào cây khung không tạo thành chu trình
thì thêm cạnh này vào
Thuật toán dừng lại khi
o Cây khung có đủ (푛 − 1) cạnh,
o Hoặc không còn cạnh nào chưa nằm trong cây khung
18
Thuật toán Kruskal (2/2)
Kruskal( ){
Bước 1 (khởi tạo):
푇 = ∅; //Ban đầu tập cạnh cây khung là rỗng
푑 퐻 = 0; //Ban đầu độ dài cây khung là 0
Bước 2 (sắp xếp):
<sắp xếp các cạnh đồ thị theo thứ tự tăng dần của trọng số>;
Bước 3 (lặp):
while(|푇| < 푛 − 1 && 퐸 ≠ ∅ ){
푒 = <Cạnh có độ dài nhỏ nhất>;
퐸 = 퐸\*푒+; //Loại cạnh 푒 ra khỏi tập cạnh
if (푇 ∪ *푒+ không tạo nên chu trình ){
T = 푇 ∪ *푒+; //Đưa 푒 vào cây khung
푑 퐻 = 푑 퐻 + 푑(푒); //cập nhật độ dài cây khung
}
}
Bước 4 (trả lại kết quả):
if(|푇| < 푛 − 1) <Đồ thị không liên thông>;
else return (T, d(H));
}
19
Kiểm nghiệm thuật toán
Áp dụng thuật toán
Kruskal tìm cây
khung nhỏ nhất cho
đồ thị được biểu
diễn bằng ma trận
trọng số như hình
bên ?
(Phương ND, 2013)
20
Tải về để xem bản đầy đủ
25 trang
27081
Free
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 của đồ thị - Ngô Xuân Bách", để 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:
- bai_giang_toan_roi_rac_2_chuong_5_cay_va_cay_khung_cua_do_th.pdf
