Chương 1 GIỚI THIỆU TÔNG QUAN 1.1 Lịch sử của bài toàn cây khung nhỏ nhất Cho G = (V, F) ("la tập đỉnh, Z là tập cạnh) là đỗ thị vô hướng liên thông có trọng số trên cạnh w(£),e € R. Giả sử 7 là một cây khung của Ớ, ta gọi trọng số của cây 7 là tổng trọng số các cạnh trong 7, li toản đặt ra là trong số các cây khung của Ơ, hãy tìm cây khung có trọng số nhỏ nhật. Cây khung như vậy được gọi là cây khung nhỏ nhất của dỏ thị (ainnnum spanning, tree) và bài toán dặt ra được gọi là bài toán cây khung nhỏ nhất. Nam 1926, nhà toán học người Séc Otakar Boruvka mô tả một thuật toán giải “một số bài toán cực tiêu hoá" [4].
Ông đã để xuất các thuật toán để tôi ưu hoá mang lưới điện. Vào thời Bơravka chưa có các khát mệm về đỗ thị và cây khimg tối thiểu. 'Thuật toán cúa ông là thuật toán giải bài toán cây khung nhỏ nhất được biết đến sớm. Thất, Ngày nay thuật toán này được gọi là thuật toán của Boruvka.
Trong luận vn, cây khung nhỏ nhất được gọi tắt là "MST", Năm 1930, một thuật toán MST khác dược phát hiện bởi nhà toán học Séc Jarnnk [9]. Thuật toán nảy được đề xuất độc lập bởi nhà toán học vá khoa hoc may tính người Mỹ Prim vào nấm 1957, và sau đó tái khám phá bởi các nhà khoa học máy tinh Ha Lan Dijkstra trong năm 1959, Do dỏ, thuật toán đồi khi dược gọi là thuật toán: của Prim, thuật toán của Jarnlik, thuật toán Prim-Jamik: hoặc thuật toán DỊP. Trong, luận văn này, chúng tôi gọi thuật toán này là thuật toán DỊP. Thuật toán Kruskal là một thuật toán trong lý thuyết để thị để tìm cây bao trùm tối [ểu của một đỏ thị liên thông có trọng số.
Noi ách khác, nó tìm một tập hợp các cạnh tạo thành một cây chứa tất cả cáo đỉnh của để thị và có tổng trọng số. các cạnh là nhỏ nhất. Thuật toán Kruskal là một ví đụ của tuiật toán tham lam Thuật †oán nay xuất bản lan dau tiên năm 1956, béi Joseph Kruskal Nhiéu thuat toán MST hiện dại sử dụng, các ý tưởng từ thuật toán Boruvka và DỊP. Cụ thể là các thuật toán MST tối ưa được nghiên cửu trong luận văn này sử 1.
Cây khưng nhỏ nhất. Định nghĩa: Cho G là một dễ thị liên thông. Một cây lung của 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 Œ. Nói cách khác cây khung là một cây bao trùm tat cd cde dink trong G.
Bink nghĩa: Cho T là một câu khung của một đồ thị liên thông có trọng số. Trọng lượng của †' được xác định bằng tông trọng số của các cạnh trong T: ø(T) = >3 ole) erFŒ) Tịnh nghĩa: Cho Œ là một đồ thị liên thông có trọng số. Câu khung nhồ nhất (AST) của G là cây khung của G với trọng số là nhà nhất. Rõ ràng là từ dịnh nghĩa, MST là một lời giải cho các bài toán trong dỏ đòi hồi 'phải so sánh các trọng số cạnh.
Mếu đỗ thị có trọng số các cạnh lá bằng nhau thì mọi cây khung của nó đêu là MST. Vỉ dụ này che thây đề thị có thế có nhiều cây khưng nhỏ nhất, Tuy nhiên, trong phần tiếp theo ta sẽ thấy là nếu một dỗ thị sỏ trọng só các cạnh là phân biệt (tức la không có hai cạnh nao cd cing trong số), thì cây khung nhỏ nhất của nó là đuy nhất 1.1 Một số tính chất 'TThuộc tính chu trình Pink ly 1.1: Déi với mỗi chủ trình đan 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 chủ trình không thuộc bất cứ một MST nào của G. Chúng mình: Xem Tĩnh 12a Giả sử ngược lại, túc là cạnh nặng nhất e thuộc một MST. Xóa e từ một MST sẽ chia thảnh hai cây con tách rồi với hai điểm cuối của e trong cây con kháe nhau.
Có tổn tại một số cạnh ƒ z ø trong, chu trình với các đầu cuốt trong hai cây con khác nhau. Bởi vì w(ƒ) < w(e), kết nỗi hai cây con lại 1. Cây khưng nhỏ nhất. Định nghĩa: Cho G là một dễ thị liên thông.
Một cây lung của 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 Œ. Nói cách khác cây khung là một cây bao trùm tat cd cde dink trong G. Bink nghĩa: Cho T là một câu khung của một đồ thị liên thông có trọng số. Trọng lượng của †' được xác định bằng tông trọng số của các cạnh trong T: ø(T) = >3 ole) erFŒ) Tịnh nghĩa: Cho Œ là một đồ thị liên thông có trọng số.
Câu khung nhồ nhất (AST) của G là cây khung của G với trọng số là nhà nhất. Rõ ràng là từ dịnh nghĩa, MST là một lời giải cho các bài toán trong dỏ đòi hồi 'phải so sánh các trọng số cạnh. Mếu đỗ thị có trọng số các cạnh lá bằng nhau thì mọi cây khung của nó đêu là MST. Vỉ dụ này che thây đề thị có thế có nhiều cây khưng nhỏ nhất, Tuy nhiên, trong phần tiếp theo ta sẽ thấy là nếu một dỗ thị sỏ trọng só các cạnh là phân biệt (tức la không có hai cạnh nao cd cing trong số), thì cây khung nhỏ nhất của nó là đuy nhất 1.1 Một số tính chất 'TThuộc tính chu trình Pink ly 1.1: Déi với mỗi chủ trình đan 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 chủ trình không thuộc bất cứ một MST nào của G.
Chúng mình: Xem Tĩnh 12a Giả sử ngược lại, túc là cạnh nặng nhất e thuộc một MST. Xóa e từ một MST sẽ chia thảnh hai cây con tách rồi với hai điểm cuối của e trong cây con kháe nhau. Có tổn tại một số cạnh ƒ z ø trong, chu trình với các đầu cuốt trong hai cây con khác nhau. Khi 46 A’ ting rất nhanh, ngược lại hàm nghịch đáo của nó 4°—1 tăng, rất chậm.
Liàm nghịch đáo của hảm Ackermann durge Icy higu la at. Liam #(n) là nhỏ hơn 5 cho tất cả ga trị "thực" của =. Hàm nghịch đào Ackermam hai tham số được định nghĩa bởi đớn, n) = min{i >1| A(/[m/n]) > logn}. Chú ý là hàm œ tăng rất chậm, Đồi với số nguyễn ;m > 0 và m: >1, hàm đứn.r) được định nghĩa là 8(m,n) = min{i | log(1) < m/n), nghĩa là ØŒmjn) 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.3 Lý thuyết dỗ thị Đô thị vô hướng G là một kiểu dữ liệu trừu tượng dược xác định bởi Œ = (Œ,E), trong đỏ V là một tập đính và # là một tập cạnh, đỏ là cáo cặp đính không có thứ tự.
Ta sẽ kỷ hiệu m! =|V| và ? =|E|, và tập đính V = {Pa,tz,. Lớp các đồ thị với n đính và m cạnh được ký éu la G11, 771). Để chỉ ra tập đính của đồ thị Œ ta đùng kí hiệu bởi V(G), và tập cạnh của nó được kí hiệu bởi E(G). Một cạnh ø; nối hai đỉnh ơạ và wạ, và được ký hiểu (ra,zp).
Theo định nghữa của một. đỗ thị vô hưởng, một cạnh là một cặp không có thứ tự gồm hai dính, vì vậy (0, ,y) = (0„,0„). Mỗi cạnh e; của dễ thị sẽ dược gán một trọng số dương w(@;) có thể hiểu dỏ lá chỉ phí của "sử dụng" cạnh Nếu w(#¡) < w(e,) voi í # ƒ thiø, được coi là nhẹ hơn e;, ¢; ning hem ø,. Dẻ đơn gián, tất cá các ví dụ đỏ thị trong luận vẫn nảy sẽ có trọng số cạnh tương ứng với khoảng cách Buclide giữa các diém cuối.
Điều này là một giả dịnh phổ biến trong các vi dụ thực tế, chẳng hạn như xnạng lưới đường bộ và mạng lưới điện hoặc dây đữ liệu. Bậc của một đỉnh v, ký hiệu tổi dep(œ), là số cạnh kẻ với nó (nhận nả 14 dau mun). Mét đường đi trong đồ thị là xuột đây các đỉnh và cạnh xen kế bắt. đầu từ rnột.
đình và kết thúc tại một đỉnh. Như nti ifm=0 Aứm,r)= 4 AŒm — 1,1) ifm > 0 and ra = 0 A(m — 1,Aữn,n — 1)) else ‘Mét tinh chat quan trong cua 4(m,m) là giá trị của nó tăng rất nhanh, Gọi An) = An, 2). Khi 46 A’ ting rất nhanh, ngược lại hàm nghịch đáo của nó 4°—1 tăng, rất chậm. Liàm nghịch đáo của hảm Ackermann durge Icy higu la at.
Liam #(n) là nhỏ hơn 5 cho tất cả ga trị "thực" của =. Hàm nghịch đào Ackermam hai tham số được định nghĩa bởi đớn, n) = min{i >1| A(/[m/n]) > logn}. Chú ý là hàm œ tăng rất chậm, Đồi với số nguyễn ;m > 0 và m: >1, hàm đứn.r) được định nghĩa là 8(m,n) = min{i | log(1) < m/n), nghĩa là ØŒmjn) 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.3 Lý thuyết dỗ thị Đô thị vô hướng G là một kiểu dữ liệu trừu tượng dược xác định bởi Œ = (Œ,E), trong đỏ V là một tập đính và # là một tập cạnh, đỏ là cáo cặp đính không có thứ tự. Ta sẽ kỷ hiệu m! =|V| và ? =|E|, và tập đính V = {Pa,tz,.
Lớp các đồ thị với n đính và m cạnh được ký éu la G11, 771). Để chỉ ra tập đính của đồ thị Œ ta đùng kí hiệu bởi V(G), và tập cạnh của nó được kí hiệu bởi E(G). Một cạnh ø; nối hai đỉnh ơạ và wạ, và được ký hiểu (ra,zp). Theo định nghữa của một.
đỗ thị vô hưởng, một cạnh là một cặp không có thứ tự gồm hai dính, vì vậy (0, ,y) = (0„,0„). Mỗi cạnh e; của dễ thị sẽ dược gán một trọng số dương w(@;) có thể hiểu dỏ lá chỉ phí của "sử dụng" cạnh Nếu w(#¡) < w(e,) voi í # ƒ thiø, được coi là nhẹ hơn e;, ¢; ning hem ø,. Dẻ đơn gián, tất cá các ví dụ đỏ thị trong luận vẫn nảy sẽ có trọng số cạnh tương ứng với khoảng cách Buclide giữa các diém cuối. Điều này là một giả dịnh phổ biến trong các vi dụ thực tế, chẳng hạn như xnạng lưới đường bộ và mạng lưới điện hoặc dây đữ liệu.
Bậc của một đỉnh v, ký hiệu tổi dep(œ), là số cạnh kẻ với nó (nhận nả 14 dau mun). Mét đường đi trong đồ thị là xuột đây các đỉnh và cạnh xen kế bắt. đầu từ rnột. đình và kết thúc tại một đỉnh.