Wiki › Thuật toán › Matroid và giao matroid

Matroid và giao matroid

Matroid (đồ thị, tuyến tính, phân hoạch, đều), vì sao tham lam tối ưu trên matroid, và thuật toán giao hai matroid bằng đường tăng ngắn nhất trên đồ thị trao đổi với O(r^2 n) lần gọi oracle.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 23 phút 4 lượt xem

Matroid là một cấu trúc trừu tượng hoá khái niệm "độc lập": tập cạnh không có chu trình, tập vector độc lập tuyến tính, tập phần tử mà mỗi nhóm lấy không quá một số lượng cho trước... Trên một matroid, thuật toán tham lam (sắp theo trọng số rồi lấy nếu còn độc lập) luôn cho đáp án tối ưu, đó là lý do Kruskal và cơ sở XOR đúng. Khi bài toán đòi đồng thời độc lập trong hai matroid (ví dụ "rừng khung lớn nhất mà mỗi màu dùng tối đa một cạnh"), tham lam thất bại, nhưng giao matroid (matroid intersection) vẫn tìm được tập chung lớn nhất trong thời gian đa thức: O(r2n) lần gọi "oracle độc lập", với n là số phần tử và r là kích thước đáp án, thay vì thử 2n tập con.

Matroid là gì

Một matroid M=(E,ℐ) gồm tập nền hữu hạn E và họ ℐ các tập con của E gọi là tập độc lập, thoả ba tiên đề:

  1. ∅∈ℐ.
  2. Di truyền: nếu A∈ℐ và B⊆A thì B∈ℐ (bỏ bớt phần tử vẫn độc lập).
  3. Trao đổi: nếu A,B∈ℐ và |A|<|B| thì tồn tại x∈B⧵A sao cho A∪{x}∈ℐ.

Tập độc lập tối đại gọi là cơ sở (basis); theo tiên đề trao đổi mọi cơ sở có cùng kích thước, gọi là hạng r(M). Tổng quát, hạng r(S) của một tập S⊆E là kích thước tập độc lập lớn nhất nằm trong S.

Bốn ví dụ hay gặp:

Matroid Tập nền E S độc lập khi Oracle kiểm tra
Đồ thị (graphic) cạnh của một đồ thị S không chứa chu trình (là một rừng) DSU
Tuyến tính (linear, XOR) các vector, ví dụ số nguyên xem như vector trên GF(2) các vector độc lập tuyến tính (không tập con khác rỗng nào XOR bằng 0) cơ sở XOR / khử Gauss
Phân hoạch (partition) phần tử chia thành các nhóm G1,G2,… |S∩Gj|≤cj với mọi nhóm j đếm số phần tử mỗi nhóm
Đều (uniform) Uk,n n phần tử bất kỳ |S|≤k so sánh kích thước

Kiểm tra tiên đề trao đổi cho matroid đồ thị: rừng A có V−|A| thành phần, rừng B có ít thành phần hơn, nên phải có một cạnh của B nối hai thành phần khác nhau của A; thêm cạnh đó vào A vẫn là rừng.

Không phải matroid: tập các cặp ghép (matching) của một đồ thị. Trên đường 1−2−3−4, A={(2,3)} và B={(1,2),(3,4)} đều là cặp ghép, |A|<|B|, nhưng thêm cạnh nào của B vào A cũng đụng đỉnh 2 hoặc 3. Đây chính là lý do ghép cặp không giải bằng tham lam được, nhưng (như sẽ thấy) ghép cặp hai phía lại là giao của hai matroid.

Tham lam trên matroid

Định lý (Rado, Edmonds). Cho trọng số w(x) trên các phần tử. Thuật toán: sắp phần tử theo w giảm dần, duyệt lần lượt, thêm x vào S nếu S∪{x} còn độc lập. Kết quả là cơ sở có tổng trọng số lớn nhất. Ngược lại, nếu một họ tập con có tính di truyền mà thuật toán này đúng với mọi trọng số thì họ đó là một matroid.

Vì sao đúng (phác thảo). Gọi s1,s2,… là các phần tử tham lam chọn (theo thứ tự chọn) và giả sử có cơ sở T={t1,t2,…} (sắp giảm) tốt hơn. Lấy i nhỏ nhất mà w(ti)>w(si). Áp dụng tiên đề trao đổi cho A={s1,…,si−1} và B={t1,…,ti}: có tj (j≤i, nên w(tj)≥w(ti)>w(si)) thêm được vào A. Nhưng khi đó tham lam đã xét tj trước si và đã phải chọn nó, mâu thuẫn.

