›
›

Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất - Nguyễn Đức Nghĩa

Download
Chương 4  
Bài toán cây khung nhỏ nhất  
The Minimum Spanning Tree Problem  
Nội dung  
4.1Cây và cátính chấcơ bản của cây  
4.2. Cây khung của đồ thị  
4.3. Xây dựng tập các chu trình cơ bản của đồ thị  
4.4. Bài toán cây khung nhỏ nhất  
2
Cây và rừng (Tree and Forest)  
§Þnh nghÜa 1. Ta gäi c©y lµ ®å thÞ v« híng liªn th«ng  
kh«ng cã chu tr×nh. §å thÞ kh«ng cã chu tr×nh ®îc gäi lµ  
rõng.  
Nh vËy, rõng lµ ®å thÞ mµ mçi thµnh phÇn liªn th«ng  
cña nã lµ mét c©y.  
T1  
T2  
T3  
Rừng F gồm 3 cây T1, T2,, T3  
3
VÍ DỤ  
G1, G2 là cây  
G3, G4 không là cây  
4
Các tính chất cơ bản của cây  
Định lý 1. Giả sử T=(V,E) là đồ thị vô hướng n đỉnh. Khi  
đó các mệnh đề sau đây là tương đương:  
(1) T là liên thông và không chứa chu trình;  
(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 nó đều là cầu;  
(5) Hai đỉnh bất kỳ của T được nối với nhau bởi  
đúng một đường đi đơn;  
(6) T 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.  
5
Nội dung  
4.1. Cây và các tính chất cơ bản của cây  
4.2Cây khung của đồ thị  
4.3. Xây dựng tập các chu trình cơ bản của đồ thị  
4.4. Bài toán cây khung nhỏ nhất  
6
Cây khung của đồ thị  
Định nghĩa 2. Giả sử G=(V,E) là đồ thị vô hướng liên  
thông. Cây T=(V,F) với FE được gọi là cây khung của  
đồ thị G.  
b
c
b
c
b
c
a
d
a
d
a
d
e
e
e
T2  
G
T1  
Đồ thị G và 2 cây khung T1 và T2 của nó  
7
Số lượng cây khung của đồ thị  
Định lý sau đây cho biết số lượng cây khung  
của đồ thị đầy đủ Kn:  
Định lý 2 (Cayley). Số cây khung của đồ thị  
Kn là nn-2 .  
Arthur Cayley  
(1821 – 1895)  
b
a
b
c
b
c
a
c
a
b
a
c
K3  
Ba cây khung của K3  
8
Bài toán trong hoá học hữu cơ  
Biểu diễn cấu trúc phân tử:  
Mỗi đỉnh tương ứng với một nguyên tử  
Cạnh – thể hiện liên kết giữa các nguyên tử  
Bài toán: Đếm số đồng phân của cacbua hydro no chứa  
một số nguyên tử cácbon cho trước  
9
H
H
C
methane  
ethane  
H
C
H
H
H
H
H
H
C
C
H
H
propane  
H
C
H
H
H
H
H
C
C
C
H
H
H
H
H
C
C
H
H
butane  
H
H
H
H
saturated hydrocarbons CnH2n+2  
10  
Nội dung  
4.1. Cây và các tính chất cơ bản của cây  
4.2. Cây khung của đồ thị  
4.3Xây dựng tập cáchu trình cơ bản của đồ thị  
4.4. Bài toán cây khung nhỏ nhất  
11  
Tập các chu trình cơ bản  
Gi¶ sö G = (V, E) lµ ®¬n ®å thÞ v« híng liªn th«ng,  
H=(V,T) lµ c©y khung cña nã. C¸c c¹nh cña ®å thÞ thuéc  
c©y khung ta sÏ gäi lµ c¸c c¹nh trong, cßn c¸c c¹nh cßn l¹i  
sÏ gäi lµ c¹nh ngoµi.  
§Þnh nghÜa 3. NÕu thªm mét c¹nh ngoµi e E \ T vµo c©y  
khung H chóng ta sÏ thu ®îc ®óng mét chu tr×nh trong H,  
ký hiÖu chu tr×nh nµy lµ Ce . TËp c¸c chu tr×nh  
= { Ce : e E \ T }  
®îc gäi lµ tËp c¸c chu tr×nh c¬ b¶n cña ®å thÞ G.  
12  
Tính chất  
Gi¶ sö A vµ B lµ hai tËp hîp, ta ®a vµo phÐp to¸n sau  
A B = (A B) \ (A B).  
TËp AB ®îc gäi lµ hiÖu ®èi xøng cña hai tËp A vµ B.  
Tªn gäi chu tr×nh c¬ b¶n g¾n liÒn víi sù kiÖn chØ ra trong  
®Þnh lý sau ®©y:  
§Þnh lý 3. Gi¶ sö G=(V,E) lµ ®å thÞ v« híng liªn th«ng,  
H=(V,T) lµ c©y khung cña nã. Khi ®ã mäi chu tr×nh cña  
®å thÞ G ®Òu cã thÓ biÓu diÔn nh lµ hiÖu ®èi xøng cña mét  
sè c¸c chu tr×nh c¬ b¶n.  
13  
Ý nghĩa ứng dụng  
Việc tìm tập các chu trình cơ bản giữ một vai trò  
quan trọng trong vấn đề giải tích mạng điện:  
⚫ Theo mỗi chu trình cơ bản của đồ thị tương  
ứng với mạng điện cần phân tích ta sẽ thiết lập  
được một phương trình tuyến tính theo định  
luật Kirchoff: Tổng hiệu điện thế dọc theo một  
mạch vòng là bằng không.  
⚫ Hệ thống phương trình tuyến tính thu được cho  
phép tính toán hiệu điện thế trên mọi đoạn  
đường dây của lưới điện.  
14  
Thuật toán xây dựng tập chu trình cơ bản  
Đầu vào: Đồ thị G=(V,E) ®îc m« t¶ b»ng danh s¸ch kÒ Ke(v), vV.  
procedure Cycle(v);  
(* Tìm tập các chu trình cơ bản của thành phần liên thông chứa đỉnh v  
C¸c biÕn d, num, STACK, Index lµ toµn côc *)  
begin  
d:=d+1;  
STACK[d] := v;  
num := num+1;  
Index[v] := num;  
for u Ke(v) do  
if Index[u]=0 then Cycle(u)  
else  
if (u STACK[d-1]) and (Index[v] > Index[u]) then  
< Ghi nhËn chu tr×nh víi c¸c ®Ønh:  
STACK[d], STACK[d-1], ... , STACK[c], víi STACK[c]=u >;  
d := d-1;  
end;  
15  
Thuật toán xây dựng tập chu trình cơ bản  
(* Main Program *)  
BEGIN  
for v V do Index[v] := 0;  
num := 0; d := 0;  
STACK[0] := 0;  
for v V do  
if Index[v] = 0 then Cycle(v);  
END.  
Độ phức tạp: O(|V|+|E|)  
16  
Nội dung  
4.1. Cây và các tính chất cơ bản của cây  
4.2. Cây khung của đồ thị  
4.3. Xây dựng tập các chu trình cơ bản của đồ thị  
4.4Bàtoán cây khung nhỏ nhất  
17  
BÀI TOÁN CÂY KHUNG NHỎ NHẤT  
Minimum Spanning Tree (MST)  
18  
Bài toá n CKNN  
Bài toán: Cho đồ thị vô hướng liên thông G=(V,E) với trọng số  
c(e), e E. Độ dài của cây khung là tổng trọng số trên các cạnh  
của nó. Cần tìm cây khung có độ dài nhỏ nhất.  
7
a
2
d
2
5
5
4
f
b
1
g
1
4
3
7
4
Độ dài của cây khung là  
Tổng độ dài các cạnh: 14  
c
e
19  
Bài toán cây khung nhỏ nhất  
Có thể phát biểu dưới dạng bài toán tối ưu tổ hợp:  
Tìm cực tiểu  
c(H) = c(e) → min,  
eT  
với điều kiện H=(V,T) là cây khung của G.  
Do số lượng cây khung của G là rất lớn (xem định lý  
Cayley), nên không thể giải nhờ duyệt toàn bộ  
20  
Tải về để xem bản đầy đủ
ppt 60 trang Thùy Anh 26/04/2022 8360
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 - Phần 2: Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất - Nguyễn Đức Nghĩa", để 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:

  • pptbai_giang_toan_roi_rac_phan_2_ly_thuyet_do_thi_chuong_4_bai.ppt