Cấu trúc dữ liệu và Giải thuật Bài 130: Thuật toán Blossom (Edmonds' Blossom Algorithm) - Ghép cặp cực đại trên đồ thị tổng quát bằng kỹ thuật co chu trình lẻ

Ở Bài 112, chúng ta đã giải quyết bài toán Ghép cặp cực đại trên Đồ thị hai phía (Maximum Bipartite Matching) bằng thuật toán Hopcroft-Karp trong thời gian $O(E \sqrt{V})$ . Trong đồ thị hai phía, cấu trúc không bao giờ chứa chu trình có độ dài lẻ ( $C_3, C_5, \dots$ ), cho phép ta phân chia các đỉnh thành hai tập độc lập và tìm đường tăng luồng (Augmenting Path) thông qua BFS/DFS định hướng luồng một cách tự nhiên.

Tuy nhiên, trong các bài toán phân bổ nguồn lực tổng quát — chẳng hạn như ghép đôi người ở ghép (Stable Roommates Problem), lập lịch ghép cặp đối kháng 1-1 không phân biệt vai trò, hay thiết kế cấu trúc mạng viễn thông bất đối xứng — đồ thị không thể phân chia thành hai phía. Khi đó, sự xuất hiện của chu trình độ dài lẻ (Odd-length Cycle) phá hủy tính đúng đắn của các thuật toán tìm đường xen kẽ thông thường.

Năm 1965, Jack Edmonds công bố công trình "Paths, Trees, and Flowers" giới thiệu Thuật toán Blossom (Edmonds' Blossom Algorithm). Thuật toán này chứng minh rằng bài toán Ghép cặp cực đại trên đồ thị tổng quát có thể giải được trong thời gian đa thức nhờ kỹ thuật co chu trình lẻ (Blossom Contraction), mở ra kỷ nguyên của lý thuyết Đa thức hóa (P-time algorithms) trong tối ưu tổ hợp.

1. Tử huyệt của Chu trình lẻ đối với Bổ đề Berge

Nhắc lại Bổ đề Berge (Berge's Lemma): Một tập ghép $M$ trên đồ thị $G$ là cực đại khi và chỉ khi $G$ không còn tồn tại đường tăng luồng (Augmenting Path) đối với $M$ .

Đường đi xen kẽ (Alternating Path): Đường đi có các cạnh xen kẽ luân phiên giữa: không thuộc $M \to$ thuộc $M \to$ không thuộc $M \dots$
Đường tăng luồng (Augmenting Path): Đường đi xen kẽ bắt đầu và kết thúc tại hai đỉnh chưa được ghép (free/unmatched vertices).

       Đồ thị hai phía:                             Đồ thị chứa chu trình lẻ:
       (Duyệt tầng chẵn/lẻ rõ ràng)                  (Nút 3 vừa là Chẵn vừa là Lẻ!)
          (A) --- [m] --- (B)                                  (1) [Free]
           |               |                                  /   \
          [m]             [m]                                (2)---(3) [Chu trình lẻ C3]
           |               |                                  |     |
          (C) --- [m] --- (D)                                [m]   [m]
                                                              |     |
                                                             (4)---(5)

Trên đồ thị hai phía, mọi chu trình đều có độ dài chẵn, do đó khoảng cách tính từ gốc duyệt luôn xác định một đỉnh là nút loại "Chẵn" (Even - cách gốc số cạnh chẵn) hoặc nút loại "Lẻ" (Odd - cách gốc số cạnh lẻ).

Trên đồ thị tổng quát, nếu tồn tại một chu trình lẻ:

Một đỉnh nằm trên chu trình lẻ có thể vừa cách gốc một số chẵn cạnh, vừa cách gốc một số lẻ cạnh tùy theo chiều đi quanh chu trình.
Khi thuật toán BFS chạm vào một cạnh nối giữa hai nút cùng là loại "Chẵn", nó không thể xác định hướng đi tiếp để duy trì tính xen kẽ của đường đi, dẫn đến việc bỏ sót các đường tăng luồng hợp lệ.

2. Mô hình "Cuống và Bông hoa" (Stem & Blossom)

Edmonds đã giải quyết bài toán bằng cách hình thức hóa cấu trúc chu trình lẻ:

Bông hoa (Blossom - $B$ ): Một chu trình đơn có độ dài lẻ $2k + 1$ cạnh, trong đó chứa đúng $k$ cạnh thuộc tập ghép $M$ và $k + 1$ cạnh không thuộc $M$ .
Gốc bông hoa (Base of Blossom): Đỉnh duy nhất trong chu trình $B$ kề với hai cạnh không thuộc $M$ bên trong chu trình (nói cách khác, là đỉnh duy nhất có cạnh ghép đi ra ngoài chu trình, hoặc chính là đỉnh tự do).
Cuống hoa (Stem): Một đường đi xen kẽ có độ dài chẵn xuất phát từ một đỉnh tự do (gốc của cây BFS) đến đỉnh Base của bông hoa.

              (Gốc tự do r)
                   |
                  [m]   <-- Cuống hoa (Stem - độ dài chẵn)
                   |
                 (Base) <------------------+
                /      \                   |
               o        o                  | Bông hoa (Blossom)
               |        |                  | (Chu trình lẻ 2k + 1 cạnh)
              [m]      [m]                 |
               \        /                  |
                o ---- o ------------------+

Định lý Co cụm của Edmonds (Blossom Contraction Theorem)

Cho $G$ là đồ thị và $B$ là một bông hoa đối với tập ghép $M$ . Gọi $G / B$ là đồ thị thu được sau khi co cụm toàn bộ bông hoa $B$ thành một siêu đỉnh duy nhất $v_B$ . Khi đó:

$G \text{ chứa một đường tăng luồng đối với } M \iff G / B \text{ chứa một đường tăng luồng đối với } M / B$

Ý nghĩa: Khi phát hiện một bông hoa $B$ , ta có thể an tâm gộp tất cả các đỉnh của $B$ thành một đỉnh đại diện. Nếu tìm thấy đường tăng luồng chạy qua siêu đỉnh $v_B$ , ta luôn có thể "mở rộng" (unfold) đường đi này qua một trong hai nhánh của chu trình $B$ để thu được một đường tăng luồng thực sự trên đồ thị gốc $G$ .

3. Thuật toán Edmonds: Rừng BFS và Co cụm bằng DSU

Thuật toán lặp lại việc tìm đường tăng luồng từ các đỉnh tự do cho đến khi không còn tìm được nữa:

Phân loại đỉnh trong BFS

Cây BFS xen kẽ gán nhãn cho các đỉnh:

Gốc (Root): Đỉnh tự do ban đầu, là đỉnh loại Chẵn (Type 0).
Đỉnh loại Chẵn (Even): Nằm cách gốc số chẵn cạnh trên cây BFS.
Đỉnh loại Lẻ (Odd): Nằm cách gốc số lẻ cạnh trên cây BFS.

Xử lý các cạnh $(u, v)$ trong quá trình duyệt BFS

Duyệt qua một cạnh $(u, v)$ xuất phát từ một đỉnh Chẵn $u$ :

Nếu $v$ chưa được thăm:
- $v$ chắc chắn đã được ghép với một đỉnh $w = \text{match}[v]$ (nếu $v$ tự do thì đã tìm thấy đường tăng luồng $r \to \dots \to u \to v$ ).
- Đánh dấu $v$ là đỉnh loại Lẻ, đánh dấu $w$ là đỉnh loại Chẵn.
- Đặt cha của $v$ là $u$ , cha của $w$ là $v$ , và đẩy $w$ vào hàng đợi BFS để tiếp tục mở rộng.
Nếu $v$ là đỉnh loại Lẻ: Bỏ qua (không tạo ra thông tin mới).
Nếu $v$ là đỉnh loại Chẵn và thuộc cùng cây BFS:
- Phát hiện một Blossom! Chu trình tạo bởi đường đi từ $u$ và $v$ ngược về tổ tiên chung gần nhất (LCA) của chúng có độ dài lẻ.
- Tìm đỉnh gốc của bông hoa: $\text{base} = \text{LCA}(u, v)$ trong cây BFS.
- Co cụm (Contract): Dùng cấu trúc Disjoint Set Union (DSU) gộp tất cả các đỉnh trên chu trình về $\text{base}$ . Đổi tất cả các đỉnh loại Lẻ trên chu trình thành loại Chẵn và đẩy chúng vào hàng đợi BFS (vì giờ đây chúng có thể mở rộng đường đi theo chiều ngược lại của chu trình).
Nếu $v$ là đỉnh loại Chẵn nhưng thuộc một cây BFS khác:
- Hai cây BFS xuất phát từ hai đỉnh tự do khác nhau đã chạm nhau $\implies$ Tìm thấy đường tăng luồng!
- Lần vết đường đi và đảo ngược các cạnh ghép (Augment).

4. Hiện thực hóa Thuật toán Blossom bằng Golang

Đoạn mã dưới đây cài đặt hoàn chỉnh Thuật toán Blossom của Edmonds với độ phức tạp $O(V^3)$ sử dụng DSU và hàng đợi BFS:

package main

import (
	"fmt"
)

type BlossomMatcher struct {
	n       int
	adj     [][]int
	match   []int // match[u] = v nghĩa là u ghép với v (-1 nếu tự do)
	parent  []int // Mảng vết trên cây BFS
	base    []int // DSU: Đại diện của blossom chứa u
	q       []int
	inQueue []bool
	status  []int // -1: chưa thăm, 0: Chẵn (Even), 1: Lẻ (Odd)
}

func NewBlossomMatcher(n int) *BlossomMatcher {
	return &BlossomMatcher{
		n:      n,
		adj:    make([][]int, n),
		match:  make([]int, n),
		parent: make([]int, n),
		base:   make([]int, n),
		status: make([]int, n),
	}
}

func (bm *BlossomMatcher) AddEdge(u, v int) {
	bm.adj[u] = append(bm.adj[u], v)
	bm.adj[v] = append(bm.adj[v], u)
}

// DSU find: Tìm đỉnh đại diện (Base của Blossom)
func (bm *BlossomMatcher) findBase(u int) int {
	if bm.base[u] == u {
		return u
	}
	bm.base[u] = bm.findBase(bm.base[u])
	return bm.base[u]
}

// Tìm tổ tiên chung gần nhất (LCA) của hai đỉnh Chẵn trong cây BFS
func (bm *BlossomMatcher) getLCA(root, u, v int) int {
	visited := make([]bool, bm.n)
	for {
		u = bm.findBase(u)
		visited[u] = true
		if u == root {
			break
		}
		u = bm.parent[bm.match[u]]
	}

	for {
		v = bm.findBase(v)
		if visited[v] {
			return v
		}
		v = bm.parent[bm.match[v]]
	}
}

// Co cụm một nhánh của Blossom từ u lên lca
func (bm *BlossomMatcher) contractPath(u, v, lca int) {
	for bm.findBase(u) != lca {
		bm.parent[u] = v
		v = bm.match[u]

		// Nếu v là nút Lẻ, biến nó thành Chẵn và đẩy vào Queue để tiếp tục tìm kiếm
		if bm.status[v] == 1 {
			bm.status[v] = 0
			bm.q = append(bm.q, v)
		}

		// Gộp base của u và v vào lca
		if bm.base[u] == u {
			bm.base[u] = lca
		}
		if bm.base[v] == v {
			bm.base[v] = lca
		}

		u = bm.parent[v]
	}
}

// Co cụm toàn bộ Blossom tạo bởi cạnh (u, v) với gốc lca
func (bm *BlossomMatcher) contractBlossom(u, v, lca int) {
	bm.contractPath(u, v, lca)
	bm.contractPath(v, u, lca)
}

// BFS tìm đường tăng luồng xuất phát từ đỉnh tự do root
func (bm *BlossomMatcher) findAugmentingPath(root int) int {
	for i := 0; i < bm.n; i++ {
		bm.status[i] = -1
		bm.parent[i] = -1
		bm.base[i] = i
	}

	bm.q = []int{root}
	bm.status[root] = 0 // Đỉnh gốc là loại Chẵn

	for len(bm.q) > 0 {
		u := bm.q[0]
		bm.q = bm.q[1:]

		for _, v := range bm.adj[u] {
			// Bỏ qua nếu hai đỉnh cùng thuộc một Blossom đã co cụm
			if bm.findBase(u) == bm.findBase(v) {
				continue
			}

			// Nếu v chưa được thăm trong lượt BFS này
			if bm.status[v] == -1 {
				if bm.match[v] == -1 {
					// v là đỉnh tự do -> Tìm thấy đường tăng luồng!
					bm.parent[v] = u
					return v
				}

				// v đã được ghép: gán v là Lẻ, match[v] là Chẵn
				bm.parent[v] = u
				bm.status[v] = 1
				matchedNode := bm.match[v]
				bm.status[matchedNode] = 0
				bm.q = append(bm.q, matchedNode)

			} else if bm.status[bm.findBase(v)] == 0 {
				// Cả u và v đều là loại Chẵn -> Phát hiện Blossom!
				lca := bm.getLCA(root, u, v)
				bm.contractBlossom(u, v, lca)
			}
		}
	}

	return -1
}

// Đảo ngược các cạnh trên đường tăng luồng kết thúc tại endpoint
func (bm *BlossomMatcher) augment(endpoint int) {
	curr := endpoint
	for curr != -1 {
		p := bm.parent[curr]
		next := -1
		if p != -1 {
			next = bm.match[p]
		}
		bm.match[curr] = p
		if p != -1 {
			bm.match[p] = curr
		}
		curr = next
	}
}

// Thuật toán Blossom giải quyết Maximum General Matching: O(V^3)
func (bm *BlossomMatcher) MaxMatch() int {
	for i := 0; i < bm.n; i++ {
		bm.match[i] = -1
	}

	matchingSize := 0

	for i := 0; i < bm.n; i++ {
		if bm.match[i] == -1 {
			endpoint := bm.findAugmentingPath(i)
			if endpoint != -1 {
				bm.augment(endpoint)
				matchingSize++
			}
		}
	}

	return matchingSize
}

func main() {
	// Khởi tạo đồ thị gồm 5 đỉnh chứa chu trình lẻ:
	// Chu trình C5: (0-1-2-3-4-0)
	// Thêm cạnh phụ (0-5) nếu có, ở đây xét đồ thị 5 đỉnh:
	// Chu trình lẻ C5 không thể có ghép cặp hoàn hảo (tối đa chỉ ghép được 2 cặp)
	n := 6
	matcher := NewBlossomMatcher(n)

	// Xây dựng đồ thị chứa chu trình lẻ 3 đỉnh (0, 1, 2) và các đỉnh rẽ nhánh:
	// 0 nối 1, 1 nối 2, 2 nối 0 (Tam giác C3)
	// 0 nối 3, 1 nối 4, 2 nối 5
	matcher.AddEdge(0, 1)
	matcher.AddEdge(1, 2)
	matcher.AddEdge(2, 0)
	matcher.AddEdge(0, 3)
	matcher.AddEdge(1, 4)
	matcher.AddEdge(2, 5)

	maxPairs := matcher.MaxMatch()
	fmt.Printf("Số lượng cặp ghép cực đại: %d cặp\n", maxPairs)
	fmt.Println("Chi tiết các cặp ghép:")
	for i := 0; i < n; i++ {
		if i < matcher.match[i] {
			fmt.Printf("Đỉnh %d <===> Đỉnh %d\n", i, matcher.match[i])
		}
	}
}

5. Phân tích độ phức tạp

Biến thể thuật toán	Độ phức tạp thời gian	Chi phí bộ nhớ	Ghi chú
Edmonds' Blossom (Cài đặt trên)	$O(V^3)$	$O(V + E)$	Mỗi lần tăng luồng duyệt $O(V)$ đỉnh, BFS mất $O(V^2)$ do co cụm
Edmonds' Blossom (Tối ưu DSU)	$O(V \cdot E)$	$O(V + E)$	Sử dụng DSU nén đường đi cho mọi thao tác co cụm
Micali-Vazirani Algorithm (1980)	$O(E \sqrt{V})$	$O(V + E)$	Tìm đồng thời nhiều đường tăng luồng ngắn nhất (tương tự Hopcroft-Karp)
Blossom V (Vladimir Kolmogorov)	Thực nghiệm $O(E)$	$O(V + E)$	Thư viện chuẩn mực giải Maximum Weight General Matching trong thực tế

Số bước tăng luồng: Kích thước tập ghép cực đại không vượt quá $V / 2$ , do đó có tối đa $O(V)$ lượt tăng luồng thành công.
Mỗi lượt BFS: Mỗi cạnh được duyệt tối đa một số lần hằng số; mỗi thao tác tìm LCA và co cụm blossom duyệt qua không quá $O(V)$ đỉnh. Tổng thời gian cho một lượt BFS là $O(V^2)$ (hoặc $O(E)$ nếu tối ưu chặt chẽ).

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

Bài toán ghép cặp bạn cùng phòng (Stable Roommates with Incomplete Lists): Ghép đôi sinh viên vào các phòng ký túc xá 2 người dựa trên sự tương thích mà không có sự phân chia giới tính/vai trò cố định.
Lập lịch phân công kíp tuần tra (Police / Rescue Patrol Pairing): Ghép các nhân sự cứu hộ hoặc cảnh sát thành từng đội 2 người dựa trên kỹ năng bổ trợ lẫn nhau, đảm bảo số lượng đội hình xuất phát cùng lúc là lớn nhất.
Xử lý hình ảnh & Thị giác máy tính (Feature Point Matching): Ghép nối các điểm đặc trưng hình ảnh trong tái tạo không gian 3D (Structure from Motion) khi các liên kết đối sánh có thể tạo thành các chu trình không phân hai phía.
Tối ưu hóa hóa học lượng tử & Phân tử hữu cơ: Tìm cấu trúc cộng hưởng hóa trị cực đại (Kekulé structures) trên các phân tử hydrocacbon thơm dạng lưới lục giác/ngũ giác phức tạp.

cấu trúc dữ liệu