Cây Bao Trùm Ngắn Nhất Lý Thuyết, Thuật Toán Và ứng Dụng - Tài Liệu Text

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (72 trang)

Trang chủ

Luận Văn - Báo Cáo

Công nghệ thông tin

Cây bao trùm ngắn nhất lý thuyết, thuật toán và ứng dụng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.24 MB, 72 trang )

iMỤC LỤCtrangMỤC LỤC ............................................................................................................... iDANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .............................................. iiiDANH MỤC BẢNG .............................................................................................. ivDANH MỤC HÌNH ................................................................................................ vMỞ ĐẦU ................................................................................................................ 1CHƯƠNG I. GIỚI THIỆU CÂY BAO TRÙM NGẮN NHẤT ............................... 41.1. GIỚI THIỆU .................................................................................................... 41.1.1. Khái niệm về cây .................................................................................... 41.1.2. Cây Có Gốc ............................................................................................ 61.1.3. Cây m - phân .......................................................................................... 81.1.4. Duyệt cây nhị phân ............................................................................... 101.1.5. Cây tìm kiếm nhị phân .......................................................................... 131.1.6. Cây bao trùm ........................................................................................ 141.1.7. Cây bao trùm ngắn nhất ........................................................................ 151.1.8. Cây bao trùm trên đồ thị có trọng số ...................................................... 181.2. MỘT SỐ BÀI TOÁN DẪN ĐẾN CÂY BAO TRÙM ..................................... 221.2.1. Cây và bài toán liệt kê .......................................................................... 221.2.2. Vạch đường trong mạng di động ........................................................... 241.3. TỔNG KẾT CHƯƠNG .................................................................................. 28CHƯƠNG II. MỘT SỐ THUẬT TOÁN TÌM CÂY BAO TRÙM NGẮN NHẤT ...... 292.1. THUẬT TOÁN BORŮVKA ........................................................................ 302.1.1. Mô tả thuật toán Borůvka song song. .................................................... 322.1.2. Thuật toán song song cho bước 2 .......................................................... 332.1.3. Thuật toán con trỏ nhảy mới ................................................................. 342.2. THUẬT TOÁN KRUSKAL .......................................................................... 362.2.1. Mô tả thuật toán .................................................................................... 362.2.2. Chứng minh tính đúng đắn.................................................................... 402.2.3. Thực hiện thuật toán ............................................................................. 412.3. THUẬT TOÁN PRIM .................................................................................... 422.3.1. Mô tả thuật toán. ................................................................................... 432.3.2. Độ phức tạp thuật toán ......................................................................... 482.3.3. Chứng minh tính đúng đắn.................................................................... 482.3.4. Thực hiện thuật toán ............................................................................. 49ii2.4 TỔNG KẾT CHƯƠNG II ............................................................................... 50CHƯƠNG III. ỨNG DỤNG THUẬT TOÁN CÂY BAO TRÙM NGẮN NHẤTVÀO BÀI TOÁN THIẾT KẾ ĐƯỜNG CÁP TRUYỀN HÌNH ............................. 513.1. TỔNG QUAN MẠNG TRUYỂN HÌNH CÁP ................................................ 513.1.1. Hệ thống trung tâm ............................................................................... 523.1.2. Mạng phân phối tín hiệu truyền hình cáp .............................................. 523.1.3. Thiết bị tại nhà thuê bao ...................................................................... 523.1.4. Cấu hình mạng truyền hình cáp ............................................................ 533.2. MÔ TẢ THUẬT TOÁN CÂY BAO TRÙM NGẮN NHẤT CHO BÀI TOÁNTHIẾT KẾ CÁP TRUYỀN HÌNH ......................................................................... 573.2.1. Phát biểu bài toán ................................................................................. 573.2.2. Mô tả dạng toán học của bài toán .......................................................... 583.2.3. Thực hiện bài toán ................................................................................ 593.3. THIẾT KẾ CHƯƠNG TRÌNH VÀ KẾT QUẢ THỬ NGHIỆM .................... 603.3.1. Thiết kế chương trình .......................................................................... 603.3.2. Kết quả thử nghiệm .............................................................................. 613.4 TỔNG KẾT CHƯƠNG III .............................................................................. 65KẾT LUẬN VÀ KIẾN NGHỊ ............................................................................... 66iiiDANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮTTiếng AnhTừ viết tắtTên đầy đủDiễn giảiMSTMinimum Spanning TreeCây khung nhỏ nhấtBSTBinary Search TreeCây tìm kiếm nhị phânMultichannel MultipointDịch vụ phân phối đa điểm đaMMDSDistribution ServicekênhHFCHybrid Fiber CoaxiaMạng truyền dẫnFTTHFiber to the homeCáp quang băng thông rộngstrStructureCấu trúcivDANH MỤC BẢNGTrangBảngBảngBảngBảngBảngBảngBảngBảng1. Minh họa thuật toán Borůvka ......................................................... 322. Đồ thị có cấu trúc ........................................................................... 353. Thuật toán Kruskal ......................................................................... 394. Kết quả chạy ví dụ 1....................................................................... 405. Minh hoạ thuật toán Prim ............................................................... 466. Kết quả chạy ví dụ.......................................................................... 477. Liệt kê thời gian chạy thuật toán .................................................... 488. Khoảng cách giữa các trạm FTTH .................................................. 62vDANH MỤC HÌNHTrangHình 1. 1 Sơ đồ hình cây ......................................................................................... 4Hình 1. 2 Cây có gốc x0 .......................................................................................... 7Hình 1. 3 Cây có gốc ............................................................................................... 7Hình 1. 4 Duyệt cây nhị phân................................................................................. 11Hình 1. 5 Duyệt cây nhị phân theo trung thứ tự ..................................................... 12Hình 1. 6 Cây bao trùm nhỏ nhất trên đồ thị phẳng ................................................ 16Hình 1. 7 Cây bao trùm nhỏ nhất trong một đồ thị ................................................. 16Hình 1. 8 Cây bao trùm nhỏ nhất có trọng số nhỏ nhất .......................................... 18Hình 1. 9 Cây liệt kê hoán vị của {1, 2, 3}............................................................. 23Hình 1. 10 Liệt kê các xâu ..................................................................................... 24Hình 1. 11 Liệt kê các tập con ............................................................................... 24Hình 1. 12 Mô hình mạng có hệ thống không dây.................................................. 25Hình 1. 13 Vạch đường đi trong mạng di động ...................................................... 27Hình 2. 1 Thuật toán siêu đỉnh thực hiện theo danh sách ....................................... 34Hình 2. 2 cây khung nhỏ nhất của đồ thị ................................................................ 39Hình 2. 3 Kết thúc thuật toán được cây khung nhỏ nhất ......................................... 40Hình 2. 4 Cây khung có trọng số ........................................................................... 47Hình 3. 1 Sơ đồ khối hệ thống truyền hình cáp ...................................................... 51Hình 3. 2 Các cấu hình mạng HFC ........................................................................ 53Hình 3. 3 Mạng sao truyền dẫn .............................................................................. 54Hình 3. 4 Mạng vòng truyền dẫn ........................................................................... 54Hình 3. 5 Mạng con phân phối............................................................................... 54Hình 3. 6 Cấu hình FTF ......................................................................................... 55Hình 3. 7 Cấu hình FTTH ...................................................................................... 56Hình 3. 8 Cấu hình FTTC ...................................................................................... 56Hình 3. 9 Cấu hình FTLA ...................................................................................... 57Hình 3. 10 Tuyến huyện ........................................................................................ 58Hình 3. 11 Triển khai mạng cáp tuyến huyện. ........................................................ 59Hình 3. 12 Giao diện chương trình......................................................................... 60Hình 3. 13 Nhập dữ liệu vào chương trình ............................................................. 62Hình 3. 14 Kết quả chạy chương trình với thuật toán Prim .................................... 63Hình 3. 15 Kết quả chạy chương trình thuật toán Kruskal ...................................... 63Hình 3. 16 Bài toán nhiều đỉnh .............................................................................. 64Hình 3. 17 Chương trình chạy thuật toán Kruskal .................................................. 65Hình 3. 18 Chương trình chạy thuật toán Prim....................................................... 651MỞ ĐẦU1. Lý do chọn đề tàiLý thuyết đồ thị là một lĩnh vực đã được nghiên cứu từ những năm1857, khi nhà toán học Anh tên là Arthur Cayley dùng cây để xác định nhữngdạng khác nhau của hợp chất hoá học. Từ đó cây đã được dùng để giải nhiềubài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, người ta dùng cây để xâydựng các thuật toán rất có hiệu quả để tìm kiếm các phần tử trong một danhsách. Cây cũng được dùng để tạo ra các mã có hiệu quả để lưu trữ và truyềndữ liệu. Dùng cây có thể mô hình các thủ tục mà để thi hành nó cần dùng mộtdãy các quyết định. Cây cũng dùng để xây dựng các mạng máy tính với chiphí rẻ nhất cho các đường điện thoại nối các máy phân tán do có thể tìm đượccây bao trùm ngắn nhất giữa các nút mạng.Lý thuyết đồ thị không những có nhiều ứng dụng trong thực tế mà cònlà công cụ đắc lực cho ngành công nghệ thông tin. Nó giúp cho chúng ta môtả một cách dễ dàng các bài toán phức tạp cụ thể, để từ đó ta có thể mã hoácác bài toán đó vào máy tính. Ngoài ra lý thuyết đồ thị được sử dụng để giảiquyết các bài toán trong nhiều lĩnh vực khác nhau.Cùng với sự phát triển chung của nhân loại thì trong lĩnh vực thông tincũng có những bước phát triển mạnh mẽ nhằm đáp ứng nhu cầu của cuộcsống ngày nay. Các hệ thống thông tin truyền thống như thông tin vô tuyến,thông tin hữu tuyến ngày càng có những biến đổi cả về chất lẫn lượng. Nhucầu thực tế yêu cầu hệ thống truyền dẫn thông tin có dung lượng lớn, tốc độtruyền dẫn cao. Đặt ra yêu cầu cho nhà cung cấp hệ thống thông tin cũng nóichung và các nhà cung cấp truyền hình nói riêng về vấn đề nâng cao chấtlượng phục vụ, cũng như việc triển khai lắp đặt mới một hệ thống truyền hìnhcáp trong một khu vực nhỏ như cấp huyện hay trong một thành phố lớn.2Việc tính toán khảo sát một địa điểm mới để triển khai mới tránh lãngphí tài nguyên cáp truyền dẫn, lãng phí nhân công và tài chính của đơn vịcung cấp truyền hình cáp, cũng như lắp đặt các trạm truyền dẫn một cách hiệuquả. Đòi hỏi nhà cung cấp phải tính toán đường đi cáp xuyên suốt từ trungtâm truyền dẫn đến các điểm sử dụng thuê bao một cách ngắn nhất, tích kiệmnhất để chánh lãng phí và đảm bảo tín hiệu truyền dẫn được ổn định.Nhận thấy sự khó khăn mất nhiều thời gian, công sức và tài chính đểkhảo sát địa điểm lựa chọn giải pháp lắp đặt hệ thống truyền hình cáp sao chotối ưu và tích kiệm nhất, đảm bảo tính khoa học vì vậy em đã lựa chọn đề tài“Cây bao trùm ngắn nhất : Lý thuyết, thuật toán và ứng dụng”. để ápdụng vào thực tế khảo sát và triển khai mới hệ thống truyền hình cáp mộtcách tối ưu nhất có thể.2. Đối tượng nghiên cứuĐối tượng nghiên cứu của luận văn là các vấn đề về Cây bao trùmngắn nhất, thuật toán và các ứng dụng thực tiễn của nó.3. Phạm vi nghiên cứuLuận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ sở lýthuyết như: Lý thuyết về đồ thị và cây, cây bao trùm ngắn nhất, thuật toán vàcác ứng dụng của cây bao trùm ngắn nhất.4. Nhiệm vụ nghiên cứu- Tìm hiểu những kiến thức tổng quan về cây bao trùm ngắn nhất.- Tìm hiều ba thuật toán liên quan đến cây bao trùm ngắn nhất Borůvka,thuật toán Kruskal, thuật toán Prim.- Thiết kế chương trình ứng dụng vào thực tế giải bài toán thiết hệ thốngtruyền hình cáp.35. Những nội dung nghiên cứu chínhBố cục của luận văn gồm phần mở đầu trình bày lý do chọn đề tài, đốitượng và nhiệm vụ nghiên cứu của đề tài. Chương một, Tìm hiểu và trình bàynhững lý thuyết cơ bản về khái niệm cây bao trùm: lịch sử ra đời và phát triểncủa của cây bao trùm, khái niệm cây, các định nghĩa, định lý, tính chất, ví dụvề cây bao trùm và cây bao trùm có trọng số bé nhất. Một số bài toán dẫn đếncây bao trùm. Chương hai, Tìm hiều, giới thiệu ba thuật toán liên quan đếncây bao trùm ngắn nhất Borůvka, thuật toán Kruskal, thuật toán Prim. Chương3, Tìm hiểu lịch sử truyền hình cáp, sự phát triển của truyền hình cáp hiệnnay. Mổ ta bài toán cây bao trùm ngắn nhất cho bài toán thiết kế cáp truyềnhình. Thiết kế chương trình, và kết quả thử nghiệm.6. Phương pháp nghiên cứu- Phương pháp đọc tài liệu- Phương pháp quan sát- Phương pháp phân tích – tổng hợp lý thuyết.- Phương pháp thực nghiệm.4CHƯƠNG I. GIỚI THIỆU CÂY BAO TRÙM NGẮN NHẤT1.1. GIỚI THIỆUMột đồ thị liên thông và không có chu trình được gọi là cây. Cây đượcdùng từ năm 1857, khi nhà toán học Anh tên là Arthur Cayley dùng cây đểxác định những dạng khác nhau của hợp chất hóa học. Từ đó cây đã đượcdùng để giải nhiều bài toán trong nhiều lĩnh vực khác nhau. Trong tin học câyđược dùng để tìm kiếm các phần tử trong danh sách hoặc bài toán xây dựngcác mạng máy tính với chi phí rẻ với các máy phân tán.[1]1.1.1. Khái niệm về câyĐịnh nghĩa.Cây là một đồ thị mà trong đó hai đỉnh bất kì đều được nối với nhaubằng đúng một đường đi. [4]aebabcaddfcbgeHình 1. 1 Sơ đồ hình câyĐịnh lý 1. Nếu T là một cây có n đỉnh thì T có ít nhất hai đỉnh treo.Chứng minh:Lấy một cạnh (a,b) bất kỳ của cây T. Trong tập hợp các đường đi chứacạnh (a,b), ta lấy đường đi từ u đến v dài nhất. Vì T là một cây nếu u ≠ v. u và vphải là hai đỉnh treo vì nếu một đỉnh, u chẳng hạn, không phải là đỉnh treo thì uphải là đầu mút của một cạnh (u,x), với x là đỉnh không thuộc đường đi từ uđến v. Do đó, đường đi sơ cấp từ x đến v, chứa cạnh (a,b), dài hơn đường đi từ5u đến v, trái với tính chất đường đi từ u đến v đã chọn.Ta nhận thấy rằng cây là đồ thị vô hướng đơn giản nhất, định lí 2 cho tamột số tính chất của cây.[3]Định lý 2. Cho đồ thị T=(V,E) có n đỉnh. Sáu mệnh đề là tương đương:1) T là một cây.2) T liên thông và có n1 cạnh.3) T không chứa chu trình và có n-1 cạnh.4) T liên thông và mỗi cạnh là cầu.5) Giữa hai đỉnh phân biệt của T luôn có duy nhất mộtđường đi sơ cấp.6) T không chứa chu trình nhưng khi bổ sung vào mộtcạnh nối hai đỉnh không kề nhau thì xuất hiện một chutrình.Chứng minh.Chứng minh 12 (theo quy nạp)Khẳng định đúng với n  1 và n  2 . Giả sử khẳng định đúng với mọicây T' với n  1 đỉnh khi đó T' liên thông và có n  2 cạnh.Ta chứng minh khẳng định đúng với mọi T có n đỉnh (n  2) . Trong Tbao giờ cũng tìm được ít nhất một đỉnh treo vì trái lại sẽ tồn tại chu trình trongT. Giả sử v1 là đỉnh treo và v1 kề v2 trong T khi đó nếu ta loại bỏ v1 và cạnh( v1 , v2 ) khỏi T thì T sẽ có n  2 cạnh (theo giả thiết quy nạp). Vậy cây T cón  2  1  n  1 cạnh.Chứng minh 23 (theo phản chứng)Giả sử T không liên thông khi đó T sẽ có k thành phần liên thông( k  1) và giả sử rằng các thành phần liên thông đó là T1 , T2 ,..., Tk . Vì T không6chưa chu trình nên các thành phần liên thông đó cũng không chứa chu trình.Gọi ni và ei tương ứng số các đỉnh và các cạnh của thành phần liên thông Ti .Ta có ei  ni  1(i  1, 2,..., k ) suy ra n1  n2  ...nk  k  e1  e2  ...ek  n  1(vì e1  e2  ...ek  n  1 ) n1  n2  ...  nk  (n  1  k )  n mâu thuẫn.Chứng minh 34Khi loại bỏ một cạnh bất kì khỏi T thì T sẽ có n đỉnh và n  2 cạnh nêntồn tại ít nhất một đỉnh cô lập có nghĩa là T không liên thông. Vậy mọi cạnhtrong T đều là cầu.Chứng minh 45 (theo phản chứng)Vì T liên thông nên giữa hai đỉnh bất kì luôn tồn tại đường đi sơ cấp vàđường đi này là duy nhất. Thật vậy giả sử tồn tại một đường đi sơ cấp khác thìT sẽ chứa chu trình và các cạnh trên chu trình này không phải là cầu mâuthuẫn với giả thiết.Chứng minh 56Dễ nhận thấy T không chứa chu trình vì nếu chứa chu trình thì sẽ tồn tạicặp đỉnh có nhiều hơn một đường đi đơn. Giả sử u và v là hai đỉnh không kềnhau bất kì trong T nếu ta nối u và v thì cạnh này cùng với đường đi đơn từu tới v tạo thành chu trình trong T và chu trình này là duy nhất. (đpcm)Chứng minh 61(theo phản chứng)Giả sử T không liên thông khi đó tồn tại ít nhất hai thành phần liênthông giả sử là T1 và T2 , nối cạnh ( u , v ) với u  T1 và v  T2 thì trong Tkhông xuất hiện thêm một chu trình nào cả. Điều này mâu thuẫn với giả thiết.1.1.2. Cây Có GốcĐịnh nghĩa. Cây có hướng là đồ thị có hướng mà đồ thị vô hướngtương ứng của nó là một cây.[1]7Cây có gốc là cây có hướng, trong đó có một đỉnh đặc biệt, gọi là gốc,từ gốc có đường đi đến mọi đỉnh khác của cây.Trong cây có gốc thì gốc x0 có bậc vào bằng 0, còn tất cả các đỉnh khácđều có bậc vào bằng 1.x11x1x5x15x8x4x0x2x12x16x9x6x13x3x10x7x14x17Hình 1. 2 Cây có gốc x0Một cây có gốc thường được vẽ với gốc x0 ở trên cùng và cây phát triểntừ trên xuống (hình 1.2). Gốc của cây (đỉnh x0 ) gọi là đỉnh mức 0. Các đỉnh kềvới gốc được xếp ở phía dưới và gọi là đỉnh mức 1. Đỉnh ngay dưới đỉnh mức klà đỉnh mức k +1.Tổng quát, trong một cây có gốc x0 thì đỉnh x của cây là đỉnh có mức kkhi và chỉ khi đường đi từ đến x0 có độ dài bằng k.Mức lớn nhất của một đỉnh có trong cây gọi là chiều cao của cây.Cây có gốc ở hình 2 thường được vẽ như trong hình 1.3 để làm rõ mứccủa các đỉnh.xxxxxxxxxxx10x13x12x11x14x15Hình 1. 3 Cây có gốcx16x178Trong cây có gốc, mọi cạnh đều có hướng từ trên xuống, vì vậy vẽ mũitên để chỉ hướng đi là không cần thiết. Xét một đường đi xuất phát từ gốc củacây có gốc. Ta có các khái niệm sau: Đỉnh có mức k được gọi là cha của các đỉnh mức k+1, đỉnh ở mức k+1gọi là con của đỉnh ở mức k. Các đỉnh có cùng cha được gọi là anh em. Các đỉnh có mức nhỏ hơn k gọi là tổ tiên của đỉnh ở mức k. Đỉnh ở mức lớn nhất của đường đi đó gọi là lá. Lá là đỉnh treo và khôngcó con. Mọi đỉnh không phải là lá được gọi là đỉnh trong.Cây có gốc mà mức của mọi lá sai khác nhau không quá 1 đơn vị gọi làcây cân đối (hay cây cân bằng). Nói cách khác cây cân đối là cây mà mọi láđều có mức h hoặc h – 1 trong đó h là chiều cao của cây.Với một cây tùy ý, nếu chọn một đỉnh nào đó làm gốc được cây có gốctương ứng. Do chọn gốc bất kỳ nên với cây có n đỉnh sẽ có n cây có gốc tươngứng khác nhau. Có thể chứng minh được rằng, nếu chọn tâm của cây là gốc thìđược cây có gốc có độ cao nhỏ nhất.1.1.3. Cây m – phânĐịnh nghĩa. Một cây có gốc T được gọi là cây m-phân nếu mỗi đỉnhtrong của T có nhiều nhất là m con.Cây có gốc T được gọi là một cây m-phân đầy đủ nếu mỗi đỉnh trongcủa T đều có m con.Định lý 3. Một cây m-phân đầy đủ có k đỉnh trong thì có m.k  1 đỉnhvà có (m  1)k  1 lá.9Chứng minh. Mọi đỉnh trong của cây m-phân đầy đủ đều có bậc ra làm, còn lá có bậc ra là 0. Vậy tổng số bậc ra của cây là m.k, từ đó số cạnh củacây là m.k. Và do đó số đỉnh của cây là m.k  1. Gọi s là số lá thì ta cós  k  m.k  1 , nên s  (m  1)k  1 .Định lý 4.1. Một cây m-phân có chiều cao h thì có nhiều nhất là m h lá.2. Một cây m-phân có s lá thì có chiều cao h  [log ms] .3. Một cây m-phân đầy đủ và cân đối có s lá thì có chiều caoh  [log ms] .Chứng minh.1) Mệnh đề được chứng minh bằng quy nạp theo h. Mệnh đề hiển nhiênđúng khi h = 1.Giả sử mọi cây m-phân có chiều cao h = k đều có nhiều nhất m k lá (vớih  2 ). Xét cây m-phân (cây T) có chiều cao h  k  1. Bỏ gốc khỏi cây đượcmột rừng gồm không quá m cây con, mỗi cây con này có chiều cao không quák. Do giả thiết quy nạp, mỗi cây con này có nhiều nhất là m k lá. Do lá củanhững cây con này cũng là lá của T, nên T có nhiều nhất là m. m k  mk  1 lá.Theo nguyên lý quy nạp, mệnh đề đúng đối với mọi cây có chiều caotuỳ ý.2) s  m h  h  [log ms]Do cây là cân đối nên các lá có mức h hoặc h –1, vì có ít nhất một lá ởmức h nên số lá phải nhiều hơn m h 1 Vậy:m h1  s  mh  h  1  log m s  h  h  [log ms] .Ví dụ: Xét trò chơi gửi thư dây truyền. Ban đầu có một người nhậnđược một lá thư và giả sử rằng mỗi người khi nhận được một thư hoặc sẽ sao10gửi thư đó cho 4 người khác hoặc là không chuyển cho ai cả. Hỏi có bao nhiêungười nhận được thư kể cả người đầu tiên nếu không có ai nhận được nhiềuhơn một bức thư và trò chơi kết thúc khi có 100 người nhận được thư màkhông viết cho ai cả.Giải: Biểu diễn trò chơi bằng một cây tứ phân đầy đủ, các đỉnh trong lànhững người nhận được thư và sao gửi cho người khác còn lá là những ngườinhận được thư mà không gửi cho ai cả. Vì có 100 người không viết thư cho ainên số lá của cây là s = 100, theo định lý 3 ta có 100 = (4 – 1)k + 1 thuộc sốđỉnh trong của cây là: k = 33 thuộc số đỉnh của của cây là: n = 100 + 33 = 133.Vậy có 133 người nhận được thư.1.1.4. Duyệt cây nhị phâna) Định nghĩa. [3]Trong nhiều trường hợp, ta cần phải duyệt một cách có hệ thống mọiđỉnh của một cây nhị phân, mỗi đỉnh chỉ một lần. Ta gọi đó là việc duyệt câynhị phân hay đọc cây nhị phân.Có nhiều thuật toán duyệt cây nhị phân, các thuật toán đó khác nhauchủ yếu ở thứ tự thăm các đỉnh.Cây nhị phân T có gốc r được ký hiệu là T( r ). Giả sử r có con bên tráilà u , con bên phải là v . Cây có gốc u và các đỉnh khác là mọi dòng dõi của utrong T gọi là cây con bên trái của T, ký hiệu T( u ). Tương tự, ta có cây conbên phải T( v ) của T. Một cây T( r ) có thể không có cây con bên trái hay bênphải.Sau đây là ba trong các thuật toán duyệt cây nhị phân T( r ). Các thuậttoán đều được trình bày đệ quy. Chú ý rằng khi cây T( x ) chỉ là một đỉnh x thì“duyệt T( x )” có nghĩa là “thăm đỉnh x ”.11abcdghlfeimfjnopqsHình 1. 4 Duyệt cây nhị phânb). Thuật toán duyệt cây nhị phân1) Thuật toán tiền thứ tự: (preorder)1. Thăm gốc r .2. Duyệt cây con bên trái của T( r ) theo tiền thứ tự.3. Duyệt cây con bên phải của T( r ) theo tiền thứ tự.Duyệt cây nhị phân T( a ) trong hình trên theo tiền thứ tự: Kết quả duyệtcây T( a ) theo tiền thứ tự là:a, b, d, g, l, h, e, i, m, n, c, f, j, o, p, k, q, s.2) Thuật toán trung thứ tự: (inorder)1. Duyệt cây con bên trái của T(r) theo trung thứ tự.2. Thăm gốc r.3. Duyệt cây con bên phải của T( r ) theo trung thứ tự.Duyệt cây nhị phân T( a ) trong hình trên theo trung thứ tự: Kết quảduyệt cây T( a ) theo trung thứ tự là:g, l, d, h, b, m, i, n, e, a, c, o, j, p, f, q, k, s.3) Thuật toán hậu thứ tự: (postorder)121. Duyệt cây con bên trái của T(r) theo hậu thứ tự.2. Duyệt cây con bên phải của T(r) theo hậu thứ tự.3. Thăm gốc r.Duyệt cây nhị phân T( r ) trong hình trên theo hậu thứ tự: Kết quả duyệtcây T( r ) theo trung thứ tự là:l, g, h, d, m, n, i, e, b, o, p, j, q, s, k, f, c, a.4) Ký pháp Ba LanXét biểu thức đại số sau đây:(a+b)*(cd/2)(1)Ta vẽ một cây nhị phân như hình dưới đây, trong đó mỗi đỉnh trongmang dấu của một phép tính trong (1), gốc của cây mang phép tính sau cùngtrong (1), ở đây là dấu nhân ký hiệu là *, mỗi lá mang một số hoặc một chữ đạidiện cho số.*+ab/cd2Hình 1. 5 Duyệt cây nhị phân theo trung thứ tựDuyệt cây nhị phân trong hình trên theo trung thứ tự là:a + b * c d / 2(2)và đây là biểu thức (1) đã bỏ đi các dấu ngoặc.Đối với cây trong hình thứ nhất, nếu duyệt theo tiền thứ tự, ta có* + a b c / d 2(3)13và nếu duyệt theo hậu thứ tự, ta có:a b + c d 2 / *(4)Vì vậy, nếu ta viết các biểu thức trong đại số, trong lôgic bằng cáchduyệt cây tương ứng theo tiền thứ tự hoặc hậu thứ tự thì ta không cần dùng cácdấu ngoặc mà không sợ hiểu nhầm.Người ta gọi cách viết biểu thức theo tiền thứ tự (tiền tố) là ký pháp BaLan, còn cách viết theo hậu thứ tự (hậu tố) là ký pháp Ba Lan đảo, để ghi nhớđóng góp của nhà toán học và lôgic học Ba Lan Lukasiewicz (1878-1956)trong vấn đề này.Việc chuyển một biểu thức viết theo ký pháp quen thuộc (có dấu ngoặc)sang dạng ký pháp Ba Lan hay ký pháp Ba Lan đảo hoặc ngược lại, có thểthực hiện bằng cách vẽ cây nhị phân tương ứng sau đó áp dụng thuật toánduyệt cây theo thứ tự trước; thứ tự sau như đã làm đối với biểu thức (1).Như vậy việc tính giá trị của một biểu thức trong tin học thực hiện haithao tác cơ bản(1) Chuyển đổi biểu thức dạng trung tố sang hậu tố(2) Tính giá trị biểu thức hậu tố1.1.5. Cây tìm kiếm nhị phânCây tìm kiếm nhị phân (BST) là một cấu trúc rất thuận lợi cho bài toántìm kiếm.Định nghĩa. Cây tìm kiếm ứng với n khóa k1 , k2 ,...kn là cây nhị phânmà mỗi nút đều được gán một khóa sao cho với mỗi mỗi nút k:Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút kMọi khóa trên cây con phải đều lớn hơn khóa trên nút kCây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để14xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, cácdãy kết hợp.Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tậphợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt. Mọi núttrong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây conphải có nút lớn hơn hoặc bằng khóa của nút cha.Nếu một BST không chứa các giá trị giống nhau thì nó biểu diễn mộttập hợp đơn trị như trong lí thuyết tập hợp. Cây loại này sử dụng các bất đẳngthức nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nútcha, mọi nút trên cây con phải có nút lớn hơn khóa của nút cha.Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùytheo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía,nhưng khi đó việc tìm kiếm trở nên phức tạp hơn.1.1.6. Cây bao trùmGiả xử G = ( X, E) là đồ thị vô hướng liên thông với n đỉnh (n ≥ 2). [6]Định lý 5.Đồ thị vô hướng G =( X, E )với n (n ≥ 2) đỉnh có cây bao trùm khi vàchỉ khi nó liên thông.Chứng minh.Điều kiện cần.Giả sử đồ thị vô hướng G =( X, E ) có cây bao trùm (H = ( X,F)), nhưngG lại không liên thông. Khi đó x , y  X không nối với nhau. Đồ thị H =(X,F) nhận được từ G bằng cách bỏ đi một số cạnh, nên trong đồ thị H cácđỉnh x, y cũng không nối với nhau, suy ra đồ thị H không liên thông. Xẩy ramâu thuẫn với tính chất của cây. Do đó đồ thị G liên thông.Điều kiện đủ.15Nếu đồ thị G liên thông ta tìm tất cả các cạnh, mà khi loại các cạnh nàykhỏi G không làm mất tính liên thông của đồ thị.Nếu trong G không có cạnh nào như vậy, thì G không có chu trình nênnó chính là cây bao trùm.Ngược lại giả sử a là một cạnh nào đó trong các cạnh đã nói ở trên, taxóa a khởi G và kí hiệu đồ thị bộ phận nhận được bằng G1.Đối với G1 và các đồ thị nhận được tiếp theo ta thực hiện xóa các cạnhtương ứng như trên cho tói khi nhận được đồ thị bộ phận H = (X,F) liên thôngvà tất cả các cạnh khác khi xóa đều làm mất tính liên thông của đồ thị, nên đồthị bộ phận H = (X,F) là một cây bao trùm của đồ thị G. Định lý được chứngminh.Chứng minh điều kiện đủ là thuật toán cây bao trùm của đồ thị của đồthị.1.1.7. Cây bao trùm ngắn nhấta). Định nghĩa. Cho một đồ thị liên thông G vô hướng bao gồm nđỉnh, mã số từ 1 đến n, và m cạnh nối hai đỉnh với nhau. Mỗi cạnh có chiềudài cho trước. Tính liên thông của đồ thị cho biết với hai đỉnh cho trước tuỳ ýta luôn tìm được các cạnh gối đầu nhau để đi từ đỉnh này đến đỉnh kia. Hãychỉ ra một phần P của đồ thị thoả các tính chất sau: [3][4][7](i)P chứa tất cả các đỉnh của G;(ii)P chứa một số ít nhất các cạnh của G;(iii) P là đồ thị liên thông;(iv)Tổng chiều dài các cạnh của P là ngắn nhất.Đồ thị P thoả ba tính chất (i), (ii) và (iii) được gọi là cây bao trùm củađồ thị G. Nếu P thoả thêm tính chất (iv) thì P được gọi là cây bao trùm ngắnnhất của G.1644193592971086 421893989Hình 1. 6 Cây bao trùm nhỏ nhất trên đồ thị phẳngb). Tính chất cây bao trùm[7] Tính chất đa lời giải:11ABACBC4344D25E442FD7E5F41ABC42DE5FHình 1. 7 Cây bao trùm nhỏ nhất trong một đồ thịHình 1.7 thể hiện có thể có nhiều hơn một cây bao trùm nhỏ nhất trongmột đồ thị. Hai cây ở phía dưới đồ thị là hai cây bao trùm nhỏ nhất có thể cótừ đồ thị đã cho.17Có thể có một vài cây bao trùm nhỏ nhất có cùng trọng số và có sốcạnh nhỏ nhất; cụ thể hơn, nếu tất cả các cạnh của một đồ thị đều có trọng sốbằng nhau, thì tất cả các cây bao trùm của đồ thị đó đều là nhỏ nhất. Tính duy nhấtNếu mỗi cạnh có trọng số riêng biệt thì sẽ chỉ có một, và chỉ một câybao trùm nhỏ nhất. Có thể chứng minh phát biểu này bằng quy nạp hoặc phảnchứng. Điều này đúng trong nhiều trường hợp thực tế, như ví dụ về công tytruyền hình cáp ở trên chẳng hạn, khi đó rất hiếm khi hai con đường lại cóchính xác cùng một chi phí. Phát biểu này cũng được tổng quát hóa cho rừngbao trùm. Đồ thị có chi phí nhỏ nhấtNếu trọng số là số dương, thì một cây bao trùm nhỏ nhất cũng chính làđồ thị con có chi phí nhỏ nhất kết nối tất cả đỉnh, vì các đồ thị con có chứachu trình bao giờ cũng có tổng trọng số lớn hơn. Tính chất vòngVới một chu trình C bất kỳ trong đồ thị, nếu trọng số của cạnh e nào đócủa C lớn hơn trọng số của các cạnh còn lại của C, thì cạnh đó không thểthuộc về cây bao trùm nhỏ nhất. Giả sử điều ngược lại, nếu e thuộc về cây baotrùm nhỏ nhất T1 , khi chúng ta xóa e , nó sẽ phân T1 ra làm hai cây con màhai đầu của e thuộc về hai cây con khác nhau. Các cạnh còn lại của C sẽ gắnhai cây con này lại với nhau, do đó sẽ tồn tại một cạnh f thuộc C có hai đầunằm trên hai cây con này, tức là nó sẽ kết nối hai cây con này lại một cây T2có trọng số nhỏ hơn T1 , vì trọng số của f nhỏ hơn trọng số của e . Tính chất cắtT là cây bao trùm nhỏ nhất của đồ thị. Nếu S = {A,B,D,E}, thì V-S ={C,F}, sẽ có thể có 4 cạnh nối nhát cắt (S, V-S), đó là BC, EC, EF. Khi đó, e18là một trong các cạnh có trọng số nhỏ nhất của nhát cắt, vì vậy S {e} thuộcvề cây nhỏ nhất T.Với nhát cắt C bất kỳ trong đồ thị, nếu trọng số của một cạnh e của Cnhỏ hơn trọng số của các cạnh còn lại của C, thì cạnh này thuộc về tất cả cáccây bao trùm nhỏ nhất của đồ thị. Thực vậy, giả sử điều ngược lại, cạnh BC(có trọng số là 6) thuộc về cây bao trùm nhỏ nhất T thay vì cạnh e (trọng số 4)trong hình bên trái. Khi đó thêm e vào T sẽ tạo thành một chu trình, còn thayBC bằng e sẽ tạo ra một cây bao trùm nhỏ nhất có trọng số nhỏ hơn.61AB1ACBC4351DE112FD45E1F4Hình 1. 8 Cây bao trùm nhỏ nhất có trọng số nhỏ nhất Cạnh có chi phí nhỏ nhấtNếu một cạnh của đồ thị với chi phí nhỏ nhất e là duy nhất, thì cạnhnày sẽ thuộc về bất kỳ một cây bao trùm nhỏ nhất nào. Thật vậy, nếu e khôngnằm trong cây bao trùm nhỏ nhất, xóa một cạnh (có chi phí lớn hơn) trongchu trình tạo ra sau khi thêm e vào cây, sẽ tạo ra cây bao trùm có trọng số nhỏhơn.1.1.8. Cây bao trùm trên đồ thị có trọng sốTa xét những đồ thị vô hướng, có trọng số không âm và vớin(n  2) đỉnh.Giả sử G=( X, U )là một đồ thị có trọng số. Dùng C(G) để ký hiệu tậpgồm tất cả các cây bao trùm của đồ thị G ta xác định đại lượng:l 0 ( G )  m i n { l( H ) | H  C ( G )}(5)19Bài toán 1: Cho đồ thị vô hướng liên thông có trọng số G=(X, U), hãytìm một cây bao trùm có trọng số bé nhất H = (X, E) của đồ thị G màl ( H )  l0 ( G ) . Giải bài toán 1:Để tìm cây bao trum bé nhất của đồ thị G ta giữ lại lần lượt các cạnh bénhất. Đầu tiên ta giữ lại một trong những cạnh đầu tiên bé nhất. Ký hiệu cạnhđược giữ lại tại bước 1 là v1 và tập cạnh bước này là V1  {v1} .Sang bước thứ hai giữ lại một trong những cạnh có trọng số bé nhất, màchưa được giữ. Ký hiệu cạnh được giữ lại tại bước này là v2 và tập cạnh đãđược giữ lại là :V3  V2 {v2}={v1,v2}(6)Tại bước ba giữ lại một trong những cạnh có trọng số bé nhất trong cáccạnh còn lại, mà nó không lập với cách cạnh đã giữ thành chu trình. Ký hiệucạnh được giữ lại tại bước này là v3 và tập cạnh được giữ lại làV3  V2  {v3}={v1 ,v 2 ,v3} .Giả sử sau k bước ta giữ lại được tập cạnh là: Vk  {v1 ,v 2 ,...,v k 1 ,v1} .Sang bước k+1 ta giữ lại một trong những cạnh có trọng số bé nhấttrong các canh còn lại, mà nó không lập với các cạnh thuộc Vk thành chutrình. Ký hiệu cạnh được giữ lại tạ bước này bằng Vk 1 và tập cạnh giữ đượclại sau k+1 bước là:Vk 1  Vk  {Vk 1}={v1 ,v 2 ,...,v k ,v k 1}(7)Tiếp tục quá trình này cho tới khi không cạnh nào trong các cạnh cònlại của G đầu xuất hiện chu trình, theo tính chất 4 định lý 2 đồ thị H là mộtcây và nó là một trong những cây bao trùm của đồ thị G.Mặt khác theo tính chất 2 định lý 2 cây H phải có tới i  n  1 đỉnh.Định lý 6.20Nếu đồ thị G = (X, U) liên thông và có trọng số khác nhau từng đôimột, thì cây bao trùm H=(X, V n  1 ) với tập cạnh V n  1 được xác định là câybao trùm ngắn nhất và duy nhất.Chứng minh.Giả sử H 1 =(X, V) là cây bao trùm có trọng số bé nhất tuỳ ý của đồ thịG ta chứng minh rằng V= Vn1 .Nếu V  Vn1  {V1 ,V2 ,...., Vk 1 , Vk ,Vk 1 ,....,Vn2 ,Vn1} .Khi đó, do | V || Vn1 | n  1 , nên trong Vn1 phải có cạnh không thuộc V,giả sử v k là cạnh có chỉ số nhỏ nhất trong Vn1 không thuộc V theo tính chất 4định lý 2, thì phải có một và chỉ một chu trình  trong tập V  {v k } . Nếu chỉ gồm các cạnh thuộc Vn1 , thì khi đó Vn1 có chu trình, nên mâu thuẫn vớitính chất của Vn1 . Vậy  phải chứa ít nhất một cạnh không thuộc Vn1 . Giả sửu0   và u0  Vn1 .Đặt W  (V  (vk ))  {u 0 } . Đồ thị H 2 =(X,V) không chứa chu trình và cócạnh n-1 cạnh, nên theo tính chất 2 định lý 2 nó là một cây.Mặt khác, do k là chỉ số nhỏ nhất mà vk  V và u0 V nên. Do đó tậpVk 1  {u 0 } không chứa chu trình, nhưng cạnh u0 lại không được giữ lại, màvk được chọn. Bởi vậy l ( u 0 )  l ( v k ) .Cây H 2 =(X, W) nhận được từ cây H 1 =(X.W) bằng cách đổi u0 thành vk .Bởi vậy l ( H 2 )  l ( H 1 ) . Ta đã đi tới mâu thuẫn với tính chất trọng số bé nhấtcủa H1 . Do đó V= Vn 1 và cây bao trùm H  ( X ,Vn1 ) có trọng số bé nhất vàduy nhất.Đối với những đồ thị có trọng số không khác nhau từng đôi một từ địnhlý 6.Hệ quả

