Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p6

Tham khảo tài liệu giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình poisson với tham số p6, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p6Thuật toán Prim dựa trên những định lý sau đây: Định lý 4.4. Một cây là một MST nếu và chỉ nếu cây đó chứa cạnh ngắn nhất trong mọi cutset chia các nút thành hai thành phần.Để thực hiện thuật toán Prim, cần phải theo dõi khoảng cách từ mỗinút không thuộc cây tới cây và cập nhật khoảng cách đó mỗi khi cómột nút được thêm vào cây. Việc đó được thực hiện dễ dàng; đơngiản chỉ là duy trì một dãy d_tree có các thông tin về khoảng cách đãnói ở trên. Quá trình đó tuân theo: array[n] Có thể thấy rằng độ phức tạp của thuật toán này là O(n2); cả hai hàmFindMin v à Scan có độ phức tạp là O(n) và mỗi hàm được thực hiệnn lần. So sánh với thuật toán Kruskal ta thấy rằng độ phức tạp củathuật toán Prim tăng nhanh hơn so với độ phức tạp của thuật toánKruskal nếu m, số lượng các cạnh, bằng O(n2),còn nếu m có cùng bậcvới n thì độ phức tạp của thuật toán Kruskal tăng nhanh hơn.Có thể tăng tốc thuật toán Prim trong trường hợp graph là một graphmỏng bằng cách chỉ quan tâm đến các nút láng giềng của nút i vừađược thêm vào cây. Nếu sẵn có các thông tin kề liền, vòng lặp fortrong Scan có thể trở thành. for each (j , n_adj_list[i] )Độ phức tạp của Scan trở thành O(d) với d là bậc của nút i. Chính vìthế độ phức tạp tổng cộng của Scan giảm từ O(n2) xuống O(m).Thiết lập một tập kề liền cho toàn bộ một graph là một phép toán có độphức tạp bằng O(m): index[nn,list] Hình 4.2. Graph có liên kết song song và self loop Bảng 4.1 Nút init. A C E B D A 0 0(-) 0(-) 0(-) 0(-) 0(-) B 100 10(A) 10(A) 10(A) 10(A) 10(A) C 100 2(A) 2(A) 2(A) 2(A) 2(A) D 100 100(-) 11(A) 11(A) 5(B) 5(B) E 100 7(A) 6(C) 6(C) 6(C) 6(C)Ví dụ 4.4:Trở lại hình 4.4, giả sử rằng các cạnh không được biểu diễn có độ dàibằng 100. Thuật toán Kruskal sẽ chọn (A, C), (B, D), (C, E), và loại (A,E) bởi vì nó tạo ra một chu trình với các cạnh đã được chọn là (A, C)và (C, E), chọn (A, B) sau đó dừng lại vì một cây bắc cầu hoàn toàn đãđược tìm thấy.Thuật toán Prim bắt đầu từ nút A, nút A sẽ được thêm vào cây. Tiếptheo là các nút C, E, B v à D. Bảng 4.1 tổng kết các quá trình thực hiệncủa thuật toán Prim, biểu diễn d_tree và pred khi thuật toán thựchiện. Cuối thuật toán, pred[B] là A, tương ứng với (A, B) là mộtphần của cây. Tương tự, pred chỉ ra (A, C), (B, D) và (C, E) là cácphần của cây. Vì vậy, thuật toán Prim sẽ lựa chọn được cây giống vớicây mà thuật toán Kruskal nhưng thứ tự các liên kết được lựa chọn làkhác nhau.Một đường đi trong một mạng là một chuỗi liên tiếp các liên kết bắt đầutừ một nút s nào đó và kết thúc tại một nút t nào đó. Những đường đinhư vậy được gọi là một đường đi s, t. Chú ý rằng thứ tự các liên kếttrong đường đi là có ý nghĩa. Một đường đi có thể là hữu hướng hoặcvô hướng tuỳ thuộc vào việc các thành phần của nó là các liên kết haylà các cung. Người ta gọi một đường đi là đường đi đơn giản nếukhông có nút nào xuất hiện quá hai lần trong đường đi đó. Chú ý rằngmột đường đi đơn giản trong một graph đơn giản có thể được biểu 59diễn bằng chuỗi liên tiếp các nút mà đường đi đó chứa vì chuỗi các nútđó biểu diễn duy nhất một chuỗi các liên kết .Nếu s trùng với t thì đường đi đó gọi là một chu trình, và nếu một núttrung gian xuất hiện không quá một lần thì chu trình đó được gọi làchu trình đơn giản. Một chu trình đơn giản trong một graph đơngiản có thể được biểu diễn bởi một chuỗi các nút liên tiếp.Ví dụ 4.5:Xét graph hữu hướng trong hình 4.4. Các thành phần liên thông bềnđược xác dịnh bởi {A B C D} {E F G} {H} {I} {J}Các cung (A, H), (D, I), (I, J) và (J, G) không là một phần một thànhphần liên thông bền nào cả. Xem graph trong hình 4.3 là một graph vôhướng (nghĩa là xem các cung là các liên kết vô hướng), thì graph nàycó một thành phần duy nhất, vì thế nó là một graph liên thông.Cho một graph G = (V, E), H là một graph con nếu H = (V, E), trongđó V là tập con của V and E là tập hợp con của E. Các tập con này cóthể có hoặc không tuân theo quy định đã nêu. Hình 4.4. Graph hữu hướngMột graph không hề chứa các chu trình gọi là một cây. Một cây bắccầu là một graph liên thông không có các chu trình. Những graph nhưvậy được gọi một cách đơn giản là cây. Khi graph không liên thônghoàn toàn được gọi là một rừng. Chúng ta thường đề cập các câytrong các graph vô hướng.Trong các graph hữu hướng, có một cấu trúc tương tự với cây gọi làcây phân nhánh. Một cây phân nhánh là một graph hữu hướng cócác đường đi từ một nút (gọi là nút gốc của cây phân nhánh) tớitất cả các nút khác hoặc nói một cách khác là graph hữu hướng có các 60đường đi từ tất cả các nút khác đến nút gốc. Một cây phân nhánh sẽtrở thành ...