Hệ quả quen thuộc:

  • Kruskal là tham lam trên matroid đồ thị (sắp tăng dần để được cây khung nhỏ nhất).
  • XOR lớn nhất, cơ sở XOR có tổng trọng số lớn nhất là tham lam trên matroid tuyến tính.
  • Bài lập lịch "mỗi việc có hạn chót và tiền thưởng, chọn tập việc làm kịp với tổng thưởng lớn nhất" là tham lam trên một matroid (các tập việc lập lịch được tạo thành matroid). Xem thêm Tham lam.

Một mẹo dùng được ngay: nếu bạn chứng minh được ràng buộc của bài là một matroid, tham lam đúng mà không cần lập luận đổi chỗ (exchange argument) riêng.

Giao matroid: bài toán và trực giác

Cho hai matroid M1=(E,ℐ1) và M2=(E,ℐ2) trên cùng tập nền. Tìm tập I lớn nhất sao cho I∈ℐ1 và I∈ℐ2.

Ví dụ: đồ thị có cạnh tô màu, tìm rừng nhiều cạnh nhất mà không hai cạnh nào cùng màu. M1 là matroid đồ thị, M2 là matroid phân hoạch theo màu với cj=1. Giao của hai matroid nói chung không là matroid, nên tham lam có thể kẹt (ví dụ bên dưới).

Ý tưởng giống hệt ghép cặp hai phía: bắt đầu từ I=∅, lặp lại việc tìm một đường tăng làm |I| tăng thêm 1; khi không còn đường tăng thì I là lớn nhất.

Đồ thị trao đổi (exchange graph) D(I): mỗi phần tử của E là một đỉnh. Với y∈I và x∉I:

  • cạnh y→x nếu I−y+x∈ℐ1 (trong M1, đổi y lấy x vẫn độc lập);
  • cạnh x→y nếu I−y+x∈ℐ2 (trong M2, đổi y lấy x vẫn độc lập).

Tập nguồn X1={x∉I:I+x∈ℐ1}, tập đích X2={x∉I:I+x∈ℐ2}.

Một đường đi x0→y1→x1→y2→⋯→yk→xk từ x0∈X1 tới xk∈X2 xen kẽ phần tử ngoài I và trong I. Lật đường đi (thêm các xi, bỏ các yi) cho tập mới I′=I△P lớn hơn I đúng 1. Nhìn theo từng matroid:

  • Với M1: x0 được thêm "miễn phí" (vì x0∈X1), còn mỗi xi (i≥1) thay chỗ yi qua cạnh yi→xi.
  • Với M2: xk được thêm miễn phí (vì xk∈X2), còn mỗi xi−1 thay chỗ yi qua cạnh xi−1→yi.

Mỗi phép đổi riêng lẻ giữ tính độc lập, nhưng làm nhiều phép đổi cùng lúc thì chưa chắc. Điểm mấu chốt: nếu chọn đường đi ngắn nhất (BFS) thì I′ chắc chắn độc lập trong cả hai matroid.

Phác thảo chứng minh.

  1. Đường ngắn nhất giữ độc lập. Đường ngắn nhất không có "lối tắt": chẳng hạn không có cạnh yi→xj với j>i (nếu có, bỏ được một đoạn và đường ngắn hơn), và không đỉnh nào khác trên đường thuộc X1 hay X2. Bổ đề của Edmonds (thường gọi là bổ đề ghép cặp duy nhất): nếu các cặp đổi (yi,xi) là cách ghép duy nhất giữa {yi} và {xi} trong đồ thị trao đổi của M1 thì I−{yi}+{xi} độc lập trong M1. Tính "không lối tắt" chính là điều kiện duy nhất đó. Với x0 (hoặc xk với M2), thêm một phần tử giả vào matroid để quy về cùng bổ đề.
  2. Không có đường tăng thì tối ưu. Gọi U là tập các phần tử đi tới được một đỉnh đích trong D(I). Không có đường tăng nghĩa là U∩X1=∅. Từ việc không có cạnh nào đi từ ngoài U vào U, ta suy ra r1(U)=|I∩U| và r2(E⧵U)=|I⧵U|, tức |I|=r1(U)+r2(E⧵U). Mà với mọi tập độc lập chung J và mọi U: |J|=|J∩U|+|J⧵U|≤r1(U)+r2(E⧵U). Vậy I lớn nhất.

