Tác giả:
Reviewer:
Mục đích của bài viết này là để giới thiệu với các bạn đọc về matroid, vốn là một cấu trúc trong đại số trừu tượng nhưng lại được sử dụng ở một số bài nâng cao trong lập trình thi đấu. Bài viết này sẽ chỉ giới thiệu về định nghĩa của matroid, cùng với một số tính chất đặc biệt của matroid giúp việc xây dựng các thuật toán tham lam trên matroid trở nên dễ hơn rất nhiều so với các bài khác không có matroid.
Bài viết này là phần 1 của chuỗi bài viết về các thuật toán liên quan tới matroid.
Bài viết này cần người đọc vững về các toán tử trên tập hợp, ví dụ như phép giao , phép hợp , phép hiệu , toán tử tập con và , v.v.
Mình sẽ dùng kí hiệu cho việc thêm một phần tử vào tập, và cho việc loại một phần tử khỏi tập.
Với các bạn đã làm một số bài về xor basis, với một tập gồm các số tự nhiên, ta có một số định nghĩa sau đây. Với một tập con bất kì:
Ở đây, khái niệm độc lập được định nghĩa dựa trên việc tồn tại một tập con các phần tử có tổng xor bằng . Tuy nhiên, ta không nhất thiết phải ép buộc vào một định nghĩa của độc lập như thế.
Xét ví dụ sau: cho đồ thị vô hướng liên thông gồm đỉnh và cạnh. Gọi tập tất cả các cạnh trên là tập . Ta có thể dựng một định nghĩa về tập độc lập của như sau. Với một tập con bất kì:
Ta dễ dàng nhận ra được là dưới định nghĩa tập độc lập như trên, nếu tập là cở sở của , các cạnh trong dựng nên một cây khung của đồ thị . Nói cách khác, các cây khung của dựng nên các cơ sở cho định nghĩa tập độc lập như trên. Đây là một cách định nghĩa tập độc lập trên tập các cạnh của đồ thị khá hữu ích.
![]() |
---|
Một tập cạnh độc lập. Đây còn là một cơ sở. |
![]() |
---|
Một tập cạnh không độc lập. |
Matroid là một cách tổng quát hóa định nghĩa độc lập cho bất kì tập hữu hạn nhằm giữ lại các tính chất tốt của các định nghĩa tập độc lập như xor basis hay cây khung. Mặc dù định nghĩa mình giới thiệu sau đây có thể nghe trừu tượng, định nghĩa này có thể bao quát rất nhiều cấu trúc quan trọng trong lập trình thi đấu.
Với một tập hữu hạn (tập này còn được gọi là ground set), giả sử ta định nghĩa một tính chất độc lập trên , và ta thu được là tập hợp của các tập độc lập của . Khi này (hay nói đúng hơn là cặp ) là một matroid khi:
Để làm định nghĩa tường minh hơn, ta quay lại về ví dụ của tập độc lập trên các cạnh của đồ thị như trên.
Ta có thể chứng minh được rằng là một matroid như sau:
Một số matroid điển hình bao gồm:
Với tập con , ta định nghĩa hạng của () là kích cỡ tập con độc lập to nhất của , thì ta thu được một số tính chất sau về hạng của :
Ta có thể định nghĩa thêm hạng của toàn bộ matroid là hạng của toàn bộ tập (), và cơ sở là các tập độc lập tối đa của matroid (ta không thể thêm phần tử nào khác vào mà vẫn giữ tập được độc lập), thì ta có tính chất sau:
Xét bài toán sau:
Cho matroid định nghĩa trên tập có phần tử, sao cho mỗi phần tử trong tập có một trọng số . Hãy tìm cơ sở của matroid có tổng trọng số lớn nhất/nhỏ nhất.
Không mất tính tổng quát, ta sẽ giải bài toán tìm cơ sở lớn nhất. Ta có thuật toán tham lam sau để tìm cơ sở lớn nhất của matroid.
Ta có thể chứng minh được thuật toán này trả về cơ sở lớn nhất của matroid. Ngoài ra, giả sử ta được cho một hàm kiểm tra tính độc lập: với tập độc lập và phần tử bất kì, ta có thể kiểm tra nếu là tập độc lập trong độ phức tạp , thì thấy rằng độ phức tạp của thuật toán trên là .
Giả sử thuật toán trả về cơ sở . Xét bất kì cơ sở nào khác , và giả sử là ta đã sắp xếp và theo thứ tự trọng số giảm dần, tức là và .
Với mọi từ tới , xét và . Vì và là tập độc lập, ta có và cũng là tập độc lập (tiên đề 2 của matroid). Ngoài ra, vì , theo tiên đề 3 của matroid, tồn tại phần tử nào đó của có thể cho vào để vẫn là tập độc lập (với ). Tuy nhiên, theo thuật toán trên, là phần tử có trọng số lớn nhất có thể cho vào để tập vẫn độc lập. Vậy nên ta có . Vì ta chứng minh được điều này đúng với mọi , ta có .
Với bài toán tìm cơ sở nhỏ nhất, ta chỉ cần đổi thứ tự sắp xếp của .
Cuối cùng, ta nhận thấy rằng với trường hợp đặc biệt của matroid đồ thị, thuật toán trên chính là thuật toán Kruskal để tìm cây khung lớn nhất, vì cây khung là cơ sở của matroid đồ thị.
Dưới đây là cách cài đặt tìm cơ sở lớn nhất, cùng với cách áp dụng vào bài toán tìm cây khung lớn nhất.
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> par;
DSU(int n) : par(n, -1) {}
int comp(int u) { return par[u] < 0 ? u : par[u] = comp(par[u]); }
bool connect(int u, int v) {
if ((u = comp(u)) == (v = comp(v))) {
return false;
}
if (par[u] > par[v]) {
swap(u, v);
}
par[u] += par[v]; par[v] = u;
return true;
}
};
struct GraphMat {
vector<pair<int, int>> edges;
int n;
DSU d;
GraphMat(int n, vector<pair<int, int>> edges) : n(n), d(n), edges(edges) {}
bool check(int x) {
// kiểm tra nếu ta có thể thêm phần tử a vào tập S hiện tại
auto [u, v] = edges[x];
return d.comp(u) != d.comp(v);
}
void add(int x) {
// thêm a vào tập S hiện tại
auto [u, v] = edges[x];
d.connect(u, v);
}
void clear() { d = DSU(n); }
};
template<class M>
vector<int> largestBasis(M mat, int n, vector<int> w) {
vector<int> elem(n);
iota(elem.begin(), elem.end(), 0);
sort(elem.begin(), elem.end(), [&](int u, int v) { return w[u] > w[v]; });
vector<int> S = {};
for (int u : elem) {
if (mat.check(u)) {
S.push_back(u);
mat.add(u);
}
}
return S;
}
int main() {
// tìm cây khung lớn nhất
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges;
vector<int> w(m);
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v >> w[i]; u--; v--; // giả sử đồ thị cho đỉnh từ 1 tới n, ta biến thành từ 0 tới n - 1
edges.push_back({u, v});
}
GraphMat mat(n, edges);
vector<int> span = largestBasis(mat, m, w);
for (auto x : span) {
auto [u, v] = edges[x];
cout << u + 1 << " " << v + 1 << "\n";
}
}