Matroid được phát triển vào năm 1935 bởi Hassler Whitney như là một cấu trúc tổng quát hóa khá niệm độc lập (independence) của các vector. Matroid có rất nhiều ứng dụng trong các lĩnh vực khác nhau như chúng ta thấy trong bài viết wikipeidia. Trong bài này mình sẽ giới thiệu matroid trên phương diện thuật toán tham lam. Rất nhiều các bài toán giải được bằng phương pháp tham lam có thể được mô tả bởi cấu trúc matroid. Để có một cái nhìn tổng quát hơn, bạn đọc có thể tham khảo tham tại [2].

Matroid là gì

Một matroid $\mathcal{M}$ là một họ các tập hợp thỏa mãn các điều kiện sau:

1. Non-emptiness (không rỗng): tập rỗng là một phần tử của $\mathcal{M}$, i.e, $\emptyset \in \mathcal{M}$.
2. Heredity (kế thừa) : Nếu một tập $X \in \mathcal{M}$, tất cả các tập con của $X$ cũng thuộc $\mathcal{M}$.
3. Exchange (trao đổi) : Nếu $X$ và $Y$ là hai tập hợp trong $\mathcal{M}$ và $|X| > |Y|$, luôn tồn tại một phần tử $x \in X\setminus Y$ sao cho $Y \cup \{x\} \in \mathcal{M}$

Các tập hợp trong $\mathcal{M}$ được gọi là một tập độc lập (independent set). Như vậy, tính chất kế thừa còn có thể được phát biểu lại là: tập con của một tập độc lập là một tập độc lập. Tập hợp $E = \cup_{X \in \mathcal{M}} X$ được gọi là tập gốc (ground set) của matroid, đó là tập gồm tất cả các phần tử xuất hiện trong các tập hợp của matroid. Tập con của $E$ không thuộc $\mathcal{M}$ được goị là một tập phụ thuộc (dependent set) và một tập phụ thuộc được gọi là chu trình (circuit) nếu mọi tập con đúng của tập đó là tập độc lập. Một cơ sở (basis) của matroid là tập độc lập tối đại (maximal), i.e, không có tập độc lập nào chứa nó ngoại trừ chính nó. Hạng (rank) của tập $X \subseteq E$ là kích thước của tập độc con độc lập lớn nhất của $X$. Hạng của matroid là hạng của một cơ sở (bất kì) của matroid.

Trên đây là định nghĩa matroid và những khái niệm cơ bản xung quanh matroid. Thông thường để kiểm tra một họ các tập hợp có phải là matroid hay không, tính chất 3 luôn là tính chất khó kiểm tra nhất. Bây giờ chúng ta hãy xét ví dụ đặc trưng sau:

Matroid tuyến tính (linear matroid): Gọi $A$ là ma trận $n \times m$. Tập $I \subseteq \{1,2,\ldots,n\} = E$ gọi là độc lập nếu các vector cột $\{v_i| i \in I\}$ là độc lập tuyến tính. Ta có thể dễ dàng kiểm tra tính chất 1 và 2 của matroid dựa vào định nghĩa của độc lập tuyến tính. Tính chất 3 dựa vào tính chất đại số của tập các vector độc lập.

Các ví dụ khác thường gặp:

• Matroid đồng nhất $U_{k,n}$: Một tập $X \subseteq \{1,2,\ldots,n\} = E$ được gọi là độc lập nếu $|X| \leq k$. Bất kì tập nào có kích thước $k$ đều là cơ sở. Bất kì một tập nào có kích thước lớn hơn $k$ đều là phụ thuộc.
• Graphic Matroid: Cho một đồ thị vô hướng $G = (V,E)$, tập các cạnh $X \subseteq E$ được gọi là độc lập nếu đồ thị $G = (V, X)$ không có chu trình, i.e, là một forest. Cơ sở của matroid là một cây khung (spanning tree), và chu trình (cycle) của đồ thị cũng chính là chu trình của matroid.
• Cographic Matroid: Cho một đồ thị vô hướng $G = (V,E)$, tập các cạnh $X \subseteq E$ được gọi là độc lập nếu đồ thị phần bù $G = (V, E\setminus X)$ liên thông, i.e,. Cơ sở của matroid là phần bù của một cây khung (bất kì).
• Matching Matroid: Cho một đồ thị vô hướng $G = (V,E)$, tập các đỉnh $X \subseteq V$ được gọi là độc lập nếu tồn tại một matching phủ toàn bộ $X$. Một đỉnh được gọi là phủ bở một matching nếu tồn tại một cạnh của matching kề với đỉnh đó.
• Disjoint Path Matroid: Cho một đồ thị có hướng $G = (V,E)$ và một đỉnh $s$ cố định. Tập các đỉnh $X \subseteq V$ được gọi là độc lập nếu tồn tại một tập các edge-disjoint paths từ $s$ tới các đỉnh trong tập $X$.

Chúng ta xét bài toán tìm cơ sở có trọng số lớn nhất của matroid sau:

 
Trước hết chúng ta hãy xem ý nghĩa của Theorem 1. Áp dụng Theorem 1 vào Graphic Matroid, chúng ta có thể tìm được cây khung có trọng số lớn nhất của đồ thị trong thời gian $O(n^2)$. Áp dụng Theorem 1 vào Cographic Matroid, chúng ta có thể tìm được tập $X$ trọng số lớn nhất của đồ thị trong thời gian $O(n^2)$, qua đó, tìm được $E \setminus X$ là cây khung có trọng số nhỏ nhất trong thời gian $O(n^2)$.