Phần 2 cho luôn định lý min-max của Edmonds:

maxI∈ℐ1∩ℐ2|I|=minU⊆E(r1(U)+r2(E⧵U)).

Với ghép cặp hai phía, đây chính là định lý König (cặp ghép lớn nhất bằng phủ đỉnh nhỏ nhất).

Ví dụ chạy tay

Đồ thị 4 đỉnh, 4 cạnh, 3 màu (đỏ, xanh, lục). Tìm rừng lớn nhất mà mỗi màu dùng tối đa một cạnh.

cạnh nối màu
e1 1−2 đỏ
e2 2−3 xanh
e3 1−3 lục
e4 3−4 đỏ
graph
4 4
1 2 e1(đỏ)
2 3 e2(xanh)
1 3 e3(lục)
3 4 e4(đỏ)
highlight red 1-2 3-4
highlight blue 2-3
highlight green 1-3

Tham lam theo thứ tự lấy e1, lấy e2, bỏ e3 (tạo chu trình 1−2−3), bỏ e4 (màu đỏ đã dùng). Kẹt ở I={e1,e2}, trong khi đáp án đúng có 3 cạnh. Thuật toán giao matroid cũng đi qua đúng hai bước đầu này (đường tăng độ dài 0: một phần tử vừa là nguồn vừa là đích), rồi ở I={e1,e2} dựng đồ thị trao đổi:

  • Nguồn (I+x vẫn là rừng): chỉ e4. (e3 tạo chu trình.)
  • Đích (I+x vẫn đúng màu): chỉ e3. (e4 trùng màu đỏ với e1.)
  • Cạnh M1 (y→x khi I−y+x là rừng): e1→e3, e1→e4, e2→e3, e2→e4.
  • Cạnh M2 (x→y khi I−y+x đúng màu): e3→e1, e3→e2 (màu lục còn trống nên bỏ gì cũng được), e4→e1 (bỏ e1 thì màu đỏ trống). Không có e4→e2 vì {e1,e4} có hai cạnh đỏ.
dot
digraph {
  rankdir=LR;
  node [shape=circle];
  e4 [label="e4\nnguồn", color=orange];
  e3 [label="e3\nđích", color=green];
  e1; e2;
  e1 -> e3 [color=red, penwidth=2];
  e1 -> e4;
  e2 -> e3;
  e2 -> e4;
  e3 -> e1 [style=dashed];
  e3 -> e2 [style=dashed];
  e4 -> e1 [style=dashed, color=red, penwidth=2];
}

(Nét liền: cạnh của M1; nét đứt: cạnh của M2; màu đỏ: đường tăng ngắn nhất.)

BFS từ nguồn e4 tìm được e4→e1→e3. Lật đường đi: thêm e4, bỏ e1, thêm e3. Ta được I={e2,e3,e4}: cạnh 2−3, 1−3, 3−4 là cây khung, ba màu khác nhau.

Ở vòng tiếp theo không còn nguồn (đã là cây khung) nên thuật toán dừng. Kiểm tra bằng định lý min-max: không có đích nào (e1 màu đỏ đã dùng), nên U=∅ và r1(∅)+r2(E)=0+3=3=|I|.

Chương trình bên dưới với đầu vào

4 4 3
1 2 1
2 3 2
1 3 3
3 4 1

in ra

3
2 3 4

Cài đặt

Khuôn mẫu tổng quát: mỗi matroid là một struct có hai hàm

  • build(S): nạp một tập độc lập S vào oracle;
  • canAdd(x): hỏi S+x có độc lập không (với S vừa nạp).

Để hỏi "I−y+x có độc lập không", ta build(I - y) một lần rồi gọi canAdd(x) cho mọi x∉I. Muốn đổi bài, chỉ cần viết struct matroid mới, hàm matroidIntersection giữ nguyên.

Ví dụ minh hoạ: đọc n m k rồi m cạnh u v c (1≤c≤k), in số cạnh lớn nhất của một rừng dùng mỗi màu tối đa một cạnh và chỉ số các cạnh đó.

C++
#include <bits/stdc++.h>
using namespace std;

