14.2K 212 1.7K

Đã đăng vào khoảng 7 giờ trước 8 phút đọc

Cấu trúc dữ liệu và Giải thuật Bài 132: Giao hai Matroid (Matroid Intersection) - Cấu trúc đại số tối thượng giải quyết các bài toán tối ưu tổ hợp phức tạp.

Trong lý thuyết tối ưu hóa tổ hợp, thuật toán tham lam (Greedy Algorithm) thường chỉ giải quyết được các bài toán có cấu trúc đặc biệt đơn giản — chẳng hạn như thuật toán Kruskal tìm Cây khung nhỏ nhất (MST) trên đồ thị vô hướng. Khi bài toán xuất hiện đồng thời hai ràng buộc độc lập, chiến lược tham lam thuần túy sẽ thất bại:

Tìm cây khung mà mỗi cạnh phải có màu sắc khác nhau (Cây khung đa sắc - Rainbow Spanning Tree).
Tìm số lượng đường đi có đỉnh rời nhau tối đa giữa hai tập đỉnh.
Ghép cặp cực đại trên đồ thị hai phía (Maximum Bipartite Matching) dưới góc nhìn đại số.

Điểm chung của các bài toán trên là chúng đều có thể phân rã thành bài toán tìm tập hợp độc lập chung của hai cấu trúc Matroid.

Trong khi bài toán tối ưu trên một Matroid đơn lẻ luôn giải được bằng thuật toán tham lam (Định lý Rado-Edmonds), và bài toán giao từ ba Matroid trở lên là NP-hard (chứa bài toán Đường đi Hamilton), thì Giao hai Matroid (2-Matroid Intersection) là một ranh giới đặc biệt: nó có thể giải được chính xác trong thời gian đa thức (Polynomial Time) thông qua kỹ thuật Đồ thị trao đổi (Exchange Graph) và Đường tăng luồng (Augmenting Path).

1. Cơ sở lý thuyết: Cấu trúc Đại số Matroid

Một Matroid $M$ là một cấu trúc đại số định nghĩa trên một cặp $M = (E, \mathcal{I})$ , trong đó $E$ là một tập hợp hữu hạn các phần tử (Ground Set), và $\mathcal{I}$ là một họ các tập con của $E$ (gọi là các tập độc lập - Independent Sets), thỏa mãn 3 tiên đề:

Tiên đề tập rỗng (Non-emptiness): $\emptyset \in \mathcal{I}$ .
Tiên đề di truyền (Hereditary property): Nếu $A \in \mathcal{I}$ và $B \subseteq A$ , thì $B \in \mathcal{I}$ .
Tiên đề mở rộng / trao đổi (Augmentation / Independent Set Exchange): Nếu $A, B \in \mathcal{I}$ và $\vert{}A\vert{} < \vert{}B\vert{}$ , thì tồn tại ít nhất một phần tử $e \in B \setminus A$ sao cho $A \cup \{e\} \in \mathcal{I}$ .

Các họ Matroid tiêu biểu

Graphic Matroid: $E$ là tập các cạnh của đồ thị $G$ . Một tập con các cạnh $A \subseteq E$ là độc lập nếu $A$ không chứa chu trình (tức là $A$ tạo thành một rừng cây - Forest).
Partition Matroid: $E$ được phân chia thành các khối rời nhau $E_1, E_2, \dots, E_k$ . $A \subseteq E$ là độc lập nếu $\vert{}A \cap E_i\vert{} \le d_i$ với mọi $i$ . Ví dụ: mỗi cạnh có một màu, và mỗi màu chỉ được chọn tối đa 1 cạnh ( $d_i = 1$ ).
Linear (Vector) Matroid: $E$ là tập các vector trong không gian vector. $A \subseteq E$ là độc lập nếu các vector trong $A$ độc lập tuyến tính.

2. Bài toán Giao hai Matroid (Matroid Intersection)

