intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Toán rời rạc: Bài 8 - TS. Nguyễn Văn Hiệu

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:40

Thêm vào BST
Báo xấu
103
lượt xem 10
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhằm giúp các bạn chuyên ngành Toán học có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu, mời các bạn cùng tham khảo nội dung bài 8 "Cây và cây đối đại" thuộc bài giảng Toán rời rạc dưới đây. Nội dung bài giảng trình bày về: Cây tối đại, cây tối đại ngắn nhất, xác định cây tối đại ngắn nhất, cây có gốc,...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Bài 8 - TS. Nguyễn Văn Hiệu

  1. BÀI 8 CÂY & CÂY TỐI ĐẠI Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
  2. Nội dung 8.1. Cây 8.2. Cây tối đại 8.3. Cây tối đại ngắn nhất 8.4. Xác định cây tối đại ngắn nhất 8.5. Cây có gốc Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
  3. 8.1. Cây Định nghĩa Ví dụ Cây là một đơn đồ thị vô hướng, liên thông và không chứa chu trình. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
  4. 8.1. Cây Đồ thị nào sau đây là cây? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
  5. 8.1. Cây Định nghĩa Ví dụ Rừng là một đồ thị gồm p thành phần liên thông, trong đó mỗi thành phần liên thông là một cây. Lưu ý: cây không chứa khuyên và cạnh song song 5
  6. 8.1. Cây Tính chất Ví dụ Một cây T gồm N đỉnh với N  2 chứa ít nhất hai đỉnh treo 6
  7. 8.1. Cây Tính chất Tính chất Cho T là một đồ thị vô hướng 3. T liên thông và mỗi cạnh có n đỉnh. Có các mệnh đề của T đều là cạnh cắt tương đương sau: (cầu). 1. T là cây. 4. Hai đỉnh bất kỳ của T được 2. T không chứa chu trình và nối với nhau bằng đúng 1 có n – 1 cạnh. đường đi đơn. 3. T liên thông và có n – 1 5. T không chứa chu trình cạnh. nhưng nếu thêm 1 cạnh bất kỳ vào T thì ta sẽ được thêm đúng 1 chu trình. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
  8. 8.2. Cây tối đại a Định nghĩa Cho G=(X, E) là một đồ thị c liên thông và T=(X, F) là một b đồ thị bộ phận của G. Nếu T là d cây thì T được gọi là một cây tối đại của G. e a  Các tên gọi khác: a  cây khung, b c c b  cây bao trùm,  cây phủ e e d d Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
  9. 8.2. Cây tối đại Tính chất Ví dụ  Mọi đồ thị liên thông đều có chứa ít nhất một cây tối đại D A B E C F Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
  10. 8.2. Cây tối đại Xác định cây tối đại Thuật toán Thuật toán tựa PRIM 1. Chọn tùy ý v  X và khởi tạo Input: V := { v }; U := ; 2. Chọn w X \ V sao cho e Đồ thị liên thông G=(X, E),  E, e nối w với một đỉnh X gồm N đỉnh trong V Output: 3. V := V  {w}; U := U  {e} Cây tối đại T=(V, U) của G 4. Nếu U đủ N-1 cạnh thì dừng, ngược lại lặp từ bước 2. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
  11. 8.2. Cây tối đại Xác định cây tối đại Xác định cây tối đại  V = {F, A, B, E, C, D} D  U = {FA, AB, BE, FC, ED} A B F E C Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
  12. 8.2. Cây tối đại Cài đặt Graph Graph::SpanningTree() { //Tìm cây khung của đồ thị } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
  13. 8.3. Cây tối đại ngắn nhất Định nghĩa Định nghĩa Cho G=(X, E)  TRỌNG LƯỢNG của một cây  G được gọi là ĐỒ THỊ CÓ T của G bằng với tổng trọng lượng các cạnh trong cây: TRỌNG nếu mỗi cạnh của G được tương ứng với một L(T) = (eT)L(e) số thực, nghĩa là có một ánh xạ như sau:  CÂY TỐI ĐẠI NGẮN NHẤT L: E  |R là cây tối đại có trọng lượng nhỏ nhất của G. e | L(e)  Các tên gọi khác: cây khung bé nhất, cây bao trùm nhỏ nhất, cây phủ bé nhất Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
  14. 8.3. Cây tối đại ngắn nhất Ứng dụng Ứng dụng  Bài toán xây dựng hệ thống  Bài toán nối mạng máy tính đường sắt Cần nối mạng một hệ thống Cần xây dựng hệ thống đường gồm n máy vi tính. Biết chi phí sắt nối n thành phố sao cho nối máy i với máy j là c[i,j] khách hàng có thể đi bất cứ (chi phí phụ thuộc vào độ dài một thành phố nào đến bất kỳ cáp). Hãy tìm cách nối mạng một trong số các thành phố còn sao cho tổng chi phí nối mạng lại. Mặt khác, đòi hỏi chi phí là bé nhất. để xây dựng hệ thống đường sắt là nhỏ nhất. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
  15. 8.3. Cây tối đại ngắn nhất Chú ý Nhắc lại • Trong các thuật toán tìm cây  MA TRẬN TRỌNG SỐ: tối đại ngắn nhất chúng ta LNxN : có thể bỏ đi – Lij = trọng lượng cạnh nhỏ  các khuyên; nhất nối i đến j (nếu có)  hướng các cạnh; – Lij =  nếu không có cạnh  đối với các cạnh song song thì nối i đến j có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
  16. 8.3. Cây tối đại ngắn nhất Ví dụ Ma trận trọng số 5  12 7 5  16 D   A 12 B 12  15 16 6  6 7 15   10  7 5   5   5 15 16 E  10 5   C 10  6 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
  17. 8.4. Xác định cây tối đại ngắn nhất Tiếp cạnh truyền thống Tiếp cạnh truyền thống  Liệt kê tất cả các cây khung  Số cây khung của đồ thị đầy đủ của G Kn là nn-2  TÍNH TRỌNG LƯỢNG của mỗi cây tối đại của G  Chọn cây tối đại có trọng thời gian cỡ nn-2 lượng bé nhất Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
  18. 8.4. Xác định cây tối đại ngắn nhất KRUSKAL KRUSKAL Input: đồ thị G=(X, E) liên 1. Sắp xếp các cạnh trong G thông, X gồm N đỉnh tăng dần theo trọng lượng; khởi tạo T := . Output: cây tối đại ngắn nhất T=(V, U) của G 2. Lần lượt lấy từng cạnh e thuộc danh sách đã sắp xếp. Nếu T+{e} không chứa chu trình thì kết nạp e vào T: T := T+{e}. 3. Nếu T đủ N-1 cạnh thì dừng; ngược lại, lặp bước 2. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
  19. 8.4. Xác định cây tối đại ngắn nhất KRUSKAL Mã giả Input: đồ thị G=(X, E) liên KRUSKAL(...){ thông, X gồm N đỉnh T = ʘ; Output: cây tối đại ngắn nhất while(|T| < n-1 && E!= ʘ) { T=(V, U) của G E = E \{e} if(T hợp {e} không chu trình) T = T hợp {e}; } if((|T| < n-1 ) } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
  20. 8.4. Xác định cây tối đại ngắn nhất Trọng số Cạnh Chọn 2 20 4 4 (3,5) 33 Chọn 8 8 (4,6) 18 16 Chọn 1 9 6 9 (4,5) 14 (5,6) Không 17 14 5 16 (3,4) Không 3 4 17 (1,3) Chọn 18 (2,3) Chọn. Dừng vì đã 20 (2,4) đủ cạnh. 33 (1,2) 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
44=>2