Tài liệu liên quan

Lý thuyết chọn mẫu và ứng dụng chọn mẫu trong kiểm toán
- 36
- 683
- 0
Lý thuyết chọn michael và ứng dụng
- 27
- 347
- 0
Lý thuyết độ đo và ứng dụng trong toán sơ cấp
- 21
- 696
- 1
Lý thuyết tích phân và ứng dụng
- 13
- 511
- 0
Nghiên cứu các thuật toán lý thuyết đồ thị và ứng dụng dạy tin học chuyên THPT
- 26
- 931
- 4
Lý thuyết cực trị và ứng dụng trong đo lường rủi ro tài chính
- 19
- 733
- 1
ĐỒ ÁN TỐT NGHIỆP Đề tài “Lý thuyết mạng Neuron và ứng dụng trong nhận dạng tiếng nói”
- 129
- 1
- 0
Tìm hiểu lý thuyết m dãy và ứng dụng của nó trong mật mã học
- 45
- 774
- 0
ĐỒ ÁN TỐT NGHIỆP Đề tài: “Lý thuyết mạng Neuron và ứng dụng trong nhận dạng tiếng nói.” ppt
- 129
- 903
- 1
LUẬN VĂN: Lý thuyết chọn mẫu và ứng dụng chọn mẫu trong kiểm toán pdf
- 32
- 577
- 1