Cho hai Matroid $M_1 = (E, \mathcal{I}_1)$ và $M_2 = (E, \mathcal{I}_2)$ được định nghĩa trên cùng một tập cơ sở $E$ .

Mục tiêu là tìm một tập hợp con $I \subseteq E$ có kích thước lớn nhất sao cho $I$ đồng thời độc lập trong cả hai Matroid:

$I \in \mathcal{I}_1 \cap \mathcal{I}_2 \quad \text{sao cho} \quad \vert{}I\vert{} \to \max$

Lưu ý then chốt: Giao của hai Matroid nói chung không phải là một Matroid (vì nó không thỏa mãn tiên đề mở rộng số 3). Do đó, thuật toán tham lam không áp dụng được trực tiếp.

3. Đồ thị Trao đổi (Exchange Graph) và Đường tăng luồng

Tương tự như thuật toán tìm luồng cực đại (Max Flow) hay thuật toán Blossom (Bài 130), Jack Edmonds và Eugene Lawler đã chứng minh rằng ta có thể xuất phát từ tập rỗng $I = \emptyset$ và tăng dần kích thước của $I$ thêm 1 đơn vị ở mỗi bước bằng cách tìm đường tăng luồng ngắn nhất trên Đồ thị trao đổi (Exchange Graph).

Giả sử hiện tại ta có một tập độc lập chung $I \in \mathcal{I}_1 \cap \mathcal{I}_2$ . Ta xây dựng đồ thị có hướng $D_{M_1, M_2}(I) = (V_D, E_D)$ với tập đỉnh chính là $E$ :

Phân loại đỉnh

Tập đỉnh $I$ : Các phần tử đang được chọn.
Tập đỉnh $E \setminus I$ : Các phần tử chưa được chọn.

Xác định nguồn (Sources) và đích (Sinks)

Tập nguồn $X_1$ : Tập các phần tử $y \in E \setminus I$ có thể thêm trực tiếp vào $I$ mà vẫn độc lập trong $M_1$ :

$X_1 = \{ y \in E \setminus I \mid I \cup \{y\} \in \mathcal{I}_1 \}$
Tập đích $X_2$ : Tập các phần tử $y \in E \setminus I$ có thể thêm trực tiếp vào $I$ mà vẫn độc lập trong $M_2$ :

$X_2 = \{ y \in E \setminus I \mid I \cup \{y\} \in \mathcal{I}_2 \}$

Nếu $X_1 \cap X_2 \neq \emptyset$ , ta có thể chọn ngay một phần tử bất kỳ $y \in X_1 \cap X_2$ và thêm vào $I$ ( $I \gets I \cup \{y\}$ ).

Thiết lập các cung trao đổi có hướng (Exchange Arcs)

Nếu $X_1 \cap X_2 = \emptyset$ , ta dựng các cung có hướng giữa $E \setminus I$ và $I$ :

Cung từ $y \in E \setminus I$ sang $x \in I$ : Tồn tại nếu việc hoán đổi $y$ vào và bỏ $x$ ra vẫn giữ tính độc lập trong $M_1$ :

$(I \setminus \{x\}) \cup \{y\} \in \mathcal{I}_1$
Cung từ $x \in I$ sang $y \in E \setminus I$ : Tồn tại nếu việc hoán đổi $y$ vào và bỏ $x$ ra vẫn giữ tính độc lập trong $M_2$ :

$(I \setminus \{x\}) \cup \{y\} \in \mathcal{I}_2$

        Tập nguồn X1                  Tập I                      Tập đích X2
       (Trong E \ I)              (Đang được chọn)              (Trong E \ I)
          +----+                                                   +----+
          | y1 | -------------> +----+                             | y2 |
          +----+   (theo M1)    | x1 | -------------> +----+       +----+
                                +----+   (theo M2)    | y3 | ---->   ^
                                                      +----+         |
                                                        |   (theo M2)|
                                                        +------------+