Bay giờ ta trở lại thuật toán cho Theorem 1. Ý tưởng của thuật toán khá đơn giản: sắp xếp các phần tử của tập gốc $E$ theo chiều giảm dần trọng số và lần lượt đưa các phần tử vào phương án hiện tại nếu nó không phá vỡ tính độc lập. Chi tiết như sau:

Trong thuật toán trên, để sắp xếp ta mất thời gian $O(n \log n)$ và để thực hiện vòng lặp for, ta mất thời gian $O(nF(n))$ trong đó $F(n)$ là thời gian để kiểm tra một tập có phải là độc lập hay không. Do đó tổng thời gian là $O(n\log n + nF(n))$. Vấn đề còn lại là chứng minh thuật toán tham lam cho lời giải tối ưu.

 
Chứng minh: Dựa vào tính chất trao đổi và tính chất kế thừa của matroid, ta có thể chứng minh được mọi cơ sở đều có kích thước bằng nhau và bất kì tập độc lập tối đại (maximal) nào cũng là một cơ sở. Gọi $X = \{x_1,x_2,\ldots, x_k\}$ là tập các phần tử đầu ra của thuật toán tham lam, sắp xếp theo chiều giảm dần của trọng số. Vì $X$ là tối đại, $X$ sẽ là một cơ sở của matroid $\mathcal{M}$. Ta sẽ sử dụng kĩ thuật chứng minh trong bài này để chứng minh $X$ có trọng số lớn nhất.

Giả sử tồn tại một cơ sở có kích thước lớn nhất $Y = \{y_1,y_2,\ldots, y_k\}$, , sắp xếp theo chiều giảm dần của trọng số, sao cho $w(Y) > w(X)$. Goi $i$ là chỉ số nhỏ nhất sao cho $w(x_i) < w(y_i)$. Suy ra $x_{j} \leq y_{j}$ với mọi $1 \leq j \leq i-1$. Do tính chất kế thừa: $X_{i-1} = {x_1,x_2, \ldots, x_{i-1}, x_{i-1}}$ và $Y_i = \{y_1,y_2,\ldots, y_{i}\}$ đều là các tập độc lập. Do $|X_{i-1}| < |Y_i|$, theo tính chất trao đổi, tồn tại $y_t \in Y_i \setminus X_{i-1}$ sao cho $X_{i-1} \cup \{y_t\}$ là một tập độc lập. Do $y_t \geq y_{i} > x_{i}$, thuật toán tham lam sẽ duyệt qua $y_t$ trước khi duyệt đến $x_{i}$. Nhưng theo tính chất kế thừa, $y_t \in X_{i-1}$, điều này không thể xảy ra. Do đó chỉ số $i$ không tồn tại, hay nói cách khác, $X$ là một phương án tối ưu.

Ứng dụng trong bài toán lập lịch
Phần này chúng ta trở lại bài toán lập lịch với thời hạn và tiền thưởng đã giới thiệu ở bài trước. Chúng ta đã làm quen với thuật toán tham lam để giải bài toán lập lịch đó. Trong bài này, chúng ta sẽ nhìn bài toán đó dưới góc độ matroid. Mình nhắc lại bài toán ở đây:

 
Gọi tập các tác vụ là độc lập nếu tồn tai một cách thực thi sao cho tất cả các tác vụ trong tập hợp đó được thực thi trước thời hạn. Gọi $\mathcal{M}$ là họ các tập độc lập. Ta chứng minh thuật toán tham lam trong bài trước cho lời giải tối ưu bằng cách chứng minh bổ đề sau:

 
Chứng minh: Ta có thể dễ dàng kiểm tra tính không rỗng và tính kế thừa của $\mathcal{M}$. Vấn đề khó khăn nhất chính là kiểm tra tính trao đổi. Gọi $X = \{x_1,x_2,\ldots, x_k\}$ là một tập độc lập với các tác vụ được sắp xếp theo chiều tăng dần của thời hạn. Gọi $X_t = \{x \in X | D[x] \leq t\}$ là tập các tác vụ trong $X$ có thời hạn trước $t$. Ta có nhận xét sau:

.
Gọi $Y = \{y_1,y_2,\ldots, y_{k'}\}$ là tập độc lập kích thước $k' > k$ với các tác vụ được sắp xếp theo chiều tăng dần của thời hạn. $Y_t$ cũng được định nghĩa như $X_t$. Do $|Y_0| = 0 \leq 0 = |X_0|$ và $|X_{k'}| = k < |Y_{k'}| = k'$, tồn tại một số $i$ lớn nhất sao cho $|Y_i| \leq |X_i|$. Do đó $|Y_{i+1}| > |X_{i+1}|$. Suy ra tồn tại ít nhất một tác vụ $j$ có thời hạn $ \leq i+1$ trong $Y \setminus X$. Theo nhận xét trên, $i+1 \geq |Y_{i+1}| > |X_{i+1}|$, ta có thể chèn tác vụ $j$ và sau vị trí $i$ của $X$ mà không làm thay đổi tính độc lập. Do đó, tính chất trao đổi được thỏa mãn.

Tham khảo
[1] Jeff Erickson, Algorithms Lecture Notes, UIUC.
[2] Oxley, James. What is a matroid? Cubo Matemática Educacional 5.3 (2003): 179-218.
[3] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill (2001). ISBN 0-262-03293-7.
[4]https://kunigami.wordpress.com/2013/11/11/lawler-and-an-introduction-to-matroids/