// Graphic matroid: a set of edges is independent iff it is a forest.
struct GraphicMatroid {
    int n;
    vector<pair<int, int>> edges;
    vector<int> par;
    GraphicMatroid(int n, vector<pair<int, int>> e) : n(n), edges(e), par(n + 1) {}
    int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
    // Load a base set S (assumed independent) into the oracle
    void build(const vector<int>& S) {
        iota(par.begin(), par.end(), 0);
        for (int e : S) par[find(edges[e].first)] = find(edges[e].second);
    }
    // Is S + x still independent? (S = the set passed to build)
    bool canAdd(int x) { return find(edges[x].first) != find(edges[x].second); }
};

// Partition matroid: element x has group grp[x]; at most cap[g] elements per group.
struct PartitionMatroid {
    vector<int> grp, cap, cnt;
    PartitionMatroid(vector<int> g, vector<int> c) : grp(g), cap(c), cnt(c.size()) {}
    void build(const vector<int>& S) {
        fill(cnt.begin(), cnt.end(), 0);
        for (int e : S) cnt[grp[e]]++;
    }
    bool canAdd(int x) { return cnt[grp[x]] < cap[grp[x]]; }
};

// Unweighted matroid intersection: returns a maximum common independent set.
// Each matroid M needs build(S) and canAdd(x). O(r) augmentations,
// each costs O(r) builds and O(r * m) canAdd calls.
template <class M1, class M2>
vector<int> matroidIntersection(int m, M1& A, M2& B) {
    vector<char> inI(m, 0);
    while (true) {
        vector<int> I;
        for (int i = 0; i < m; i++) if (inI[i]) I.push_back(i);

        // Sources: I + x independent in A. Sinks: I + x independent in B.
        A.build(I); B.build(I);
        vector<char> isSrc(m, 0), isSink(m, 0);
        for (int x = 0; x < m; x++) if (!inI[x]) {
            isSrc[x] = A.canAdd(x);
            isSink[x] = B.canAdd(x);
        }

        // Exchange graph, y in I, x not in I:
        //   y -> x  if I - y + x independent in A
        //   x -> y  if I - y + x independent in B
        vector<vector<int>> adj(m);
        for (int y : I) {
            vector<int> rest;
            for (int z : I) if (z != y) rest.push_back(z);
            A.build(rest); B.build(rest);
            for (int x = 0; x < m; x++) if (!inI[x]) {
                if (A.canAdd(x)) adj[y].push_back(x);
                if (B.canAdd(x)) adj[x].push_back(y);
            }
        }

        // BFS from all sources at once, stop at the first sink reached (shortest path)
        vector<int> prv(m, -2);
        queue<int> q;
        for (int x = 0; x < m; x++) if (isSrc[x]) { prv[x] = -1; q.push(x); }
        int end = -1;
        while (!q.empty() && end < 0) {
            int u = q.front(); q.pop();
            if (isSink[u]) { end = u; break; }
            for (int v : adj[u]) if (prv[v] == -2) { prv[v] = u; q.push(v); }
        }
        if (end < 0) break;                       // no augmenting path: I is maximum
        for (int v = end; v != -1; v = prv[v]) inI[v] ^= 1;   // flip along the path
    }
    vector<int> I;
    for (int i = 0; i < m; i++) if (inI[i]) I.push_back(i);
    return I;
}

int main() {
    // Input: n m k, then m lines "u v c" (1 <= c <= k).
    // Find the largest forest using at most one edge of each color.
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> edges(m);
    vector<int> color(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].first >> edges[i].second >> color[i];
        color[i]--;
    }
    GraphicMatroid G(n, edges);
    PartitionMatroid P(color, vector<int>(k, 1));
    vector<int> I = matroidIntersection(m, G, P);
    cout << I.size() << "\n";
    for (int e : I) cout << e + 1 << " ";
    cout << "\n";
}
Python
import sys
from collections import deque


class GraphicMatroid:
    """A set of edges is independent iff it is a forest."""
    def __init__(self, n, edges):
        self.n, self.edges = n, edges

    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x

    def build(self, S):
        self.par = list(range(self.n + 1))
        for e in S:
            u, v = self.edges[e]
            self.par[self.find(u)] = self.find(v)

    def can_add(self, x):
        u, v = self.edges[x]
        return self.find(u) != self.find(v)