Thuật toán Tăng kích thước (Augmentation Step)

Dùng BFS tìm đường đi có hướng ngắn nhất (số cạnh ít nhất) từ bất kỳ đỉnh nào trong $X_1$ đến bất kỳ đỉnh nào trong $X_2$ :

$P = (y_1, x_1, y_2, x_2, \dots, x_{k-1}, y_k)$
(với $y_1 \in X_1$ và $y_k \in X_2$ ).
Nếu không tìm thấy đường đi nào từ $X_1$ đến $X_2$ , tập $I$ hiện tại đã đạt kích thước cực đại toàn cục.
Nếu tìm thấy đường đi $P$ , cập nhật tập $I$ bằng phép hiệu đối xứng (Symmetric Difference):

$I \gets I \oplus P = (I \setminus \{x_1, x_2, \dots, x_{k-1}\}) \cup \{y_1, y_2, \dots, y_k\}$
Kích thước của $I$ tăng thêm đúng 1 phần tử ( $\vert{}I\vert{} \gets \vert{}I\vert{} + 1$ ).
Lặp lại cho đến khi không còn đường tăng luồng.

4. Hiện thực hóa Matroid Intersection bằng Golang

Bài toán kinh điển: Rừng cây đa sắc (Colorful Forest).

Cho một đồ thị có trọng số/không trọng số gồm $V$ đỉnh và $E$ cạnh. Mỗi cạnh được gán một màu sắc nhất định.
Cần tìm tập cạnh lớn nhất thỏa mãn đồng thời:
1. Không tạo thành chu trình (Độc lập trong Graphic Matroid $M_1$ ).
2. Không có hai cạnh nào cùng màu (Độc lập trong Partition Matroid $M_2$ ).
Nếu kích thước tập cạnh tìm được đạt $V - 1$ , đó chính là một Cây khung đa sắc (Rainbow Spanning Tree).

package main

import (
	"fmt"
)

// Cạnh của đồ thị
type Edge struct {
	id    int
	u, v  int
	color int
}

// Cấu trúc Disjoint Set Union (DSU) để kiểm tra tính độc lập trong Graphic Matroid
type DSU struct {
	parent []int
}

func NewDSU(n int) *DSU {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	return &DSU{parent: p}
}

func (d *DSU) Find(i int) int {
	if d.parent[i] == i {
		return i
	}
	d.parent[i] = d.Find(d.parent[i])
	return d.parent[i]
}

func (d *DSU) Union(i, j int) bool {
	rootI := d.Find(i)
	rootJ := d.Find(j)
	if rootI != rootJ {
		d.parent[rootI] = rootJ
		return true
	}
	return false
}

type MatroidIntersection struct {
	numVertices int
	edges       []Edge
	m           int // Số lượng cạnh (|E|)
}

func NewMatroidIntersection(numVertices int, edges []Edge) *MatroidIntersection {
	return &MatroidIntersection{
		numVertices: numVertices,
		edges:       edges,
		m:           len(edges),
	}
}

// Oracle M1: Kiểm tra tập cạnh candidate có tạo thành Rừng (Graphic Matroid) không
func (mi *MatroidIntersection) checkM1(inSet []bool) bool {
	dsu := NewDSU(mi.numVertices)
	for i := 0; i < mi.m; i++ {
		if inSet[i] {
			if !dsu.Union(mi.edges[i].u, mi.edges[i].v) {
				return false // Phát hiện chu trình
			}
		}
	}
	return true
}

// Oracle M2: Kiểm tra tập cạnh candidate có bị trùng màu (Partition Matroid) không
func (mi *MatroidIntersection) checkM2(inSet []bool) bool {
	seenColor := make(map[int]bool)
	for i := 0; i < mi.m; i++ {
		if inSet[i] {
			c := mi.edges[i].color
			if seenColor[c] {
				return false // Bị trùng màu
			}
			seenColor[c] = true
		}
	}
	return true
}

