Chứng minh tính đúng đắn của thuật toán bfs
Vì bài viết nói về cây khung nhỏ nhất, các bạn nên đọc một số kiến thức liên quan đến cây trước mà mình liệt kê dưới đây vì đây là những kiến thức rất thường gặp trong những bài tập về cây khung, trong khuôn khổ bài viết mình sẽ không giải thích lại về những kiến thức này nữa: Show
Lưu ý: Toàn bộ phần code phía dưới sử dụng cho Cây khung nhỏ nhất là gìĐịnh nghĩaTheo lý thuyết đồ thị, chúng ta đều biết rằng 1 đồ thị được biểu diễn bằng công thức $G = (V, E)$, trong đó đồ thị $G$ của chúng ta bao gồm tập các đỉnh $V$ và tập các cạnh $E$.
Trong khuôn khổ bài viết, chúng ta sẽ làm việc với đồ thị vô hướng có trọng số. Tính chấtMột vài tính chất của cây khung nhỏ nhất trong đồ thị vô hướng có trọng số:
Chứng minhLưu ý : các bạn mới học cây khung lần đầu cân nhắc việc đọc chứng minh, tác giả khuyên các bạn nên tạm thời bỏ qua phần này Xuyên suốt cả bốn tính chất, ta đều sử dụng phép phản chứng để chứng minh
Các thuật toán tìm cây khung nhỏ nhất1. Thuật toán KruskalÝ tưởng thuật toán: Ban đầu mỗi đỉnh là một cây riêng biệt, ta tìm cây khung nhỏ nhất bằng cách duyệt các cạnh theo trọng số từ nhỏ đến lớn, rồi hợp nhất các cây lại với nhau. Cụ thể hơn, giả sử cạnh đang xét nối 2 đỉnh $u$ và $v$, nếu 2 đỉnh này nằm ở 2 cây khác nhau thì ta thêm cạnh này vào cây khung, đồng thời hợp nhất 2 cây chứa $u$ và $v$. Giả sử ta cần tìm cây khung nhỏ nhất của đồ thị $G$. Thuật toán bao gồm các bước sau:
Khi thuật toán kết thúc, rừng chỉ gồm đúng một cây và đó là một cây khung nhỏ nhất của đồ thị $G$ Ví dụ các bước giải bài toán tìm cây khung nhỏ nhất với thuật toán Kruskal : Để thực hiện thao tác kiểm tra cạnh và hợp nhất 2 cây một cách nhanh chóng, ta sử dụng cấu trúc Disjoint Set, dưới đây là đoạn code dùng để cài đặt thuật toán:
Chứng minh tính đúng đắn của thuật toán:Ta phải chứng minh hai điều:
Chứng minh (1)
Chứng minh (2) Lưu ý : Nếu bạn mới học cây khung lần đầu tiên chưa nên đọc ngay chứng minh này, vì chúng có thể khiến bạn hoang mang. Chứng minh có sử dụng một số khái niệm như lát cắt, lát cắt hẹp nhất Trong chứng minh này, mình có quy ước sử dụng một số kí hiệu:
Giờ cùng đi vào chi tiết chứng minh nhé (づ◔ ͜ʖ◔)づ
Đánh giá độ phức tạp thuật toán: Gọi $n$ là số đỉnh, $m$ là số cạnh của đồ thị Thuật toán gồm 2 phần:
$\Rightarrow$ độ phức tạp của thuật toán Kruskal là $O(m\log{m} +m\log{n})$ 2. Thuật toán PrimÝ tưởng thuật toán: Ý tưởng của thuật toán Prim rất giống với ý tưởng của thuật toán Dijkstra (tìm đường đi ngắn nhất trên đồ thị). Nếu như thuật toán Kruskal xây dựng cây khung nhỏ nhất bằng cách kết nạp từng cạnh vào đồ thị thì thuật toán Prim lại kết nạp từng đỉnh vào đồ thị theo tiêu chí: đỉnh được nạp vào tiếp theo phải chưa được nạp và gần nhất với các đỉnh đã được nạp vào đồ thị. Thuật toán bao gồm các bước sau:
Mặc dù không bắt buộc, các bạn có thể đọc chứng minh tính đúng đắn thuật toán của Wiki tại . Khi hoàn thành xong $n$ bước trên, ta thu được cây khung nhỏ nhất của đồ thị gồm $n$ đỉnh và $n - 1$ cạnh. Ví dụ các bước giải bài toán tìm cây khung nhỏ nhất với thuật toán Prim: Đoạn code sử dụng để cài đặt thuật toán Prim:
Đánh giá độ phức tạp thuật toán:
Fact: Trong các bài toán tìm cây khung, phần lớn mọi người sẽ sử dụng thuật toán Kruskal do tính dễ cài đặt cũng như dễ hiểu của nó. Bonus : Các bạn có thể sử dụng Visualgo để mô phỏng thuật toán Kruskal và Prim thông qua hoạt ảnh, qua đó hiểu thêm về các thuật toán trên Một số bài toán áp dụng1. Bài toán NKCITYTóm tắt đề bài1 thành phố gồm $N$ trọng điểm, $M$ tuyến đường có thể được xây dựng với chi phí xây dựng khác nhau. Yêu cầu chọn ra một số tuyến đường sao cho $N$ trọng điểm phải được liên thông với nhau và chi phí xây dựng tuyến đường lớn nhất là nhỏ nhất có thể. Thuật toánDựa vào tính chất đường đi hẹp nhất của cây khung mà ta đã trình bày ở trên, đường đi giữa 2 đỉnh $u$, $v$ bất kỳ trên cây khung nhỏ nhất là đường đi có cạnh lớn nhất là nhỏ nhất của đồ thị. Như vậy việc chọn ra các tuyến đường để xây dựng chỉ đơn giản là chọn các cạnh trên cây khung nhỏ nhất của đồ thị. Độ phức tạpChính là độ phức tạp của thuật toán tìm cây khung nhỏ nhất mà các bạn sẽ cài đặt. Cài đặtỞ đây ta sẽ dùng Kruskal để tìm cây khung nhỏ nhất
2. Bài toán tìm cây khung nhỏ nhất cho mỗi cạnh - Codeforces 609ETóm tắt đề bàiCho đồ thị vô hướng $G$ gồm $n$ đỉnh và $m$ cạnh. Yêu cầu với mỗi cạnh trong đồ thị, tìm cây khung nhỏ nhất chứa cạnh đó của đồ thị và in ra trọng số của cây khung đó. Đây là 1 bài tập khá kinh điển về cây khung nhỏ nhất. Để giải được bài tập này, chúng ta cần giải bài LUBENICA trước. Các bạn có thể đọc thêm về bài ở đây Thuật toán:
Code mẫu:
3. Bài toán 160D - Edges in MSTTóm tắt đề bàiCho đồ thị vô hướng có trọng số $G$ gồm $n$ đỉnh và $m$ cạnh. Yêu cầu với mỗi cạnh trong đồ thị, kiểm tra xem cạnh đó không thuộc bất kỳ cây khung nhỏ nhất nào, thuộc một số cây khung nhỏ nhất hay nằm trong mọi cây khung nhỏ nhất của đồ thị. |