class PartitionMatroid:
    """At most cap[g] elements from each group g."""
    def __init__(self, grp, cap):
        self.grp, self.cap = grp, cap

    def build(self, S):
        self.cnt = [0] * len(self.cap)
        for e in S:
            self.cnt[self.grp[e]] += 1

    def can_add(self, x):
        return self.cnt[self.grp[x]] < self.cap[self.grp[x]]


def matroid_intersection(m, A, B):
    in_i = [False] * m
    while True:
        I = [i for i in range(m) if in_i[i]]
        A.build(I)
        B.build(I)
        src = [not in_i[x] and A.can_add(x) for x in range(m)]
        sink = [not in_i[x] and B.can_add(x) for x in range(m)]
        # Exchange graph: y -> x if I-y+x in A, x -> y if I-y+x in B
        adj = [[] for _ in range(m)]
        for y in I:
            rest = [z for z in I if z != y]
            A.build(rest)
            B.build(rest)
            for x in range(m):
                if not in_i[x]:
                    if A.can_add(x):
                        adj[y].append(x)
                    if B.can_add(x):
                        adj[x].append(y)
        # Multi-source BFS, stop at the first sink (shortest augmenting path)
        prv = [-2] * m
        q = deque()
        for x in range(m):
            if src[x]:
                prv[x] = -1
                q.append(x)
        end = -1
        while q:
            u = q.popleft()
            if sink[u]:
                end = u
                break
            for v in adj[u]:
                if prv[v] == -2:
                    prv[v] = u
                    q.append(v)
        if end < 0:
            break
        v = end
        while v != -1:
            in_i[v] = not in_i[v]
            v = prv[v]
    return [i for i in range(m) if in_i[i]]


def main():
    data = sys.stdin.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])
    edges, color = [], []
    for i in range(m):
        u, v, c = map(int, data[3 + 3 * i: 6 + 3 * i])
        edges.append((u, v))
        color.append(c - 1)
    I = matroid_intersection(m, GraphicMatroid(n, edges), PartitionMatroid(color, [1] * k))
    print(len(I))
    print(" ".join(str(e + 1) for e in I))


main()

Độ phức tạp

Gọi n=|E| và r là kích thước đáp án (r≤min(r(M1),r(M2))).

  • Số vòng tăng: mỗi vòng |I| tăng 1, nên có tối đa r+1 vòng (vòng cuối không tìm thấy đường).
  • Mỗi vòng: |I|+1≤r+1 lần build (một lần cho I, một lần cho mỗi I−y) và O(r·n) lần canAdd để dựng đồ thị trao đổi; đồ thị có O(r·n) cạnh nên BFS cũng tốn O(rn).
  • Tổng: O(r2n) lần gọi oracle cộng O(r2) lần build. Với matroid đồ thị (V đỉnh), build tốn O(V+r) và canAdd gần O(1) nhờ DSU, nên tổng khoảng O(r2(n+V)). Với matroid XOR B bit, mỗi oracle tốn O(B), tổng O(r2nB).
  • Bộ nhớ: O(rn) cho danh sách kề của đồ thị trao đổi (có thể bỏ, sinh cạnh ngay trong BFS, để còn O(n) nhưng phải gọi oracle lại).

Thử thực tế: V=300, m=2000 cạnh, 300 màu, đáp án r=299, chương trình C++ chạy khoảng 0,7 giây. Với r cỡ vài nghìn thì cần các cải tiến ở mục Biến thể.

