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:
- Disjoin Set Union
Lưu ý: Toàn bộ phần code phía dưới sử dụng cho C++11 trở lên, các bạn lưu ý kiểm tra trình biên dịch của mình.
Cây khung nhỏ nhất là gì
Định nghĩa
Theo 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$.
- Cây khung [spanning tree] của đồ thị là một tập hợp các cạnh của đồ thị thỏa mãn tập cạnh này không chứa chu trình và liên thông [từ một đỉnh bất kì có thể đi tới bất kỳ đỉnh nào khác theo mà chỉ dùng các cạnh trên cây khung]
- Trong đồ thị có trọng số, cây khung nhỏ nhất [minimum spanning tree] là cây khung có tổng trọng số các cạnh trong cây nhỏ nhất.
- Một ví dụ về cây khung trong đồ thị vô hướng không trọng số:
- Một ví dụ về cây khung nhỏ nhất trong đồ thị vô hướng có trọng số:
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ất
Một vài tính chất của cây khung nhỏ nhất trong đồ thị vô hướng có trọng số:
- 1. Tính chất chu trình: Trong một chu trình $C$ bất kỳ, nếu $e$ là cạnh có trọng số lớn nhất tuyệt đối [không có cạnh nào có trọng số bằng $e$] thì $e$ không thể nằm trên bất kỳ cây khung nhỏ nhất nào.
- 2. Đường đi hẹp nhất: Xét 2 đỉnh $u$, $v$ bất kỳ trong đồ thị. Nếu $w$ là trọng số của cạnh lớn nhất trên đường đi từ $u$ đến $v$ trên cây khung nhỏ nhất của đồ thị thì ta không thể tìm được đường đi nào từ $u$ đến $v$ trên đồ thị ban đầu chỉ đi qua những cạnh có trọng số nhỏ hơn $w$.
- 3. Tính duy nhất: Nếu tất cả các cạnh đều có trọng số khác nhau thì chỉ có duy một cây khung nhỏ nhất. Ngược lại, nếu một vài cạnh có trọng số giống nhau thì có thể có nhiều hơn một cây khung nhỏ nhất.
- 4. Tính chất cạnh nhỏ nhất: Nếu $e$ là cạnh có trọng số nhỏ nhất của đồ thị, và không có cạnh nào có trọng số bằng $e$ thì $e$ nằm trong mọi cây khung nhỏ nhất của đồ thị.
Chứng minh
Lư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
- 1. Tính chất chu trình: Giả sử $e$ thuộc một cây khung $T$ của đồ thị, ta sẽ chứng minh luôn tồn tại một cây khung khác của đồ thị có trọng số nhỏ hơn $T$.
- Ta thử xóa cạnh $e$ khỏi cây khung $T$. Lúc này, $T$ sẽ bị chia làm 2 thành phần liên thông và tổng trọng số giảm đi $w_e$.
- Xét các đỉnh nằm trong chu trình $C$, giả sử sau khi xóa $e$ khỏi cây khung, các đỉnh này vẫn liên thông với nhau. Vì thế, khi thêm $e$ trở lại vào cây khung, $e$ sẽ kết nối 2 đỉnh đã liên thông với nhau $\Rightarrow$ tồn tại chu trình trong cây khung $\Rightarrow$ Trái với giả thiết $T$ là cây khung. ⇒ Vậy nên, khi xóa $e$ khỏi $T$, các đỉnh nằm trong chu trình $C$ sẽ bị tách làm 2 thành phần liên thông. Do đó, ta có thể chọn ra cạnh $e'$ khác $e$ thuộc chu trình $C$ để kết nối 2 thành liên thông này, biến $T$ trở lại thành một cây khung của đồ thị. Mặt khác, $e$ là cạnh có trọng số lớn nhất tuyệt đối trên $C$, nên khi thay $e$ bằng $e'$, trọng số của T sẽ giảm đi $w_e - w_{e'}$ Kết luận: T không phải là cây khung nhỏ nhất của đồ thị.
- 2. Đường đi hẹp nhất:
- Xét cây khung nhỏ nhất $T$ bất kỳ của đồ thị $G$ mà tồn tại đường đi $u \rightarrow v$ trên $G$ có cạnh lớn nhất nhỏ hơn cạnh lớn nhất của đường đi $u \rightarrow v$ trên $T$.
- Gọi đường đi $u \rightarrow v$ trên $G$ là $path$, cạnh lớn nhất của đường đi $u \rightarrow v$ trên $T$ là $e$. ⇒ Như vậy, nếu xóa $e$ khỏi cây khung ban đầu, cây khung sẽ bị chia thành 2 TPLT rời nhau, một TPLT chứa $u$ và TPLT còn lại chứa $v$.
- Do $path$ là đường đi $u \rightarrow v$ trên $G$ nên trên $path$ sẽ tồn tại cạnh $e'$ có thể kết nối 2 TPLT này. Mà mọi cạnh trên $path$ đều có trọng số nhỏ hơn $e$ [như giả thiết] ⇒ Khi xoá $e$ và thay bằng $e'$, ta sẽ thu được 1 cây khung $T'$ có trọng số nhỏ hơn cây khung ban đầu Kết luận: $T$ không phải cây khung nhỏ nhất của đồ thị.
- 3. Tính duy nhất:
- Giả sử tồn tại 2 cây khung nhỏ nhất $T$ và $T'$. Xét cạnh $u-v$ nằm trong $T$ nhưng không trong $T'$.
- Gọi đường đi $u \rightarrow v$ trên $T$ là $path$, trên $T'$ là $path'$. Hiển nhiên, $path'$ không chứa cạnh $u-v$.
- Vì trọng số các cạnh của đồ thị đều khác nhau $\Rightarrow$ Cạnh lớn nhất của $path$ sẽ có trọng số lớn hơn trọng số cạnh lớn nhất của $path'$ hoặc ngược lại. ⇒ Theo tính chất đường đi hẹp nhất, $T$ hoặc $T'$ sẽ không phải là cây khung nhỏ nhất.
- 4. Tính chất cạnh nhỏ nhất:
Ta sẽ chứng minh mọi cây khung không chứa $e$ của đồ thị đều không phải là cây khung nhỏ nhất. Giả sử $e$ nối 2 đỉnh $u$, $v$ của đồ thị. Gọi $T$ là 1 cây khung không chứa $e$ của đồ thị. Xét cạnh $e'$ bất kỳ thuộc đường đi từ $u \rightarrow v$ trên $T$. Khi xóa $e'$ khỏi $T$, $T$ sẽ bị tách làm 2 thành phần liên thông, 1 thành phần liên thông chứa $u$, 1 phần phần liên thông chứa $v$. ⇒ Do đó, ta hoàn toàn có thể thêm cạnh $e$ [nối 2 đỉnh $u- v$] vào $T$ để kết nối 2 thành phần liên thông này, khi đó $T$ sẽ trở lại thành 1 cây khung của đồ thị.
- Mặt khác, $e$ là cạnh có trọng số nhỏ nhất tuyệt đối của đồ thị, nên khi thay $e'$ bằng $e$ trên cây khung $T$, trọng số của $T$ sẽ giảm đi 1 lượng dương Kết luận: $T$ ban đầu không phải là cây khung nhỏ nhất của đồ thị.
Các thuật toán tìm cây khung nhỏ nhất
1. 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:
- Khởi tạo rừng $F$ [tập hợp các cây], trong đó mỗi đỉnh của G tạo thành một cây riêng biệt.
- Khởi tạo tập $S$ chứa tất cả các cạnh của $G$.
- Chừng nào $S$ còn khác rỗng và $F$ gồm hơn một cây
- Xóa cạnh nhỏ nhất trong $S$
- Nếu cạnh đó nối hai cây khác nhau trong $F$, thì thêm nó vào $F$ và hợp hai cây kề với nó làm một
- Nếu không thì loại bỏ cạnh đó.
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:
/*input
4 4
1 2 1
2 3 2
3 4 3
4 1 4
*/
# include
using namespace std;
// Cấu trúc để lưu các cạnh đồ thị
// u, v là 2 đỉnh, c là trọng số cạnh
struct Edge {
int u, v, c;
Edge[int _u, int _v, int _c]: u[_u], v[_v], c[_c] {};
};
struct Dsu {
vector par;
void init[int n] {
par.resize[n + 5, 0];
for [int i = 1; i edges;
int main[] {
// Fast IO
ios_base::sync_with_stdio[0]; cin.tie[0]; cout.tie[0];
cin >> n >> m;
for [int i = 1; i > u >> v >> c;
edges.push_back[{u, v, c}];
}
dsu.init[n];
// Sắp xếp lại các cạnh theo trọng số tăng dần
sort[edges.begin[], edges.end[], [][Edge & x, Edge & y] {
return x.c < y.c;
}];
// Duyệt qua các cạnh theo thứ tự đã sắp xếp
for [auto e : edges] {
// Nếu không hợp nhất được 2 đỉnh u và v thì bỏ qua
if [!dsu.join[e.u, e.v]] continue;
// Nếu hợp nhất được u, v ta thêm trọng số cạnh vào kết quả
totalWeight += e.c;
}
// Xuất ra kết quả
cout