// Thuật toán Matroid Intersection tìm tập độc lập chung cực đại
func (mi *MatroidIntersection) MaxIndependentSet() []Edge {
	inI := make([]bool, mi.m) // inI[e] = true nghĩa là cạnh e thuộc tập I hiện tại

	for {
		// 1. Xác định tập nguồn X1 và tập đích X2
		x1 := make([]int, 0)
		x2 := make([]int, 0)
		isX2 := make([]bool, mi.m)

		for y := 0; y < mi.m; y++ {
			if !inI[y] {
				// Thử thêm y vào I
				inI[y] = true
				if mi.checkM1(inI) {
					x1 = append(x1, y)
				}
				if mi.checkM2(inI) {
					x2 = append(x2, y)
					isX2[y] = true
				}
				inI[y] = false
			}
		}

		// Nếu có phần tử thuộc cả X1 và X2, nạp ngay vào I
		directAdd := -1
		for _, y := range x1 {
			if isX2[y] {
				directAdd = y
				break
			}
		}
		if directAdd != -1 {
			inI[directAdd] = true
			continue
		}

		// 2. Dựng Đồ thị trao đổi (Exchange Graph)
		adj := make([][]int, mi.m)

		for y := 0; y < mi.m; y++ {
			if !inI[y] {
				for x := 0; x < mi.m; x++ {
					if inI[x] {
						// Kiểm tra cung y -> x (M1: I \ {x} U {y})
						inI[y] = true
						inI[x] = false
						if mi.checkM1(inI) {
							adj[y] = append(adj[y], x)
						}
						// Kiểm tra cung x -> y (M2: I \ {x} U {y})
						if mi.checkM2(inI) {
							adj[x] = append(adj[x], y)
						}
						inI[y] = false
						inI[x] = true
					}
				}
			}
		}

		// 3. BFS tìm đường tăng luồng ngắn nhất từ X1 đến X2
		queue := make([]int, 0)
		prev := make([]int, mi.m)
		visited := make([]bool, mi.m)
		for i := 0; i < mi.m; i++ {
			prev[i] = -1
		}

		for _, src := range x1 {
			queue = append(queue, src)
			visited[src] = true
		}

		target := -1
		for len(queue) > 0 {
			curr := queue[0]
			queue = queue[1:]

			if isX2[curr] {
				target = curr
				break
			}

			for _, next := range adj[curr] {
				if !visited[next] {
					visited[next] = true
					prev[next] = curr
					queue = append(queue, next)
				}
			}
		}

		// Không tìm thấy đường đi từ X1 đến X2 -> Tập I đã cực đại
		if target == -1 {
			break
		}

		// 4. Lần ngược đường đi và cập nhật I = I ^ P
		curr := target
		for curr != -1 {
			inI[curr] = !inI[curr]
			curr = prev[curr]
		}
	}

	result := make([]Edge, 0)
	for i := 0; i < mi.m; i++ {
		if inI[i] {
			result = append(result, mi.edges[i])
		}
	}
	return result
}

func main() {
	// Đồ thị 4 đỉnh (0, 1, 2, 3) với 5 cạnh và các màu sắc khác nhau
	numVertices := 4
	edges := []Edge{
		{id: 0, u: 0, v: 1, color: 1}, // Cạnh 0: màu 1
		{id: 1, u: 1, v: 2, color: 1}, // Cạnh 1: màu 1 (trùng màu với cạnh 0)
		{id: 2, u: 2, v: 3, color: 2}, // Cạnh 2: màu 2
		{id: 3, u: 3, v: 0, color: 3}, // Cạnh 3: màu 3
		{id: 4, u: 0, v: 2, color: 2}, // Cạnh 4: màu 2 (trùng màu với cạnh 2)
	}

	solver := NewMatroidIntersection(numVertices, edges)
	rainbowForest := solver.MaxIndependentSet()

	fmt.Printf("Số lượng cạnh tối đa trong Rừng cây đa sắc: %d cạnh\n", len(rainbowForest))
	fmt.Println("Chi tiết các cạnh được chọn:")
	for _, e := range rainbowForest {
		fmt.Printf("- Cạnh %d: (%d <-> %d) | Màu: %d\n", e.id, e.u, e.v, e.color)
	}

	if len(rainbowForest) == numVertices-1 {
		fmt.Println("=> Đã tìm thấy Cây khung đa sắc (Rainbow Spanning Tree) hoàn hảo!")
	} else {
		fmt.Println("=> Không tồn tại cây khung đa sắc bao phủ toàn bộ đỉnh.")
	}
}