⚠️ Lỗi thường gặp

  • Dùng DFS hoặc đường tăng bất kỳ thay vì đường ngắn nhất. Triệu chứng: tập kết quả có chu trình hoặc trùng màu, hoặc đáp án lớn hơn thực tế. Lý do: chỉ đường không lối tắt mới bảo đảm lật xong vẫn độc lập. Luôn dùng BFS nhiều nguồn, dừng ở đích đầu tiên lấy ra khỏi hàng đợi, và truy vết bằng mảng cha của BFS.
  • Đảo chiều cạnh của hai matroid. Quy ước phải nhất quán: nguồn theo M1 thì cạnh M1 đi từ y∈I sang x∉I, còn cạnh M2 đi từ x∉I sang y∈I, đích theo M2. Lẫn một chiều là thuật toán sai mà vẫn chạy ra số trông hợp lý; hãy so với brute force trên bộ nhỏ.
  • Kiểm tra I+x thay vì I−y+x khi dựng cạnh. Cạnh của đồ thị trao đổi hỏi về tập sau khi bỏ y. Phải build(I - y) rồi mới canAdd(x), không dùng lại oracle đã nạp I.
  • Quên đường độ dài 0. Phần tử vừa là nguồn vừa là đích thì chỉ cần thêm thẳng. Cài đặt BFS ở trên xử lý tự nhiên vì kiểm tra "là đích" ngay khi lấy đỉnh ra khỏi hàng đợi, kể cả với đỉnh nguồn.
  • Nghĩ tham lam là đủ. Tham lam trên giao hai matroid chỉ bảo đảm được ít nhất một nửa đáp án (ví dụ trên: 2 so với 3). Nếu bài có hai ràng buộc kiểu matroid chồng lên nhau, đó là tín hiệu cần giao matroid (hoặc luồng).
  • Mở rộng sang ba matroid. Giao ba matroid là NP-khó (đường đi Hamilton có hướng biểu diễn được như vậy). Đừng cố tổng quát hoá thuật toán cho 3 ràng buộc.
  • Khuyên (self-loop) và cạnh lặp. Khuyên u=v không bao giờ độc lập trong matroid đồ thị, DSU tự loại nó (cùng thành phần). Không được "bỏ qua" khuyên bằng cách coi nó độc lập.
  • Ước lượng độ phức tạp quá lạc quan. O(r2n) với r=n=2000 đã là 8·109. Đọc kỹ giới hạn: giao matroid ngây thơ hợp với n vài trăm đến khoảng 2000, r vài trăm.

Ứng dụng kinh điển

Cây khung nhiều màu (graphic × partition). Mỗi cạnh có một màu, màu j được dùng tối đa cj cạnh. M1 là matroid đồ thị, M2 là matroid phân hoạch theo màu với giới hạn cj. Có cây khung thoả mãn khi và chỉ khi đáp án bằng V−1. Code ở trên chỉ cần đổi vector<int>(k, 1) thành mảng giới hạn.

Cơ sở XOR có màu (linear × partition). Cho các số ai có màu, chọn nhiều số nhất độc lập tuyến tính (trên GF(2)) mà mỗi màu tối đa một số. Chỉ cần thay GraphicMatroid bằng oracle cơ sở XOR:

// Linear matroid over GF(2): a set of numbers is independent iff
// no non-empty subset XORs to 0 (i.e. they are linearly independent).
struct XorMatroid {
    vector<long long> val;
    long long basis[60];
    XorMatroid(vector<long long> v) : val(v) {}
    bool reduce(long long x, bool insert) {
        for (int b = 59; b >= 0; b--) {
            if (!(x >> b & 1)) continue;
            if (!basis[b]) {
                if (insert) basis[b] = x;
                return true;              // x is independent of the basis
            }
            x ^= basis[b];
        }
        return false;                     // x reduced to 0
    }
    void build(const vector<int>& S) {
        fill(basis, basis + 60, 0);
        for (int e : S) reduce(val[e], true);
    }
    bool canAdd(int x) { return reduce(val[x], false); }
};

Gọi XorMatroid X(a); PartitionMatroid P(color, vector<int>(k, 1)); matroidIntersection(m, X, P);. Số 0 không bao giờ độc lập, oracle tự loại nó.

Ghép cặp hai phía là trường hợp đặc biệt (partition × partition). Tập nền là các cạnh của đồ thị hai phía. M1: mỗi đỉnh trái thuộc tối đa một cạnh được chọn (phân hoạch cạnh theo đầu trái, c=1); M2: tương tự với đầu phải. Tập độc lập chung chính là cặp ghép, và đường tăng trong đồ thị trao đổi tương ứng với đường tăng xen kẽ quen thuộc. Thực tế ghép cặp nên dùng Kuhn hoặc Hopcroft-Karp cho nhanh, nhưng góc nhìn này giúp nhận ra rằng giao matroid là "ghép cặp tổng quát hoá".

Cây khung có hướng gốc r (arborescence). Chọn V−1 cung sao cho bỏ hướng là cây khung (M1: matroid đồ thị trên đồ thị vô hướng tương ứng) và mỗi đỉnh khác gốc có đúng một cung vào, gốc không có cung vào (M2: phân hoạch theo đỉnh đích, c=1, cung vào gốc có c=0). Bản có trọng số của bài này thường giải bằng thuật toán Chu-Liu/Edmonds nhanh hơn.

