Bài giảng Toán rời rạc ứng dụng trong tin học

Nội dung text: Bài giảng Toán rời rạc ứng dụng trong tin học

1. TỐN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC KHÁI NIỆM CƠ BẢN VỀ CÂY 1
2. Một số khái niệm cơ bản ⚫ Cây ⚫ Định nghĩa: ⚫ Cây là một đồ thị vơ hướng, liên thơng và khơng cĩ chu trình sơ cấp ▪ Cây khơng cĩ cạnh bội và khuyên ▪ Cây là một đơn đồ thị ⚫ Ví dụ G G G 1 2 G3 G4 Chương 2. Cây 2
3. Một số khái niệm cơ bản ⚫ Rừng ⚫ Định nghĩa: ⚫ Rừng là một đồ thị vơ hướng và khơng cĩ chu trình ▪ Rừng cĩ thể cĩ nhiều thành phần liên thơng ▪ Mỗi thành phần liên thơng là một cây ⚫ Ví dụ G Chương 2. Cây 3
4. Một số khái niệm cơ bản ⚫ Định lý (Điều kiện đủ của cây) ⚫ Nếu mọi cặp đỉnh của một đồ thị vơ hướng G luơn tồn tại một đường đi sơ cấp thì G là một cây ⚫ Chứng minh ⚫ SV tham khảo tài liệu Chương 2. Cây 4
5. Một số khái niệm cơ bản ⚫ Cây cĩ gốc ⚫ Định nghĩa ⚫ Một cây với một đỉnh được chọn làm gốc ⚫ Định hướng các cạnh trên cây từ gốc đi ra ⚫ Ví dụ a d e a f b b e g d f b e c c a c h d f g h g h ▪ Cùng một cây, nếu chọn gốc khác nhau thì cây cĩ gốc thu được sẽ khác nhau Chương 2. Cây 5
6. Một số khái niệm cơ bản ⚫ Cây cĩ gốc ⚫ Một số khái niệm ⚫ Cha ⚫ Lá ⚫ Anh em ⚫ Đỉnh trong ⚫ Tổ tiên ⚫ Cây con ⚫ Con cháu ⚫ Mức ⚫ Chiều cao Chương 2. Cây 6
7. Một số khái niệm cơ bản ⚫ Định lý Daisy Chain T là đồ thị cĩ n đỉnh. Các mệnh đề tương đương: 1. T là một cây 2. T khơng cĩ chu trình và cĩ n-1 cạnh 3. T liên thơng, mọi cạnh đều là cầu 4. Giữa hai đỉnh bất kỳ của T luơn tồn tại một đường đi sơ cấp duy nhất 5. T khơng cĩ chu trình và T U {e} cĩ chu trình 6. T liên thơng và cĩ n-1 cạnh Chương 2. Cây 7
8. Một số khái niệm cơ bản ⚫ Cây m-phân ⚫ Định nghĩa ⚫ Cây m-phân ▪ Cây cĩ gốc ▪ Tất cả các đỉnh trong cĩ khơng quá m con ⚫ Cây m-phân đầy đủ ▪ Tất cả các đỉnh trong cĩ khơng quá m con ⚫ m=2: Cây nhị phân Chương 2. Cây 8
9. Một số khái niệm cơ bản ⚫ Cây m-phân ⚫ Ví dụ T T1 2 T3 ⚫ T1: Cây nhị phân đầy đủ ⚫ T2: Cây tam phân đầy đủ ⚫ T3: Cây tứ phân (khơng đầy đủ) Chương 2. Cây 9
10. Một số tính chất của cây ⚫ Tính chất 1 ⚫ Cây n đỉnh (n 2) cĩ ít nhất 2 đỉnh treo ⚫ Tính chất 2 ⚫ Cây m-phân đầy đủ với i đỉnh trong cĩ n = m.i + 1 ⚫ Tính chất 3 ⚫ i = (n -1)/m ⚫ l = [(m - 1)n + 1] / m ⚫ l = (m - 1)i + 1 ⚫ n = l + i Chương 2. Cây 10
11. Phép duyệt Cây nhị phân ⚫ Định nghĩa ⚫ Duyệt cây ⚫ Liệt kê các đỉnh theo một thứ tự xác định, mỗi đỉnh một lần ⚫ Thường được đỉnh nghĩa đệ quy cho các cây con ⚫ 3 phương pháp duyệt cây ⚫ Duyệt tiền tự (Pre-Oder) ⚫ Duyệt trung tự (In-Oder) ⚫ Duyệt hậu tự (Post-Oder) Chương 2. Cây 11
12. Phép duyệt Cây nhị phân ⚫ Định nghĩa ⚫ Duyệt tiền tự 1. Duyệt nút gốc 2. Duyệt tiền tự con trái 3. Duyệt tiền tự con phải 1 2 3 Chương 2. Cây 12
13. Phép duyệt Cây nhị phân ⚫ Định nghĩa ⚫ Duyệt trung tự 1. Duyệt trung tự con trái 2. Duyệt nút gốc 3. Duyệt trung tự con phải 2 1 3 Chương 2. Cây 13
14. Phép duyệt Cây nhị phân ⚫ Định nghĩa ⚫ Duyệt hậu tự 1. Duyệt hậu tự con trái 2. Duyệt hậu tự con phải 3. Duyệt nút gốc 3 1 2 Chương 2. Cây 14
15. Phép duyệt Cây nhị phân ⚫ Định nghĩa ⚫ Ví dụ A ⚫ Duyệt tiền tự ▪ A B D E C F B C ⚫ Duyệt trung tự ▪ E F D B E A C F D ⚫ Duyệt hậu tự ▪ D E B F C A Chương 2. Cây 15
16. Ký pháp nghịch đảo Ba Lan ⚫ Cây biểu thức số học ⚫ Là cây nhị phân ⚫ Mỗi nút trong biểu diễn cho tốn tử 2 ngơi  ▪ Biểu diễn cho biểu thức E1  E2 ▪ Con trái biểu diễn cho biểu thức E1 ▪ Con phải biểu diễn cho biểu thức E2 ⚫ Mỗi nút lá biểu diễn cho một tốn hạng Chương 2. Cây 16
17. Ký pháp nghịch đảo Ba Lan ⚫ Cây biểu thức số học ⚫ Ví dụ E = (2 + 3)*2 – (4 – 1)*(15/5) Chương 2. Cây 17
18. Ký pháp nghịch đảo Ba Lan ⚫ Cây biểu thức số học ⚫ Duyệt cây biểu thức ⚫ Biểu thức tiền tố ⚫ Biểu thức trung tố ⚫ Biểu thức hậu tơ Chương 2. Cây 18
19. Ký pháp nghịch đảo Ba Lan ⚫ Cây biểu thức số học ⚫ Ký pháp nghịch đảo Ba Lan (Reverse Polish Notation – RPN) ⚫ Biểu thức ở dạng hậu tố ▪ Ví dụ: 5 1 2 + 4 * + 3 – ⚫ Sử dụng để tính giá trị biểu thức trên máy tính ▪ Tính từ trái qua phải ▪ Khơng sử dụng dấu ngoặc ▪ Sử dụng Stack (ngăn xếp) Chương 2. Cây 19
20. Ký pháp nghịch đảo Ba Lan ⚫ Cây biểu thức số học ⚫ Ký pháp nghịch đảo Ba Lan (Reverse Polish Notation – RPN) ⚫ Thuật tốn tính giá trị biểu thức RPN ▪ Đọc một ký hiệu (token) ▪ Nếu ký hiệu là một số ▪ Đẩy vào Stack ▪ Ngược lại, ký hiệu là một tốn tử ▪ Lấy ra 2 tốn hạng từ Stack ▪ Tính giá trị theo tốn tử đối với 2 tốn hạng ▪ Đẩy kết quả vào Stack Chương 2. Cây 20
21. Ký pháp nghịch đảo Ba Lan ⚫ Cây biểu thức số học ⚫ Ký pháp nghịch đảo Ba Lan (Reverse Polish Notation – RPN) ⚫ Ví dụ: Tính giá trị biểu thức 5 1 2 + 4 * + 3 - Chương 2. Cây 21
22. Cây khung (Spanning Tree) ⚫ Định nghĩa ⚫ Cây khung của đơn đồ thị G ⚫ Đồ thị con của G ⚫ Chứa tất cả các đỉnh của G ⚫ Một đồ thị cĩ thể cĩ nhiều cây khung ⚫ Ví dụ Chương 2. Cây 22
23. Cây khung (Spanning Tree) ⚫ Định lý ⚫ Một đơn đồ thị là liên thơng khi và chỉ khi nĩ cĩ cây khung ⚫ Chứng minh Đơn giản Chương 2. Cây 23
24. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Định nghĩa ⚫ Cây khung nhỏ nhất trong một đồ thị liên thơng, cĩ trọng số là một cây khung cĩ tổng trọng số trên các cạnh là nhỏ nhất ⚫ Định lý ⚫ Cho G = (V, E), X  V ⚫ e là cạnh cĩ trọng số nhỏ nhất nối giữa X và V\X. e là một cạnh trong cây khung nhỏ nhất. Chương 2. Cây 24
25. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Thuật tốn Prim ⚫ Phân hoạch tập đỉnh ▪ Tập các đỉnh thuộc cây đang xây dựng ▪ Tập các đỉnh cịn lại ⚫ Xây dựng cây ▪ Chọn một đỉnh chưa thuộc cây mà cĩ khoảng cách gần cây đang xây dựng nhất ▪ Ghép vào cây cạnh ngắn nhất tìm được ▪ Thuật tốn dừng khi được n-1 cạnh Chương 2. Cây 25
26. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Thuật tốn Prim ⚫ Cho T là tập đỉnh gồm một đỉnh x ⚫ Trong khi T cĩ ít hơn n đỉnh, thực hiện việc sau ▪ Tìm đỉnh u trong V \ T mà gần với T nhất ▪ thêm đỉnh u vào T ▪ thêm cạnh uv vào cây với v T là đỉnh gần u nhất Chương 2. Cây 26
27. Chương 2. Cây 27
28. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Thuật tốn Prim ⚫ Phương pháp lân cận gần nhất (Gán nhãn) ▪ Khoảng cách ▪ d(v, X) = min { d(v, x) | x X } với v X ▪ Nhãn của đỉnh ▪ Mỗi đỉnh v ta gắn một nhãn dv ▪ dv = d(v, T) với T là tập đỉnh của cây đang xây dựng ▪ Mỗi bước ta tìm đỉnh u mà du = min {dv | v T} ▪ Ghép uv vào cây T ▪ Cập nhật lại dv với v T Chương 2. Cây 28
29. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Thuật tốn Prim ⚫ Phương pháp lân cận gần nhất (Gán nhãn) ▪ Bước 1: Khởi tạo ▪ VT = {s}; T = ; ▪ ds = 0; dv = w(s, v) ▪ Bước 2: Tìm cạnh ▪ Tìm u mà du = min {dv | v VT} ▪ VT = VT  {u}; T = T  {uv} ▪ Nếu VT  V thì dừng ▪ Bước 3: Cập nhật nhãn ▪ dv = min{ dv, w(u, v) } với V VT Chương 2. Cây 29
30. Chương 2. Cây 30
31. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Thuật tốn Kruskal ⚫ Phân hoạch tập đỉnh ▪ Tập các đỉnh liên thơng với một đỉnh được chọn trong cây đang xét ▪ Tập các đỉnh cịn lại ⚫ Xây dựng cây ▪ Chọn 1 cạnh e = uv ▪ Nếu uv khơng liên thơng với nhau trong cây đang xây dựng thì ghép cạnh này vào cây ▪ Thuật tốn dừng khi được n-1 cạnh Chương 2. Cây 31
32. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Thuật tốn Kruskal ⚫ Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số. ⚫ Khởi tạo tập cạnh T =  ⚫ Với mỗi cạnh e lấy theo thứ tự: ▪ Nếu các đầu mút của e khơng liên thơng với nhau trong T thì ▪ Thêm e vào T. ⚫ Cây khung nhỏ nhất là T Chương 2. Cây 32
33. Chương 2. Cây 33
34. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Ví dụ: Tìm cây khung nhỏ nhất của đồ thị sau 5 2 2 4 20 1 6 20 1 3 5 4 Chương 2. Cây 34
35. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ Ví dụ: Tìm cây khung nhỏ nhất Chương 2. Cây 35
36. Cây khung (Spanning Tree) ⚫ Cây khung nhỏ nhất ⚫ So sánh Prim và Kruskal ⚫ Prim chọn cạnh cĩ trọng số nhỏ nhất liên thuộc với một đỉnh đã thuộc cây ⚫ Kruskal chọn cạnh cĩ trọng số nhỏ nhất miễn là khơng tạo ra chu trình ⚫ Thuật tốn Prim hiệu quả hơn đối với các đồ thị dày (số cạnh nhiều) Chương 2. Cây 36
37. Cây khung (Spanning Tree) ⚫ Một số bài tốn ứng dụng ⚫ Nối dây điện ⚫ Trong một mặt phẳng toạ độ cho N + 1 điểm, điểm đầu tiên chính là gốc tọa độ được coi là nguồn điện duy nhất mà từ đĩ ta nối dây cấp điện cho các nơi khác. Điểm thứ i trong N điểm cịn lại cĩ toạ độ là (Xi, Yi), là điểm đặt máy thứ i. Mỗi điểm đặt máy cĩ thể lấy trực tiếp từ nơi cấp điện ban đầu hay gián tiếp qua một điểm đặt máy khác. ⚫ Yêu cầu đưa ra phương án nối điện giữa các điểm để mọi nơi đặt máy đều cĩ điện và tổng chiều dài dây cần thiết là ngắn nhất. Chương 2. Cây 37
38. Cây khung (Spanning Tree) ⚫ Một số bài tốn ứng dụng ⚫ Theo thiết kế, một mạng giao thơng gồm N nút. Biết trước chi phí để xây dựng đường hai chiều trực tiếp từ nút i đến nút j. Hai tuyến đường khác nhau khơng cắt nhau tại điểm khơng là đầu mút. Hiện đã xây dựng được K tuyến đường. ⚫ Bài tốn : Hệ thống đường đã xây dựng đã bảo đảm sự đi lại giữa hai nút bất kỳ chưa? Nếu chưa, hãy chọn một số tuyến đường cần xây dựng thêm sao cho: ⚫ Các tuyến đường sẽ xây dựng thêm cùng với các đường đã xây dựng bảo đảm sự đi lại giữa hai nút bất kỳ. ⚫ Tổng kinh phí xây dựng các tuyến đường thêm vào là ít nhất. Chương 2. Cây 38