Lịch sử của bài toán cây khung nhỏ nhất
Trong đồ thị vô hướng liên thông có trọng số G = (V, E), với V là tập đỉnh và E là tập cạnh, cây khung T là một phần của G có trọng số là tổng trọng số các cạnh trong T Bài toán cây khung nhỏ nhất yêu cầu tìm cây khung có trọng số nhỏ nhất trong số các cây khung của G Cây khung này được gọi là cây khung nhỏ nhất (minimum spanning tree).
Năm 1926, nhà toán học người Séc Otakar Boruvka mô tả một thuật toán giải
Ông Boruvka đã đề xuất các thuật toán tối ưu hóa mạng lưới điện, mặc dù vào thời điểm đó chưa có khái niệm về đồ thị và cây khung tối thiểu Thuật toán của ông được coi là thuật toán giải bài toán cây khung nhỏ nhất sớm nhất, và ngày nay được biết đến với tên gọi thuật toán Boruvka Trong luận văn, cây khung nhỏ nhất thường được viết tắt là "MST".
Vào năm 1930, nhà toán học Séc Jarn'ík đã phát hiện ra một thuật toán MST, sau đó được đề xuất độc lập bởi nhà toán học và khoa học máy tính Mỹ Prim vào năm 1957, và tái khám phá bởi nhà khoa học máy tính Hà Lan Dijkstra vào năm 1959 Thuật toán này thường được gọi là thuật toán Prim, thuật toán Jarn'ík, thuật toán Prim-Jarn'ík hoặc thuật toán DJP Trong luận văn này, chúng tôi sẽ sử dụng thuật ngữ thuật toán DJP.
Thuật toán Kruskal là một phương pháp trong lý thuyết đồ thị nhằm tìm cây bao trùm tối thiểu cho một đồ thị liên thông có trọng số Nó xác định một tập hợp các cạnh để tạo thành một cây bao gồm tất cả các đỉnh của đồ thị với tổng trọng số các cạnh là nhỏ nhất Là một ví dụ điển hình của thuật toán tham lam, Kruskal được giới thiệu lần đầu tiên vào năm 1956 bởi Joseph Kruskal.
Nhiều thuật toán cây bao trùm tối thiểu (MST) hiện đại đã áp dụng ý tưởng từ thuật toán Boruvka và kết hợp nhiều khái niệm từ cả hai thuật toán Mặc dù các bài toán MST đã được nghiên cứu sâu rộng kể từ khi các thuật toán này ra đời, vẫn chưa có cận dưới chính xác cho độ phức tạp thời gian của bài toán MST Thuật toán MST tối ưu được nghiên cứu trong luận văn này được thiết kế bởi Pettie và Ramachandran vào năm 2002, và các tác giả đã chứng minh rằng thuật toán hoạt động trong thời gian tối ưu, nhưng chưa thể đưa ra cận dưới chính xác thấp hơn Thông tin chi tiết về thuật toán này sẽ được trình bày ở chương 3.
Phần tiếp theo của chương này sẽ trình bày bài toán cây khung nhỏ nhất (MST) và tổng quan về các thuật toán quan trọng liên quan Đầu tiên, chúng tôi sẽ giới thiệu các ký hiệu toán học được sử dụng trong luận văn, cùng với một số kiến thức cơ bản về lý thuyết đồ thị.
Các ký hiệu toán học
Trong luận văn, ta sẽ sử dụng ký hiệu log = , đó là logarithm với cơ số 2
Với số nguyên , ký hiệu được định nghĩa quy nạp như sau: và =
Ký hiệu được định nghĩa là { | , thể hiện số lần các hàm logarithm cần áp dụng để đạt được kết quả Hàm số này có đặc điểm tăng rất chậm và luôn nhỏ hơn 6 cho tất cả các giá trị thực của
Giai thừa của một số nguyên dương n, kí hiệu là n!, được định nghĩa là
Hàm n! có thể định nghĩa đệ qui bởi: và !=( −1) Dễ dàng thấy là Đối với số nguyên không âm và hàm Ackermann 𝐴( , ) được định nghĩa đệ quy như sau:
Một tính chất quan trọng của 𝐴 là giá trị của nó tăng rất nhanh Gọi
Hàm Ackermann 𝐴′(n) = 𝐴(n, m) có tốc độ tăng trưởng rất nhanh, trong khi hàm nghịch đảo 𝐴 tăng trưởng chậm Hàm nghịch đảo của hàm Ackermann được ký hiệu là 𝛼(n), với 𝛼(n) luôn nhỏ hơn 5 cho mọi giá trị thực của n Hàm nghịch đảo Ackermann hai tham số được định nghĩa bởi 𝛼(m, n) = min{ k ≥ 1 | 𝐴(k, [m/n]) ≥ log n } Cần lưu ý rằng hàm 𝛼 tăng rất chậm Đối với các số nguyên m ≥ 0 và n ≥ 1, hàm 𝛽(m, n) được định nghĩa là 𝛽(m, n) = { k | m, nghĩa là 𝛽(m, n) là số lần các hàm logarithm được áp dụng đối với n để thu được kết quả là ≤ m/n.
Lý thuyết đồ thị
Đồ thị vô hướng G là một kiểu dữ liệu trừu tượng gồm tập đỉnh và tập cạnh, trong đó các cạnh là các cặp đỉnh không có thứ tự Ký hiệu số lượng đỉnh là |V| và số lượng cạnh là |E| Tập đỉnh được ký hiệu là V, và tập cạnh là E, với mỗi cạnh nối hai đỉnh v_i và v_j được ký hiệu là v_i v_j Mỗi cạnh trong đồ thị được gán một trọng số dương w, thể hiện chi phí sử dụng cạnh đó, với các cạnh nhẹ hơn hoặc nặng hơn tùy thuộc vào giá trị của w Trong các ví dụ trong luận văn, trọng số cạnh tương ứng với khoảng cách Euclide giữa các điểm đầu cuối, một giả định phổ biến trong các ứng dụng thực tế như mạng lưới đường bộ và điện Bậc của một đỉnh v, ký hiệu bởi deg(v), là số cạnh kề với nó Một đường đi trong đồ thị là một dãy các đỉnh và cạnh xen kẽ, bắt đầu từ một đỉnh và kết thúc tại một đỉnh khác, có thể được mô tả bởi dãy: v_1, v_2, v_3, , v_n.
Chu trình trong lý thuyết đồ thị được định nghĩa là một đường đi không có cạnh lặp lại, bắt đầu và kết thúc tại cùng một đỉnh, ký hiệu là 𝑣 𝑣 Đường đi được gọi là đơn nếu tất cả các đỉnh trên đó đều phân biệt Tương tự, chu trình đơn là chu trình mà các đỉnh đều phân biệt, ngoại trừ đỉnh bắt đầu và kết thúc.
Hình 1.1: Đơn đồ thị liên thông với 𝒏 và 𝒎
Hình 1.1 minh họa đồ thị G = (V, E) với các đỉnh {𝑣1, , 𝑣n} Dãy các cạnh trên đường đi được thể hiện bởi đoạn tô đậm 𝑣1𝑣2𝑣3𝑣4𝑣5𝑣6𝑣7𝑣8𝑣9, cho thấy một ví dụ về đường đi đơn Trong khi đó, dãy các cạnh trên chu trình đơn được thể hiện bởi đoạn gạch chấm 𝑣1𝑣2𝑣3𝑣4𝑣5𝑣6𝑣7𝑣8𝑣9𝑣10𝑣1.
Một đồ thị được coi là liên thông khi tồn tại đường đi giữa mọi cặp đỉnh Ngoài ra, khuyên được định nghĩa là một cạnh nối một đỉnh với chính nó, tức là cạnh có dạng vòng.
Cạnh trong đồ thị được tính hai lần nếu chúng nối cùng một cặp đỉnh, và hai cạnh được gọi là song song nếu chúng giống nhau Đồ thị chứa cạnh lặp được gọi là đa đồ thị, trong khi đồ thị có cả cạnh lặp và khuyên được gọi là giả đồ thị Đơn đồ thị là đồ thị vô hướng không có khuyên và cạnh lặp, với tập cạnh là tập hợp các bộ không có thứ tự gồm hai đỉnh Bậc lớn nhất của một đỉnh trong đơn đồ thị là bậc của nó, tức số đỉnh lân cận Đồ thị liên thông trong hình 1.1 là một ví dụ về đơn đồ thị, trong khi đồ thị không liên thông có thể có các thành phần liên thông cực đại.
Số lượng cạnh trong một đồ thị liên thông luôn lớn hơn hoặc bằng n-1, điều này cho thấy cây là loại đồ thị liên thông có ít cạnh nhất Đối với rừng, đây là đồ thị mà mỗi thành phần liên thông đều là một cây.
Đồ thị đầy đủ là một trường hợp đặc biệt của đồ thị liên thông, trong đó tất cả các cạnh có thể đều hiện diện Tổng số cạnh của đồ thị đầy đủ được tính bằng công thức \( C = \frac{n(n-1)}{2} \), với \( n \) là số đỉnh Đồ thị đầy đủ với \( n \) đỉnh được ký hiệu là \( K_n \).
Trong luận văn này, mật độ của một đồ thị được định nghĩa là tỷ lệ giữa số cạnh (m) và số đỉnh (n), được biểu thị bằng m/n Số cạnh m trong một đồ thị liên thông với n đỉnh phải thỏa mãn bất đẳng thức, do đó m nằm trong khoảng nhất định Đồ thị được gọi là thưa nếu mật độ nhỏ và dày nếu mật độ lớn, với khái niệm “nhỏ”/”lớn” sẽ được làm rõ trong các ứng dụng cụ thể Một trường hợp đặc biệt của đồ thị thưa là đồ thị phẳng, tức là đồ thị có thể vẽ trên mặt phẳng mà không có hai cạnh nào giao nhau ngoại trừ tại đỉnh Theo Định lý 1.3, đồ thị phẳng đơn liên thông với n đỉnh có tối đa 3n - 6 cạnh.
Đối với một đồ thị phẳng, mật độ của nó bị giới hạn bởi một hằng số, dẫn đến việc số lượng cạnh của đơn đồ thị liên thông có cận dưới Kích thước đầu vào của bất kỳ đơn đồ thị liên thông nào với cạnh là một yếu tố quan trọng Do đó, thời gian cần thiết để xây dựng một đơn đồ thị liên thông với cạnh cũng được xác định rõ ràng.
Cây khung nhỏ nhất
Một cây khung của đồ thị liên thông G là một cây chứa tất cả các đỉnh, với tập cạnh là tập con của tập cạnh của G Cây khung này bao trùm toàn bộ các đỉnh trong G Đối với một đồ thị liên thông có trọng số, T được định nghĩa là cây khung của đồ thị đó.
Trọng lượng của T được xác định bằng tổng trọng số của các cạnh trong T:
∑ Định nghĩa: Cho G là một đồ thị liên thông có trọng số Cây khung nhỏ nhất
(MST) của G là cây khung của G với trọng số là nhỏ nhất
MST, hay Cây Khung Tối Thiểu, là giải pháp cho các bài toán so sánh trọng số cạnh trong đồ thị Nếu trọng số các cạnh trong đồ thị là giống nhau, thì mọi cây khung của nó đều là MST, cho thấy có thể có nhiều cây khung nhỏ nhất Tuy nhiên, nếu trọng số các cạnh là phân biệt, tức là không có hai cạnh nào có cùng trọng số, thì cây khung nhỏ nhất sẽ là duy nhất.
Theo Định lý 1.4.1, trong một chu trình đơn của đồ thị liên thông có trọng số với trọng lượng cạnh phân biệt, cạnh nặng nhất trong chu trình đó sẽ không thuộc vào bất kỳ cây khung nhỏ nhất (MST) nào của đồ thị.
Giả sử cạnh nặng nhất e thuộc vào một cây khung tối thiểu (MST), khi xóa cạnh này sẽ tạo ra hai cây con tách rời Trong chu trình có các cạnh kết nối hai cây con khác nhau, và việc kết nối chúng bằng cạnh nặng nhất 𝑤 sẽ tạo ra một cây khung có trọng lượng nhỏ hơn Do đó, cạnh e không thể thuộc về một MST.
(a) Các thuộc tính chu kỳ Các cạnh đậm là
MST Các đường đứt minh họa của tách cây
(b) Các thuộc tính cắt Chỉ có các cạnh trong cắt được hiển thị
Hình 1.2: Các thuộc tính chu kỳ và các thuộc tính cắt cắt
Thuộc tính cắt trong lý thuyết đồ thị được định nghĩa qua một đồ thị với tập đỉnh Cho hai tập con không rỗng tạo thành phân hoạch của tập đỉnh, ký hiệu là và Nếu tập các cạnh có một đầu mút thuộc về và đầu mút kia thuộc về , thì ta có thể xác định thuộc tính cắt của đồ thị.
Trong đồ thị liên thông có trọng số với trọng lượng cạnh phân biệt, một lát cắt C được tạo thành có tính chất quan trọng: cạnh nhẹ nhất trong lát cắt này phải thuộc vào cây khung tối thiểu (MST) của đồ thị.
Giả sử 𝑢 và 𝑣 là hai đỉnh cuối của một cạnh nhẹ Nếu cạnh này là duy nhất trên đường đơn giữa 𝑢 và 𝑣, thì điều này chứng minh rằng tất cả các đỉnh trong đồ thị phải được kết nối trong một cây khung tối thiểu (MST) Ngược lại, nếu cạnh nhẹ nhất không thuộc về một MST, điều này sẽ tạo ra mâu thuẫn với định nghĩa về cây khung tối thiểu.
Trong một cây khung tối thiểu (MST), nếu tồn tại một cạnh giữa hai đỉnh 𝑢 và 𝑣, thì chúng sẽ được kết nối Nếu không có cạnh này, hai đỉnh sẽ không nằm trong MST Việc thay thế trọng số 𝑤 bằng một trọng số nhỏ hơn sẽ tạo ra một cây khung có trọng lượng giảm, do đó, cạnh này thuộc về MST.
Sử dụng hai thuộc tính trên, ta có thể chứng minh định lý 1.4.3: Trong một đồ thị liên thông có trọng số với trọng số cạnh khác biệt, nếu T là một cây khung tối thiểu (MST) và e là một cạnh bất kỳ, thì nếu trọng số của e nhỏ hơn trọng số của bất kỳ cạnh nào trong một lát cắt của T, e là cạnh nhẹ Ngược lại, nếu trọng số của e lớn hơn trọng số của bất kỳ cạnh nào trong một chu trình của T, e là cạnh nặng nhất.
Tính duy nhất Định lý 1.4.4: Một đồ thị liên thông có trọng số với trọng lượng số cạnh phân biệt có một MST duy nhất
Trong bài viết này, chúng tôi giả định rằng tất cả các đồ thị có trọng số cạnh đều khác nhau, dẫn đến việc mỗi đồ thị sẽ có một cây khung tối thiểu (MST) duy nhất.
1.4.2 Rừng trải rộng tối thiểu và những giả định đồ thị
Chúng tôi đã xác định các bài toán cây khung tối thiểu (MST) cho các đồ thị liên thông Thành phần liên thông là rất quan trọng, vì theo định nghĩa, không thể tồn tại cây khung cho các đồ thị không liên thông.
Rừng khung được xác định bởi sự kết hợp của cây khung cho mỗi thành phần liên thông trong đồ thị, trong khi rừng khung tối thiểu (MSF) là rừng khung với trọng số tối thiểu Bài toán MSF là một tổng quát của bài toán cây khung tối thiểu (MST) và có thể được giải quyết bằng cách tìm MST cho từng thành phần liên thông trong đồ thị Việc xác định các thành phần liên thông có thể thực hiện dễ dàng trong thời gian tuyến tính thông qua thuật toán tìm kiếm theo chiều sâu (DFS), sau đó giải quyết các bài toán MST cho từng thành phần đó.
Bài toán MST có thể được coi là một biến thể của bài toán MSF, với hai thuật ngữ này thường được sử dụng thay thế cho nhau do sự khác biệt không đáng kể Đối với bất kỳ đồ thị đầu vào nào không phải là đơn đồ thị, chúng ta có thể thực hiện một bước tính toán trước để loại bỏ các cạnh lặp và các khuyên Bước tính toán này có thể được thực hiện trong thời gian tuyến tính thông qua việc sử dụng thuật toán DFS để xây dựng 𝑡𝑟 𝑡.
Trong luận văn này, chúng tôi giả định là tất cả các đơn đồ thị và liên thông
Trong phần này, chúng tôi sẽ trình bày thời gian chạy của các thuật toán MST trong luận văn này, cũng như một số thuật toán quan trọng khác
Các thuật toán cây khung tối thiểu (MST) nhận đầu vào là đồ thị với các đỉnh và cạnh Đến nay, chưa có hàm nào mô tả chính xác độ phức tạp của bài toán MST cho đồ thị tổng quát Luận văn này sẽ chỉ ra rằng tồn tại một thuật toán có thể chạy với thời gian tối ưu dựa trên tổng số trọng lượng của các cạnh, mặc dù các hàm cho khái niệm "tối ưu" vẫn chưa được làm rõ.
Đối với mọi đồ thị có ít nhất 2 đỉnh, có thể xây dựng một đồ thị đơn mà mỗi cạnh thuộc ít nhất một chu trình đơn Để giải quyết bài toán cây khung nhỏ nhất (MST), mỗi cạnh cần được xử lý ít nhất một lần, dẫn đến cận dưới cho độ phức tạp của bài toán MST là Ω(n) Cận dưới tốt nhất hiện nay là α(n), với α(n) là nghịch đảo của hàm Ackermann, cho thấy độ phức tạp của bài toán MST "gần như tuyến tính" với kích thước đồ thị Năm 1995, Karger và cộng sự đã giới thiệu một thuật toán MST ngẫu nhiên với thời gian kỳ vọng là O(n log n), dựa trên giả định có quyền truy cập vào vô số bit ngẫu nhiên Tuy nhiên, bài viết này sẽ tập trung vào trường hợp xấu nhất của thời gian chạy cho các thuật toán xác định giải bài toán MST.
Các ứng dụng của bài toán MST
Cây bao trùm tối thiểu là công cụ quan trọng trong việc xây dựng lưới mạng, giúp kết nối các địa điểm với tổng chi phí dây nhỏ nhất Nghiên cứu và ứng dụng về cây bao trùm tối thiểu chủ yếu được thực hiện bởi các công ty truyền thông.
Khi một công ty truyền hình cáp lắp đặt cáp đến một khu phố mới, họ phải tuân theo các hạn chế về việc chôn cáp chỉ theo những con đường nhất định Điều này tạo ra một đồ thị với các điểm được kết nối qua những con đường Một số con đường có thể tốn kém hơn do chiều dài lớn hơn hoặc yêu cầu chôn sâu hơn Cây bao trùm cho đồ thị này là tập hợp các con đường không có chu kỳ nhưng vẫn kết nối đến từng nhà Có thể tồn tại nhiều cây khung, nhưng cây bao trùm tối thiểu sẽ phải có tổng chi phí thấp nhất.
1.5.2 Thiết kế mạch điện tử
Trong thiết kế mạch điện tử, việc nối dây các chân lại với nhau là cần thiết để đảm bảo có điện tương đương Một cây bao trùm tối thiểu cần phải sử dụng ít dây nhất có thể để kết nối một tập hợp các điểm.
Trong một dự án kết nối các hòn đảo bằng cầu, chính phủ mong muốn chi tiêu tối thiểu để đảm bảo việc di chuyển giữa các đảo Các kỹ sư có thể tính toán chi phí xây dựng cầu cho mỗi cặp đảo Tập hợp các cầu này sẽ tạo thành một mạng lưới cho phép di chuyển từ bất kỳ hòn đảo nào đến tất cả các đảo khác với chi phí thấp nhất, được gọi là cây bao trùm tối thiểu.
1.5.4 Clustering biểu hiện dữ liệu gen (Thuật phân nhóm dữ liệu biểu hiện gen)
Cây bao trùm tối thiểu cung cấp một phương pháp hiệu quả để phân nhóm các điểm trong không gian, như được mô tả bởi Ying Xu và cộng sự Họ đã phát triển một cấu trúc mới để biểu diễn dữ liệu biểu hiện gene đa chiều dưới dạng cây bao trùm tối thiểu, trong đó mỗi cụm dữ liệu tương ứng với một cây con của MST Điều này cho phép chuyển đổi bài toán phân nhóm đa chiều thành bài toán phân vùng cây mà không mất đi thông tin quan trọng Hai lợi thế chính của việc sử dụng MST là cấu trúc đơn giản giúp thực hiện thuật toán phân cụm hiệu quả và khả năng vượt qua các vấn đề mà các thuật toán phân nhóm cổ điển gặp phải Ngoài ra, phần mềm EXCAVATOR, viết tắt của “EXpression data Clustering Analysis and VisualizATiOn Resource,” đã được phát triển dựa trên khung công tác mới này, cho thấy kết quả phân nhóm hứa hẹn từ dữ liệu biểu hiện gene của Saccharomyces cerevisiae, phản ứng nguyên bào sợi huyết thanh của người, và Arabidopsis trong phản ứng với chitin.
1.5.5 Xấp xỉ dựa trên MST
Trong bài toán nhân viên bán hàng đi du lịch (TSP), chúng ta tìm kiếm một tour có trọng lượng tối thiểu trên đồ thị vô hướng hoàn chỉnh với hàm trọng lượng Bài toán này đã được chứng minh là NP-khó, ngay cả khi hàm trọng lượng thỏa mãn bất đẳng thức tam giác Các bất đẳng thức tam giác xuất hiện trong nhiều tình huống thực tế và có thể được xử lý bằng cách áp dụng một thuật toán xấp xỉ với tỷ lệ 2 Đầu tiên, cần tìm một cây khung tối thiểu (MST) cho đồ thị, sau đó tăng gấp đôi MST và xây dựng một tour Cuối cùng, thêm các đường tắt để đảm bảo không có đỉnh nào được truy cập nhiều hơn một lần, nhờ vào một bộ cây định trước Kết quả là chiều dài của các tour không vượt quá hai lần chiều dài tối ưu Phương pháp dựa trên MST cũng cho thấy hiệu quả trong việc cung cấp xấp xỉ tốt cho các bài toán cây Steiner.
Kỹ nghệ thuật toán (Algorithm Engineering)
Trong thời đại hiện nay, thuật toán đóng vai trò quan trọng trong mọi lĩnh vực, từ kinh tế đến công nghệ và khoa học Sự áp dụng của các thuật toán trong phần mềm không chỉ cải thiện hiệu suất mà còn ảnh hưởng sâu sắc đến cuộc sống hàng ngày của chúng ta.
Một số ngành nghề đặc biệt có sự liên quan chặt chẽ đến việc áp dụng các thuật toán bao gồm công nghệ sinh học, tìm kiếm thông tin, mạng lưới thông tin liên lạc, mật mã, hệ thống thông tin địa lý, xử lý và khôi phục thông tin từ hình ảnh, cũng như vận tải đa phương tiện.
Thuật toán học là một yếu tố quan trọng trong việc phát triển ứng dụng máy tính, tuy nhiên, khoảng cách giữa lý thuyết và thực tiễn ngày càng lớn Điều này dẫn đến việc chỉ một số ít thuật toán được áp dụng thực tế, gây ra những hạn chế trong ứng dụng công nghệ Để hiểu rõ hơn về vấn đề này, cần tìm hiểu quy trình nghiên cứu và phát triển thuật toán theo cách truyền thống.
Lý thuyết về thuật toán tập trung vào các vấn đề đơn giản và trừu tượng, với nhiều thuật toán được thiết kế và phân tích dựa trên các mô hình giả định từ máy trừu tượng Qua đó, thời gian chạy của các thuật toán trong trường hợp xấu nhất được đánh giá, giúp xác định chất lượng của thuật toán.
Trong khoa học máy tính, thời gian thực hiện và chất lượng lời giải là thước đo cho tính hiệu quả của thuật toán
Giải quyết các các vấn đề trừu tượng và mô hình máy trừu tượng (abstract machine) có những điểm đáng chú ý trên lý thuyết:
- Các thuật toán được thiết kế với các vấn đề như vậy có thể áp dụng trên nhiều ứng dụng cụ thể hóa trong các lĩnh vực khác nhau
Hầu hết các mô hình máy cổ điển có sự tương đương với thời gian sai khác không vượt quá đa thức, trong khi tác động của thuật toán chưa được phân tích một cách chi tiết.
- Trường hợp xấu nhất của thuật toán xảy ra không giống như trong thiết kế
- Cho phép các máy tính độc lập thực hiện thuật toán để có thể so sánh về trường hợp xấu nhất mà không cần trang bị gì thêm
Từ góc độ lý thuyết thuật toán, việc áp dụng thuật toán đóng vai trò quan trọng trong thiết kế và phát triển phần mềm Hiệu quả của các thuật toán này thường được đánh giá bởi các chuyên gia trong lĩnh vực ứng dụng tương ứng.
Trong những ngày đầu của việc phát triển thuật toán, các tiên phong như Knuth và Floyd đã đánh giá các thuật toán dựa trên tiêu chuẩn thực hành Quan điểm này đã làm thay đổi cách thiết kế thuật toán, đồng thời yêu cầu phát triển các cấu trúc dữ liệu tiên tiến để cài đặt các thuật toán một cách hiệu quả.
Trong 15 năm qua, nhiều nhà khoa học đã nhận thấy sự cần thiết ngày càng tăng trong việc thiết kế và phân tích dựa trên thực tế thông qua việc triển khai và thử nghiệm giữa lý thuyết và thực hành Để giải quyết vấn đề này, một nhóm các nhà nghiên cứu thuật toán đã bắt đầu tìm kiếm các giải pháp hiệu quả.
1.6.1.2 Nền tảng của Kỹ nghệ thuật toán
Cách tiếp cận thuật toán nhấn mạnh tầm quan trọng của việc thực thi và thí nghiệm bên cạnh phân tích và thiết kế Điều này dẫn đến khái niệm mới về Kỹ nghệ thuật toán, mở ra hướng đi mới trong việc phát triển và ứng dụng thuật toán.
Thomas Kuhn phân tích cấu trúc sự biến chuyển của khoa học và sử dụng các mô hình khái niệm để mô tả “sự kết hợp truyền thống của nghiên cứu khoa học” Ông cho rằng sự biến chuyển mô hình chỉ xảy ra khi mô hình cũ gặp khủng hoảng và không thể giải quyết các vấn đề mới Điều này đặt ra câu hỏi về các sự kiện cần một mô hình mới Dưới đây là một số ví dụ minh họa cho điều này.
Mô hình máy tính Von – Neumann ngày càng trở nên không phù hợp với thực tế trong các lĩnh vực như xử lý song song, pipelining, dự đoán trước, phân cấp bộ nhớ, bộ nhớ đệm, xử lý đa luồng, và các mô hình tính toán phân tán và song song.
Trong thiết kế thuật toán, mục tiêu chính là cải thiện đánh giá tiệm cận trong trường hợp xấu nhất và đảm bảo rằng kết quả của thuật toán gần giống như dự đoán Tuy nhiên, nhiều thuật toán và cấu trúc dữ liệu mới được phát triển thường thiếu tính thực tiễn, dẫn đến việc không chắc chắn về khả năng áp dụng của chúng Việc triển khai những thuật toán này trong thực tế thường gặp khó khăn lớn, khiến nhiều người ngần ngại thử nghiệm Hơn nữa, nghiên cứu thời gian chạy tiệm cận có thể che giấu các hằng số lớn, trong khi yêu cầu bộ nhớ cũng có thể rất cao, mặc dù bị giới hạn bởi đa thức.
- Như ví dụ cụ thể, chúng tôi có thể trích dẫn một số vấn đề trong thuật toán:
1 Rất nhiều (không phải tất cả) sơ đồ xấp xỉ thời gian đa thức (PTAS), chẳng hạn các sơ đồ của Aurora hoặc Mitchell cho bài toán người du lịch (TSP), có hệ số rất lớn
2 Robins và Zelikovsky trình bày một hệ thống thuật toán giải bài toán cây Steiner trong đồ thị với thời gian chạy là , trong đó là một tham số ảnh hưởng đến hiệu suất Đối với trường hợp lớn, thuật toán của họ đạt cận tỷ lệ tốt nhất hiện nay là 1.55 Để cải tiến tốt nhất mức xấp xỉ bảo đảm ở 1.598 bởi Hougardy và Prửmel, cần thiết phải chọn Ngoài ra, cũn cần hơn 217 thiết bị đầu cuối
3 Câu hỏi liệu một đa giác đơn có thể được tam giác hóa trong thời gian tuyến tính hay không là một trong những vấn đề chính trong hình học tính toán nhiều năm qua Năm 1990, vấn đề này cuối cùng đã được Chazelle giải quyết, ông đã đưa ra một thuật toán với thời gian tuyến tính khá phức tạp Theo những kiến thức chúng tôi biết thì thuật toán này chưa bao giờ được áp dụng
Mục tiêu và kết quả của Luận văn
Mục tiêu của luận văn này là mô tả và phân tích thuật toán MST tối ưu của Pettie và Ramachandran, đồng thời kiểm tra thời gian chạy của thuật toán này so với các thuật toán MST khác có độ phức tạp lý thuyết cao hơn Thuật toán MST tối ưu cơ bản là một phần quan trọng trong phương pháp thuật toán nổi tiếng, được trình bày trong các nghiên cứu của Fredman và Tarjan, Chazelle, cùng với Mares.
Chương 2 của luận văn này tập trung vào việc mô tả các phương pháp của Boruvka và Jarn'ík, trong khi Chương 3 trình bày và phân tích thuật toán MST tối ưu Thời gian chạy của thuật toán này được so sánh với các thuật toán MST khác trong Chương 4.
Chúng tôi đã tiến hành thử nghiệm thời gian chạy của thuật toán MST tối ưu và các thuật toán MST khác trên nhiều loại đồ thị Kết quả cho thấy thuật toán MST tối ưu có chi phí thời gian chạy cao hơn so với các thuật toán MST khác Điều này cho thấy rằng các ẩn hằng số trong đánh giá tiệm cận của thuật toán này chi phối thời gian chạy, và giá trị của chúng cao hơn so với các thuật toán khác.
Big-Oh có ảnh hưởng lớn đến thời gian chạy của thuật toán MST tối ưu trong các trường hợp đồ thị thực tế Cần lưu ý rằng có giới hạn về kích thước của đồ thị thử nghiệm mà chúng ta có thể tạo ra, do đó, điều này cũng áp dụng cho các đồ thị thử nghiệm của chúng tôi Tóm lại, giả thuyết này đã được xác nhận qua các thí nghiệm Thuật toán DJP thường nhanh nhất, trong khi thuật toán MST tối ưu thường có thời gian chạy chậm nhất.
Các thuật toán MST tối ưu của Pettie và Ramachandran không mang lại lợi ích cho việc giải quyết bài toán MST trong trường hợp đồ thị thực tế.
Khối xây dựng cơ bản
Hàng đợi ưu tiên là một kiểu dữ liệu trừu tượng quan trọng, lưu trữ các cặp (phần tử, khóa) liên kết với nhau Trong bài viết này, chúng tôi tập trung vào các hàng đợi ưu tiên được triển khai qua cây nhị phân sắp thứ tự, cụ thể là các đống min Đống là một cấu trúc cây với nút gốc, nơi các nút được sắp xếp theo thứ tự, đảm bảo rằng khóa của mỗi nút không lớn hơn khóa của các nút con Nhờ đó, nút gốc luôn chứa phần tử có khóa nhỏ nhất trong hàng đợi ưu tiên.
Ngoại trừ các Đống mềm đặc biệt, bài viết này không đề cập đến hàng đợi ưu tiên Tuy nhiên, chúng tôi sẽ tóm tắt các giao diện hoạt động phổ biến của hàng đợi ưu tiên.
𝒊𝒏𝒔𝒆𝒓𝒕(𝒆, 𝒌): Chèn phần tử e với khóa k vào hàng đợi
𝒇𝒊𝒏𝒅𝑴𝒊𝒏: Trả về phần tử với khóa tối thiểu trong hàng đợi
𝒅𝒆𝒍𝒆𝒕𝒆𝑴𝒊𝒏: Xóa và trả về phần tử với khóa tối thiểu trong hàng đợi
Giảm khóa của phần tử bằng cách sử dụng hàm decreaseKey(e, 𝜟) là một phương pháp quan trọng trong quản lý hàng đợi Để thực hiện hiệu quả, một số hàng đợi cần tham chiếu đến nút đang lưu trữ phần tử e trong hàng đợi.
Xóa phần tử khỏi hàng đợi bằng cách sử dụng lệnh delete(e) Để thực hiện hiệu quả, một số hàng đợi cần tham chiếu đến nút đang lưu trữ phần tử e trong hàng đợi.
𝒎𝒆𝒍𝒅(𝑸): Hợp nhất hàng đợi Q vào hàng đợi
Trong luận văn này, sẽ không cần xóa các phần tử tùy ý cũng không ghép chung đống Do đó, sẽ không cần các phép toán 𝑑 𝑙 𝑡 và 𝑙𝑑
Phép toán 𝑑 𝑙 𝑡 𝑀 của Đống mềm có thể trả về một phần tử sai do sự xuất hiện của các phần tử khóa lỗi Thời gian chạy của Đống mềm phụ thuộc vào tỷ lệ lỗi 0 < 𝜀 < 1/2, được khởi tạo với hàng đợi ưu tiên, và tỷ lệ lỗi này cũng ảnh hưởng đến giới hạn số lượng phần tử lỗi trong đống Bảng 2.1.1 thể hiện thời gian chạy của Đống nhị phân cổ điển, Đống Fibonacci cao cấp và Đống mềm, dựa trên số lượng phần tử trong đống.
Worst case Worst case Amortised Amortised
Bảng 2.1 Thời gian thực hiện của đống nhị phân, đống Fibonaccis, và Đống mềm
2.1.2 Kết nối đồ thị và sơ đồ tổng quát của các thuật toán MST
Các thuật toán cây khung mini (MST) được trình bày trong luận văn này bao gồm cả thuật toán tối ưu và việc sử dụng đồ thị kết nối Phần này sẽ tập trung vào mô tả phương pháp kết nối Đầu tiên, cần có định nghĩa về các ký hiệu: cho một đồ thị con của, đồ thị được tạo ra từ việc kết nối từng thành phần liên thông trong được ký hiệu là.
2.1.2.1 Sơ đồ của thuật toán MST tổng quát
Nhiều thuật toán cây khung nhỏ nhất (MST) hoạt động bằng cách lặp lại quá trình nhận diện các cạnh MST, sử dụng thuộc tính cắt trong định lý 1.4.2 để kết nối các cụm đỉnh riêng biệt cho đến khi tìm đủ các cạnh MST Mỗi cụm ban đầu được xác định là một đỉnh riêng lẻ, và khi một cạnh MST mới được phát hiện, nó sẽ được thêm vào tập hợp các cạnh MST Các cụm tương ứng với hai đỉnh của cạnh đó sẽ được kết hợp thành một cụm mới, tạo thành một thành phần liên thông của các cạnh MST Quá trình này đảm bảo rằng mỗi lần lặp của vòng lặp bên ngoài tương ứng với một lần lặp duy nhất trong việc xây dựng MST.
Thuật toán 2.1.1: Thuật toán MST tổng quát foreach đỉnh v của G do xác định cụm C(v) {v}
T tất cả các đỉnh của G while |E(T)| < |V(G)| − 1 do
Tìm một số cạnh MST ( , 𝑏), với ( )≠ (𝑏)
Hợp nhất cụm ( ) và (𝑏) vào một cụm return T Điều kiện 𝑏 là rất quan trọng do đặc tính chu trình MST ( Định lý
Một nhược điểm của phương pháp này là các đồ thị có kích thước giống nhau trong tất cả các lần lặp, dẫn đến việc một số cạnh 𝑏 có thể không thuộc về cây khung tối thiểu (MST) do tính chất chu kỳ Để khắc phục điều này, chúng ta cần loại bỏ các cạnh không cần thiết bằng cách kết nối mọi thành phần liên thông của cây MST ở cuối mỗi lần lặp Bằng cách này, mỗi đỉnh mới sẽ được kết nối với một thành phần liên thông trước đó, cho phép chúng ta "thiết lập lại" các cụm trước mỗi lần lặp, đảm bảo rằng mỗi đỉnh tương ứng với một cụm riêng biệt.
2.1.2.2 Thủ tục kết nối đơn giản
Với kết nối ở cuối mỗi lần lặp, của các thuật toán Boruvka và Thuật toán
Trong trường hợp đồ thị dày, không cần xác định rõ ràng các cụm riêng biệt Các thuật toán có thể tự hạn chế chỉ đánh dấu một cạnh MST khi phát hiện mà không cần thêm vào Điều này giúp dễ dàng kiểm tra xem một cạnh đặc biệt có nằm trong MST hay không Chúng tôi sẽ mô tả sự kết nối cho đồ thị không có các cụm liên kết, với sự kết nối được đạt được như đã nêu trong chương này.
Phát hiện các thành phần liên thông thông qua các cạnh của cây khung tối thiểu (MST) được gán nhãn, cho phép gán cho mỗi đỉnh các thành phần mà nó thuộc về Phương pháp này là một cách tiếp cận chậm để phát hiện các cụm trong dữ liệu.
• Xây dựng một đồ thị kết nối mới ′ với:
1) Một đỉnh cho mỗi thành phần
2) Một cạnh cho mỗi cạnh kết nối các thành phần khác nhau Mỗi cạnh mới phải có một tham chiếu đến các cạnh trong đồ thị ban đầu liên quan
• Thêm các cạnh MST được gán nhãn vào Điều này có thể làm đồng thời với một trong hai bước khác
Cuối mỗi lấn lặp, chúng ta kết nối đồ thị thành một đồ thị nhỏ hơn, trong đó các thành phần liên thông được kết nối bằng các cạnh MST đã được gán nhãn, tương ứng với các cụm trong thuật toán gốc Đồng thời, một số cạnh không thuộc MST sẽ bị loại bỏ, cụ thể là tất cả các cạnh có cả hai điểm đầu cuối nằm trong cùng một thành phần.
Tìm kiếm theo chiều sâu và phát hiện của các thành phần được kết nối
Duyệt đồ thị là phương pháp kiểm tra toàn bộ các đỉnh và cạnh trong đồ thị, trong đó Depth-First Search (DFS) là một kỹ thuật duyệt chuẩn được sử dụng phổ biến.
Thuật toán Duyệt DFS có thể được sử dụng để phát hiện các thành phần liên thông trong một đồ thị và gán một số thành phần duy nhất cho mỗi đỉnh Đầu tiên, tất cả các đỉnh được đánh dấu là chưa được xét và thiết lập biến số thành phần tổng quát bằng 0 Tiếp theo, thuật toán lặp lại việc tìm một đỉnh chưa được xét, chọn đỉnh 𝑣, và gọi hàm DFS mở rộng trên 𝑣, đồng thời tăng biến thành phần tổng quát lên một Trong quá trình thực hiện DFS đệ quy, thuật toán sẽ kết hợp số thành phần với đỉnh hiện tại Để tìm một đỉnh chưa được xét một cách hiệu quả, cần duy trì tham chiếu đến đỉnh chưa được xét đầu tiên trong danh sách các đỉnh.
Bên cạnh đồ thị kết nối, chúng ta có thể tổng quát các thuật toán cho một MSF bằng cách điều chỉnh các điều kiện lặp của thuật toán Khi tìm thấy một thành phần liên thông của MST, các thành phần này kết nối với một đỉnh duy nhất, dẫn đến việc đồ thị có một tập cạnh trống Do đó, các điều kiện vòng lặp mới sẽ là khi đồ thị hiện tại có một tập cạnh khác rỗng.
Khối xây dựng nâng cao
2.2.1 Thuật toán "Trường hợp đồ thị dày"
Thuật toán MST tối ưu cần có khả năng tìm cây khung tối thiểu (MST) cho đồ thị dày trong thời gian tuyến tính Giới hạn dưới Ω(log) của mật độ trong thuật toán DJP gốc quá cao cho mục tiêu này Tuy nhiên, đã có nhiều thuật toán xác định khác nhau có thể đạt được thời gian chạy tuyến tính cho các đồ thị dày, đặc biệt khi sử dụng cấu trúc dữ liệu đống Fibonacci.
Theo mục 2.1.5.2, các phát hiện từ đống Fibonacci cho thấy thời gian chạy của thuật toán DJP giảm xuống còn (log + ) Một kết quả quan trọng hơn là sự tồn tại của một thuật toán với độ phức tạp MST, đạt được cho các đồ thị "đủ dày".
Thuật toán cho đồ thị dày là một phiên bản cải tiến của thuật toán DJP, sử dụng đống Fibonacci làm hàng đợi ưu tiên Mục tiêu chính là giới hạn số lượng đỉnh lân cận trong đống đến một giá trị tối đa k, và hàm cho k sẽ được trình bày trong Mục 2.2.1.2 Khi một đỉnh được lấy từ hàng đợi, nó sẽ được đánh dấu là đã chết, cho thấy nó thuộc về một cây đã phát triển Nếu đống vượt quá giới hạn k hoặc kết nối với một cây đã phát triển trước đó, thuật toán DJP sẽ được lặp lại với đỉnh sống là đỉnh gốc Quá trình này tiếp tục cho đến khi tất cả các đỉnh được đánh dấu chết, tức là tất cả đều thuộc về một cây Khi tất cả đỉnh đã chết, các thành phần liên thông từ các cạnh MST sẽ được kết nối, và mỗi cây phát triển sẽ trở thành một thành phần liên thông, kết nối vào một đỉnh duy nhất Thuật toán sẽ lặp lại cho đến khi toàn bộ các cạnh MST được tìm thấy, tương đương với việc kết nối các đồ thị thành một đồ thị không có cạnh nào.
Thuật toán cho trường hợp đồ thị dày sử dụng một phiên bản sửa đổi của các thuật toán DJP, cụ thể là hàm growTree(𝑣) Hàm này không khởi tạo hàng đợi ưu tiên hay khóa cho mỗi đỉnh, mà sử dụng các đỉnh 𝑣 sống làm gốc 𝑣 Khi một đỉnh chết được lấy từ hàng đợi, quá trình sẽ dừng lại nếu không được đánh dấu là chết Trước khi thêm một đỉnh vào đống, nếu đống đã đầy (kích thước k), quá trình cũng sẽ dừng GrowTree sẽ dừng lại khi nó kết nối với cây khác, khi các đống bị tràn, hoặc khi đống là trống rỗng Thuật toán cho "trường hợp đồ thị dày" được mô tả trong thuật toán 2.1.6.
Thuật toán 2.1.6: Thuật toán MST trường hợp đồ thị dày rừng gồm tất cả các đỉnh của while ( ) > 0 do
Tính toán k cho lần lặp này /* sẽ được lựa chọn trong mục 2.2.1.2 */
Thiết lập Đống Fibonacci với giới hạn forall đỉnh 𝑣 ( ) do Đánh dấu 𝑣 tồn tại Khóa (𝑣) while có một đỉnh v tồn tại do
Phát triển (𝑣) Heap rỗng forall chèn đỉnh 𝑣 do khóa 𝑣 kết nối ( , ) return
Sử dụng các dữ kiện sau đây với thuật toán, chúng ta có thể giới hạn số lượng các phép toán duyệt cho mỗi đống:
• Đỉnh sống duy nhất liền kề đỉnh cuối cùng được đưa vào đống hoặc khóa của chúng giảm
• Mỗi đỉnh được đánh dấu chết khi nó được xóa khỏi đống
• Các đỉnh đầu tiên xóa trong growTree là còn sống Đỉnh này là 𝑣
Giả sử 𝑡 = | ( )|, đó là số đỉnh của đồ thị kết nối khi bắt đầu duyệt Số phép toán chèn và giảm khóa tối đa là 2, với một lần cho mỗi điểm đầu cuối Tổng số phép toán deleteMin bao gồm số đỉnh sống xóa và số đỉnh chết xóa, trong đó số đỉnh sống xóa là 𝑡 Khi một đỉnh chết bị xóa, quá trình growTree dừng lại và khởi động lại, dẫn đến việc đỉnh tiếp theo sẽ là đỉnh sống Điều này cho thấy số đỉnh chết xóa không vượt quá 𝑡 Tổng số phép toán 𝑑 𝑙 𝑡 𝑀 trên một đống kích thước tối đa là (𝑡) Thời gian khởi tạo cho một lần duyệt là (𝑡) và các bước kết nối cũng tốn thời gian ( ) Việc quản lý đỉnh chèn được thực hiện bằng cách gán các đỉnh vào danh sách khi chèn Chi phí cho đống rỗng và đặt lại khóa được tính vào các phép toán chèn Để tìm một đỉnh gốc trực tiếp, chúng ta duy trì một tham chiếu đến đỉnh sống đầu tiên trong danh sách Khi cần tìm một đỉnh sống mới, ta lặp qua danh sách cho đến khi tìm thấy Tổng thời gian cho mỗi lần lặp là (𝑡), và nếu các đống Fibonacci bị giới hạn ở k, tổng thời gian cho một lần lặp hoàn chỉnh sẽ là (𝑡log( ) + + 𝑡) = (𝑡log( ) + ).
Giá trị nhỏ hơn k sẽ giảm thời gian thực hiện mỗi lần lặp nhưng tăng số lượng các lần lặp, trong khi giá trị lớn hơn sẽ làm giảm số lượng các lần lặp nhưng tăng thời gian thực hiện mỗi lần Giá trị nhỏ hơn ⌈ / 𝑡⌉ thường không được thực hiện do cây cuối cùng không phát triển vì tràn đống trong bước lặp đầu tiên của mỗi growTree Ngược lại, giá trị lớn hơn hoặc bằng 𝑡 sẽ khiến một lần lặp trở thành lần lặp cuối cùng vì không đủ chỗ cho tất cả các cây trong đống, làm cho lần lặp này giống với thuật toán DJP gốc Do đó, nếu giá trị ≥ trong lần lặp đầu tiên, thuật toán sẽ hoàn toàn tương tự như DJP.
Trong đống Fibonacci, các hàm được chọn cho quá trình lặp với đỉnh đầu vào 𝑡, trong đó tập hợp là số lượng các cạnh ban đầu Mỗi lần lặp tiêu tốn thời gian 𝑡, dẫn đến việc mỗi lần lặp mất thời gian tuyến tính theo số lượng cạnh của đồ thị ban đầu Khi số lượng đỉnh giảm dần qua các lần lặp, giá trị của 𝑡 sẽ tăng lên theo từng lần lặp.
Một giới hạn trên về số lần lặp là cần thiết để bắt đầu từ 𝑡 = 1 trong trường hợp xấu nhất, với điều kiện đồ thị đầu vào phải liên thông.
Một cây mới dừng tăng khi:
Việc vi phạm giới hạn kích thước đống của các đỉnh liền kề đồng nghĩa với việc tồn tại ít nhất một đỉnh bên ngoài Điều này dẫn đến việc có ít nhất một cạnh với ít nhất một điểm cuối trong, cụ thể là mỗi đỉnh kề đều có ít nhất một cạnh.
• Các đống là trống rỗng, tương đương với và không thể phát triển lớn hơn
Cây ′ được kết nối với một cây chết, trong đó cây này là một phần của cây chung đã phát triển từ các kết nối trước đó Tùy chọn này không khả thi khi cây đầu tiên trong một lần lặp ngừng phát triển Do đó, cây ′ có ít nhất một cạnh nối với ít nhất một điểm cuối trong cây ′, dẫn đến việc kết quả chung tạo thành một cây của ′.
Chúng tôi giả định rằng một cây là sự kết hợp của một hoặc nhiều cây phát được kết nối bởi growTree Nếu quá trình lặp kết thúc với một cây duy nhất của các cạnh MST, đó là lần lặp cuối cùng vì nó chỉ kết nối với một đỉnh Ngược lại, một lần lặp sẽ kết thúc khi mỗi cây có ít nhất một cạnh với ít nhất một điểm cuối Giả sử 𝑡 là số đỉnh và ′ là số cạnh khi bắt đầu lần lặp, tổng số điểm cuối cạnh là 2 ′ Số lượng cây sau lần lặp sẽ là 𝑡′ ≤ 2 ′/ và kích thước đống ràng buộc cho các lần lặp tiếp theo cũng sẽ bị ảnh hưởng Do đó, với điều kiện 𝑡′ ≤ 2 ′/ và ′ ≤ , ta có 2 /𝑡′ ≥ 2 /(2 ) ≥ , dẫn đến ′ ≥ 2 Điều này cho thấy rằng số lượng cây sẽ tăng lên theo cấp số nhân giữa mỗi lần lặp.
Trong lần lặp đầu tiên của thuật toán DJP, cây sẽ không ngừng phát triển cho đến khi chứa tất cả các đỉnh, miễn là kích thước đống không bị giới hạn Khi đạt đến điều kiện ≥ , đây sẽ là lần lặp cuối cùng Để phân tích số lượng tối đa các lần lặp cần thiết, chúng ta cần tìm thời gian tối thiểu để tăng giá trị ban đầu bằng trước khi đạt điều kiện ≥ Số lần lặp lại hàm logarit cần thiết để giá trị này nhỏ hơn hoặc bằng với giá trị ban đầu sẽ xác định số lượng tối đa các lần lặp cần thiết, được chặn bởi { |
Số lượng tối đa các lần lặp cần thiết là
Trong nghiên cứu [8], các tác giả đã xác định giá trị 𝛽 Kết quả cho thấy số lần lặp tối đa cần thiết để đạt được kết quả là 𝛽( , ) + (1) Mỗi lần lặp tiêu tốn thời gian ( ), do đó tổng thời gian chạy sẽ là ( 𝛽( , )).
Có thể nhận thấy rằng 𝛽( , ) có thể được diễn đạt qua các "logarithm lặp" hay hàm "log-star" Điều này cho thấy rằng biểu thức tối thiểu kết hợp với phần còn lại sẽ trở thành một dạng đơn giản hơn.
Trường hợp tồi nhất và thời gian tính tuyến tính
Số lượng lần lặp 𝛽 không phụ thuộc trực tiếp vào các yếu tố như mật độ đồ thị (tỷ lệ ghép cạnh với đỉnh) Chúng tôi giả định rằng các đồ thị là đơn và liên thông Nếu < , thì = −1 và đồ thị trở thành một cây, do đó không cần thiết phải chạy thuật toán này Mật độ cao thường dẫn đến thời gian thực hiện thấp hơn, trong khi trường hợp xấu nhất xảy ra khi = ⇒ / = 1, khiến 𝛽 trở thành một yếu tố quan trọng Trường hợp tốt nhất là đồ thị đầy đủ, khi đó 𝛽( , ) = (1), cho thấy thời gian thực hiện tồi nhất cho thuật toán là Ngược lại, thuật toán có thể hoạt động trong thời gian tuyến tính ( ) cho các đồ thị đủ dày, điều này rất có lợi cho các thuật toán MST tối ưu.