5. Phân tích độ phức tạp thuật toán

Gọi:

$n = \vert{}E\vert{}$ là số lượng phần tử của Ground Set.
$r = \max(\vert{}I\vert{}) \le n$ là hạng (rank) của giao Matroid (kích thước tập độc lập cực đại).
$T_{\text{oracle}}$ là thời gian kiểm tra tính độc lập trong mỗi Matroid (Independence Oracle). Với Graphic Matroid dùng DSU, $T_{\text{oracle}} \approx O(n \alpha(V))$ ; với Partition Matroid, $T_{\text{oracle}} \approx O(n)$ .

Giai đoạn	Số lần thực thi	Chi phí mỗi lần	Tổng độ phức tạp
Số lần tăng luồng (Augmentations)	Tối đa $r$ lần	—	$\le r$ vòng lặp lớn
Xác định nguồn $X_1$ và đích $X_2$	Mỗi vòng lặp 1 lần	$O(n \cdot T_{\text{oracle}})$	$O(r \cdot n \cdot T_{\text{oracle}})$
Dựng Đồ thị trao đổi ( $D_{M_1, M_2}$ )	Mỗi vòng lặp 1 lần	$O(n \cdot r \cdot T_{\text{oracle}})$	$O(r^2 \cdot n \cdot T_{\text{oracle}})$
Tìm đường đi ngắn nhất (BFS)	Mỗi vòng lặp 1 lần	$O(n +	E_D
Tổng thể thuật toán cơ bản	—	—	$O(r^2 \cdot n \cdot T_{\text{oracle}})$

Với kỹ thuật Cunningham (1986), bằng cách tìm nhiều đường tăng luồng rời rạc có cùng độ dài ngắn nhất trong một pha duyệt (tương tự như Dinic trong Max Flow), độ phức tạp có thể giảm xuống $O(r^{1.5} \cdot n \cdot T_{\text{oracle}})$ .

6. Ứng dụng thực tế

Bài toán Cây khung đa sắc & Mạng phủ bền vững: Trong thiết kế mạng viễn thông quang học, mỗi liên kết cáp được thuê từ một nhà cung cấp hạ tầng viễn thông khác nhau (mỗi nhà cung cấp tương ứng một màu). Mục tiêu là thiết lập cây định tuyến khung mà không bao giờ phụ thuộc vào hai đường dây từ cùng một nhà mạng, phòng ngừa rủi ro đứt cáp diện rộng.
Bài toán Phân bổ tần số vô tuyến (Wireless Channel Assignment): Ghép nối các trạm phát sóng với các kênh tần số sao cho không xảy ra giao thoa trường sóng (Graphic/Matroid can thiệp) và không vượt quá hạn mức phân bổ băng tần của cơ quan quản lý (Partition Matroid).
Định lý Phân rã cây phân nhánh của Edmonds (Packing Arborescences): Phân tích xem một mạng phân phối có thể chứa đồng thời bao nhiêu cây phân nhánh có hướng rời nhau về cạnh (Edge-disjoint Arborescences), đóng vai trò nền tảng trong truyền dữ liệu song song đa kênh chịu lỗi.

cấu trúc dữ liệu