Bài giảng môn Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất
lượt xem 4
download
Bài giảng Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất, cung cấp cho người đọc những kiến thức như: Cây và các tính chất cơ bản của cây; Cây khung của đồ thị; Xây dựng tập các chu trình cơ bản của đồ thị; Xây dựng cây theo chiều sâu và chiều rộng; Bài toán cây khung nhỏ nhất. Mời các bạn cùng tham khảo!
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng môn Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất
- Chương 4 Bài toán cây khung nhỏ nhất The Minimum Spanning Tree Problem
- 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. Xây dựng cây theo chiều sâu và chiều rộng 4.5. 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: MĐ1: T là cây ( T liên thông và không chứa chu trình ). MĐ2: T không chứa chu trình và có n-1 cạnh. MĐ3: T liên thông và có n-1 cạnh. MĐ4: T liên thông và mỗi cạnh của nó đều là cầu. MĐ5: Hai đỉnh bất kỳcủa T được nối với nhau bởi đúng 1 đường đi đơn. MĐ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 1 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.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. Xây dựng cây theo chiều sâu và chiều rộng 4.5. 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 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 T1 T2 Đồ 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 a c c a b K3 Ba cây khung của K3 8
- methane H ethane H H C H H C H H H H C H propane H H C H H H C H H C H H C H H C H butane H C H H C H H H saturated hydrocarbons CnH2n+2 9
- Ví dụ: Các cây khung của đồ thị: abc, bcd, cda, dab, afc, dfb, aec, deb, aed, afb, bec, cfd, efc, efd, efa, efb. Số cây khung là: 42= 16 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.3. Xây dựng tập các chu trình cơ bản của đồ thị 4.4. Xây dựng cây theo chiều sâu và chiều rộng 4.5. Bài toán cây khung nhỏ nhất 11
- Tập các chu trình cơ bản Định nghĩa: Giả sử G=(V,E) là đơn đồ thị vô hướng hướng liên thông, H=(V,T) là cây khung của G. Nếu thêm một cạnh e ∈E\T vào cây khung H ta sẽ thu được đúng 1 chu trình trong H, ký hiệu n 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: Tập các chu trình cơ bản phụ thuộc vào cây khung của đồ thị. Hai cây khung khác nhau có thể cho hai tập chu trình cơ sở khác nhau. Nếu một đồ thị liên thông có n đỉnh, m cạnh. Khi đó cây khung có n-1 cạnh, còn lại m-n+1 cạnh ngoài. Tương ứng với mỗi cạnh ngoài, ta có một chu trình cơ bản. Vì vậy, số chu trình cơ bản của một đồ thị liên thông là m-n+1. Tập các chu trình cơ bản là một tập nhiều nhất các chu trình thỏa mãn điều kiện: Mỗi chu trình có đúng một cạnh riêng, cạnh đó không nằm trong các chu trình còn lại và việc loại bỏ cạnh này không ảnh hưởng đến tính liên thông của đồ thị và không ảnh hưởng đến các chu trình còn lại. Như vậy ta có thể bỏ tối đa m - n+1 cạnh mà vẫn đảm bảo tính liên thông của đồ thị. 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. 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. 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ậ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 >; 16 d := d-1; end;
- 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|) 17
- Ví dụ: 18
- Tập các chu trình cơ bản: 19
- 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. Xây dựng cây theo chiều sâu và chiều rộng 4.5. Bài toán cây khung nhỏ nhất 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Hóa lý: Chương 3 - GV. Nguyễn Trọng Tăng
161 p | 390 | 100
-
Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 4
0 p | 247 | 54
-
Bài giảng môn học Toán rời rạc - GV. Huỳnh Thị Thu Thủy
46 p | 223 | 25
-
ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: HC3CT-Lần 1-Đề 1
1 p | 166 | 21
-
Bài giảng môn học Toán học rời rạc
93 p | 115 | 18
-
Bài giảng Vật lý phân tử và nhiệt học - ĐH Phạm Văn Đồng
127 p | 135 | 17
-
ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: HC3CT-Lần 1-Đề 2
1 p | 156 | 15
-
Bài giảng môn Lý thuyết đồ thị
279 p | 91 | 14
-
Tóm tắt bài giảng môn Lý thuyết đồ thị
34 p | 196 | 13
-
ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: Học lại K4
1 p | 129 | 12
-
Bài giảng Lý thuyết đồ thị: Chương 0 - Giới thiệu môn học
12 p | 104 | 7
-
Bài giảng môn Xác suất thống kê - Nguyễn Thị Thu Thủy
146 p | 68 | 6
-
Bài giảng môn Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại
54 p | 10 | 4
-
Bài giảng Toán rời rạc: Chương 0 - ThS. Trần Quang Khải
18 p | 29 | 3
-
Bài giảng môn Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất
69 p | 10 | 3
-
Những vấn đề đặt ra trong đổi mới giảng dạy môn lý thuyết xác suất và thống kê ở các trường khối ngành kinh tế hiện nay
7 p | 31 | 2
-
Bàn về giảng dạy môn lý thuyết xác suất và thống kê ứng dụng
8 p | 35 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn