第 2 页
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.4. Bài toán cây khung nhỏ nhất 2
资料内容
第 3 页
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 T 2 T3 Rừng F gồm 3 cây T1, T2,, T3 3
第 5 页
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
第 6 页
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.4. Bài toán cây khung nhỏ nhất 6
第 7 页
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 F E đượ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 G T T2 1 Đồ thị G và 2 cây khung T1 và T2 của nó 7
第 8 页
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 a c c a b K3 Ba cây khung của K3 8
第 9 页
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
第 10 页
methane H ethane H H C H H C H H H propane H C H H H C H H H C H H C H H C H butane H C H H C H H H C H H saturated hydrocarbons CnH2n+2 10
第 11 页
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.4. Bài toán cây khung nhỏ nhất 11
第 12 页
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
第 13 页
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
第 14 页
Ý 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
第 15 页
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
第 16 页
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
第 17 页
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.4. Bài toán cây khung nhỏ nhất 17
第 19 页
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. a 7 2 d 2 5 f 5 4 b 1 g 4 1 3 7 c 4 e Độ dài của cây khung là Tổng độ dài các cạnh: 14 19
第 20 页
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
显示前 20 页。下载资料查看完整内容。
评论 (0)
暂无评论。快来抢沙发吧！