Biến thể / Mở rộng

  • Giao matroid có trọng số. Mỗi phần tử có trọng số w(x), tìm tập độc lập chung có tổng lớn nhất. Gán trọng số cho đỉnh của đồ thị trao đổi: x∉I mang chi phí −w(x) (thêm vào thì được w(x)), y∈I mang chi phí +w(y) (bỏ ra thì mất w(y)). Mỗi vòng tìm đường từ X1 tới X2 có tổng chi phí nhỏ nhất, hoà thì lấy đường ít cạnh nhất. Vì có chi phí âm nên dùng Bellman-Ford / SPFA (đồ thị trao đổi không có chu trình âm khi I đang tối ưu cho kích thước của nó). Sau vòng thứ k, I là tập độc lập chung kích thước k có trọng số lớn nhất; đáp án không giới hạn kích thước là giá trị tốt nhất qua mọi k. Ý tưởng giống hệt luồng chi phí nhỏ nhất tăng dần theo đường ngắn nhất.
  • Tăng tốc. Thuật toán Cunningham tìm nhiều đường tăng ngắn nhất rời nhau mỗi pha (giống Hopcroft-Karp), giảm còn O(r1.5n) lần gọi oracle. Với matroid đồ thị và phân hoạch còn có thể dựng cạnh nhanh hơn: với M1 đồ thị, y→x khi và chỉ khi I+x có chu trình đi qua y (hoặc I+x là rừng), nên chỉ cần tìm đường trên cây.
  • Hợp matroid (matroid union / partition). Câu hỏi "phủ được E bằng k tập độc lập không", hay "đồ thị có k cây khung rời cạnh không", quy về giao matroid: nhân bản mỗi phần tử k lần, lấy giao của "hợp rời k bản sao của M" với matroid phân hoạch "mỗi phần tử gốc chọn tối đa một bản".
  • Tính chất trao đổi tự nó đã mạnh. Nhiều bài không cần giao matroid đầy đủ, chỉ cần tiên đề trao đổi: ví dụ "số cạnh đỏ trong một cây khung nhận mọi giá trị trong một đoạn [kmin,kmax]" vì từ một cây khung có thể đổi từng cạnh một làm số cạnh đỏ thay đổi đúng 1.

Bài tập luyện

Hiện CTOJ chưa có bài đòi đúng giao matroid tổng quát; các bài dưới đây luyện các khối xây dựng: nhận ra matroid, tham lam trên matroid, tính chất trao đổi và các oracle (DSU, cơ sở XOR).

  • Mạng công ty (dhbb2410comnet): (Khó) Chọn k−1 dây rẻ nhất để đấu nối lại sao cho gỡ chúng ra không làm tăng số thành phần liên thông. Các tập dây như vậy là tập độc lập của matroid đối ngẫu của matroid đồ thị, nên tham lam theo chi phí (tương đương dựng rừng khung lớn nhất) là tối ưu.
  • Mạng truyền thông (voi14_aznet): (Rất khó) Cây khung gồm cạnh của hai công ty, chi phí chỉ phụ thuộc số cạnh mỗi bên. Dùng tính chất trao đổi của cây khung để chứng minh các số lượng đạt được là một đoạn liên tục, rồi dựng cây đúng số lượng bằng DSU.
  • XOR cực đại tập con (xorbasis): (Rất khó) Dựng cơ sở XOR, chính là oracle độc lập của matroid tuyến tính dùng trong XorMatroid ở trên, rồi tham lam từ bit cao xuống.
  • Cơn Ác Mộng Euclid (eucz2): (Rất khó) Vector trên ℤ2 có tối đa hai bit 1: nhận ra matroid tuyến tính này thực chất là matroid đồ thị (thêm một đỉnh giả), rồi tham lam theo thứ tự chỉ số để được cơ sở nhỏ nhất theo thứ tự từ điển.
  • Bàn thắng (icpc23mng): (Chuyên gia) Tập khung thành mà người đi sau thắng được cùng lúc (điều kiện Hall) là một matroid ghép cặp (transversal matroid), nên tham lam theo điểm giảm dần là tối ưu; kết hợp với lập luận về nước đi của người đi trước và quy hoạch động xác suất.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0