Cấu trúc dữ liệu và Giải thuật Bài 138: Cây Gomory-Hu (Gomory-Hu Cut Tree) - Cấu trúc dữ liệu đại diện cho tất cả các lát cắt s-t cực tiểu trên đồ thị vô hướng.

Cho một đồ thị vô hướng có trọng số $G = (V, E)$ gồm $N = \vert{}V\vert{}$ đỉnh. Giữa hai đỉnh bất kỳ $u$ và $v$ , ta có một giá trị lát cắt cực tiểu $\lambda(u, v)$ (cũng chính là giá trị luồng cực đại giữa $u$ và $v$ theo định lý Max-Flow Min-Cut). Vì có tất cả $\binom{N}{2} = \frac{N(N-1)}{2}$ cặp đỉnh, cách tiếp cận ngây thơ để tìm lát cắt cực tiểu cho mọi cặp đòi hỏi phải chạy thuật toán Max-Flow (như Dinic) $\Theta(N^2)$ lần, dẫn đến độ phức tạp khổng lồ $O(N^4 E)$ .

Năm 1961, Ralph E. Gomory và T. C. Hu đã công bố một kết quả tổ hợp kinh điển: Toàn bộ $\binom{N}{2}$ giá trị lát cắt cực tiểu này có thể được nén trọn vẹn vào một cây có trọng số duy nhất $T = (V, E_T)$ chỉ gồm đúng $N - 1$ cạnh. Cấu trúc này được gọi là Cây Gomory-Hu (Gomory-Hu Cut Tree). Hơn thế nữa, cây này có thể được xây dựng bằng cách chỉ gọi thuật toán Max-Flow đúng $N - 1$ lần.

1. Bản chất toán học và Hai tính chất cốt tử của Cây Gomory-Hu

Một cây có trọng số $T = (V, E_T)$ được gọi là Cây Gomory-Hu của đồ thị vô hướng $G = (V, E)$ nếu nó có cùng tập đỉnh $V$ với $G$ và thỏa mãn đồng thời hai tính chất sau:

Tính chất 1: Bảo toàn giá trị Lát cắt cực tiểu (Flow Equivalence)

Với mọi cặp đỉnh $u, v \in V$ , giá trị lát cắt $u-v$ cực tiểu trong đồ thị ban đầu $G$ đúng bằng trọng số của cạnh nhỏ nhất trên đường đi duy nhất giữa $u$ và $v$ trên cây $T$ :

$\lambda_G(u, v) = \min_{e \in \text{path}_T(u, v)} w_T(e)$

Tính chất 2: Bảo toàn tập phân hoạch Lát cắt (Cut Preservation)

Với bất kỳ cạnh nào $e = (p, q) \in E_T$ trên cây $T$ :

Khi ta cắt bỏ cạnh $e$ , cây $T$ bị chia cắt thành đúng hai thành phần liên thông với tập đỉnh tương ứng là $S_e$ và $V \setminus S_e$ .
Tập cắt $(S_e, V \setminus S_e)$ này chính là một lát cắt cực tiểu thực sự giữa $p$ và $q$ trên đồ thị gốc $G$ , và dung lượng của lát cắt đó trên $G$ đúng bằng $w_T(e)$ :

$c_G(S_e, V \setminus S_e) = w_T(e) = \lambda_G(p, q)$

Phân biệt Cây Gomory-Hu và Cây luồng tương đương (Equivalent Flow Tree):

Equivalent Flow Tree: Chỉ cần thỏa mãn Tính chất 1 (cho phép truy vấn đúng giá trị lát cắt cực tiểu của mọi cặp).

Gomory-Hu Cut Tree: Thỏa mãn cả Tính chất 1 và Tính chất 2 (vừa cho giá trị, vừa cho biết chính xác các tập đỉnh bị chia cắt bởi lát cắt đó).

          Đồ thị gốc G (Chứa O(N^2) lát cắt)
                     (0) --- 10 --- (1)
                      | \          / |
                      2   1      3   2
                      |     \  /     |
                     (2) --- 8 ---- (3)
                            
                            ||
             [Nén thành Gomory-Hu Tree T]
                            ||
                            v
                     (0) --- 13 --- (1)
                      |              |
                      10             9
                      |              |
                     (2)            (3)

2. Thuật toán Gusfield: Xây dựng Gomory-Hu Tree không cần co cụm (Contraction-Free)

Thuật toán Gomory-Hu nguyên bản (1961) sử dụng chiến lược chia để trị và thực hiện co cụm (contraction) các thành phần liên thông thành các siêu đỉnh ở mỗi bước. Thao tác co cụm này tương đối phức tạp khi cài đặt thực tế.

Năm 1990, Dan Gusfield đề xuất một thuật toán cải tiến mang tính đột phá: Xây dựng cây mà không cần co cụm bất kỳ đỉnh nào của đồ thị. Thuật toán luôn chạy trực tiếp trên đồ thị gốc $G$ , duy trì một mảng con trỏ cha parent biểu diễn cấu trúc cây hình sao khởi tạo, và cập nhật dần qua $N - 1$ pha.

Các bước của Thuật toán Gusfield:

Khởi tạo:
- Chọn một đỉnh làm gốc quy ước (thường là đỉnh $0$ ).
- Khởi tạo mảng cha: $\text{parent}[i] = 0$ với mọi $i \in \{1, 2, \dots, N-1\}$ .
- Cấu trúc cây ban đầu là một hình sao với tâm tại đỉnh $0$ .
Lặp qua từng đỉnh $s = 1, 2, \dots, N - 1$ :
- Đặt $t = \text{parent}[s]$ .
- Chạy thuật toán Max-Flow giữa hai nguồn - đích $s$ và $t$ trên đồ thị gốc $G$ .
- Gọi $C$ là giá trị luồng cực đại tìm được ( $\lambda(s, t) = C$ ). Gán trọng số cạnh giữa $s$ và $t$ trên cây là $w(s, t) = C$ .
- Sau khi luồng đạt cực đại, tìm tập lát cắt $S \subset V$ gồm các đỉnh có thể tiếp cận được từ $s$ trên đồ thị thặng dư (Residual Graph). Khi đó $s \in S$ và $t \notin S$ .
- Cập nhật lại liên kết cây: Duyệt qua tất cả các đỉnh $j \in \{s + 1, \dots, N - 1\}$ :
  - Nếu $j \in S$ và $\text{parent}[j] == t$ , ta đổi con trỏ:
    
    $\text{parent}[j] \gets s$
Kết thúc: Sau $N - 1$ bước, tập các cạnh $(i, \text{parent}[i])$ cùng trọng số $w(i, \text{parent}[i])$ tạo thành một cây đại diện hoàn chỉnh.

3. Truy vấn Lát cắt $u-v$ Min-Cut bằng Binary Lifting trong $O(\log N)$

Sau khi cây Gomory-Hu được xây dựng, việc tìm lát cắt cực tiểu giữa hai đỉnh bất kỳ $u$ và $v$ quy về bài toán: Tìm cạnh có trọng số nhỏ nhất trên đường đi giữa $u$ và $v$ trên cây.

Ta áp dụng kỹ thuật Nhảy nhị phân (Binary Lifting):

up[u][k]: Tổ tiên thứ $2^k$ của đỉnh $u$ .
minEdge[u][k]: Trọng số cạnh nhỏ nhất trên đường đi từ $u$ lên tổ tiên thứ $2^k$ .

Bảng thưa được xây dựng trong $O(N \log N)$ , cho phép trả lời mỗi truy vấn $\lambda(u, v)$ trong thời gian $O(\log N)$ (hoặc $O(1)$ nếu kết hợp với Euler Tour + RMQ Sparse Table).

4. Hiện thực hóa Gomory-Hu Tree bằng Golang

Chương trình dưới đây cài đặt hoàn chỉnh:

Thuật toán Dinic Max-Flow trên đồ thị thặng dư để tìm $s-t$ Min-Cut và trích xuất tập đỉnh reachable.
Thuật toán Gusfield để xây dựng cây Gomory-Hu qua $N - 1$ lần chạy Dinic.
Kỹ thuật Binary Lifting để hỗ trợ truy vấn lát cắt cực tiểu giữa hai đỉnh bất kỳ trong $O(\log N)$ .

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4
const MAXLOG = 20

// Cấu trúc cạnh của đồ thị thặng dư
type Edge struct {
	to   int
	rev  int
	cap  int64
	flow int64
}

type Dinic struct {
	n     int
	adj   [][]Edge
	level []int
	ptr   []int
}

func NewDinic(n int) *Dinic {
	return &Dinic{
		n:     n,
		adj:   make([][]Edge, n),
		level: make([]int, n),
		ptr:   make([]int, n),
	}
}

// Thêm cạnh vô hướng với dung lượng c
func (d *Dinic) AddUndirectedEdge(u, v int, c int64) {
	d.adj[u] = append(d.adj[u], Edge{to: v, rev: len(d.adj[v]), cap: c, flow: 0})
	d.adj[v] = append(d.adj[v], Edge{to: u, rev: len(d.adj[u]) - 1, cap: c, flow: 0})
}

func (d *Dinic) bfs(s, t int) bool {
	for i := 0; i < d.n; i++ {
		d.level[i] = -1
	}
	d.level[s] = 0
	queue := []int{s}

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for _, e := range d.adj[u] {
			if e.cap-e.flow > 0 && d.level[e.to] == -1 {
				d.level[e.to] = d.level[u] + 1
				queue = append(queue, e.to)
			}
		}
	}
	return d.level[t] != -1
}

func (d *Dinic) dfs(u, t int, pushed int64) int64 {
	if pushed == 0 || u == t {
		return pushed
	}

	for ; d.ptr[u] < len(d.adj[u]); d.ptr[u]++ {
		e := &d.adj[u][d.ptr[u]]
		tr := e.to

		if d.level[u]+1 != d.level[tr] || e.cap-e.flow == 0 {
			continue
		}

		pushVal := pushed
		if e.cap-e.flow < pushVal {
			pushVal = e.cap - e.flow
		}

		trPushed := d.dfs(tr, t, pushVal)
		if trPushed == 0 {
			continue
		}

		e.flow += trPushed
		d.adj[tr][e.rev].flow -= trPushed
		return trPushed
	}
	return 0
}

func (d *Dinic) MaxFlow(s, t int) int64 {
	var flow int64 = 0
	for d.bfs(s, t) {
		for i := 0; i < d.n; i++ {
			d.ptr[i] = 0
		}
		for {
			pushed := d.dfs(s, t, INF)
			if pushed == 0 {
				break
			}
			flow += pushed
		}
	}
	return flow
}

// Lấy tập hợp các đỉnh thuộc phía nguồn (source side) của lát cắt
func (d *Dinic) GetCutSet(s int) []bool {
	visited := make([]bool, d.n)
	queue := []int{s}
	visited[s] = true

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for _, e := range d.adj[u] {
			if e.cap-e.flow > 0 && !visited[e.to] {
				visited[e.to] = true
				queue = append(queue, e.to)
			}
		}
	}
	return visited
}

// Cấu trúc Gomory-Hu Tree
type TreeEdge struct {
	to     int
	weight int64
}

type GomoryHuTree struct {
	n        int
	rawEdges [][3]int64 // Lưu trữ danh sách cạnh gốc (u, v, w)
	treeAdj  [][]TreeEdge

	depth   []int
	up      [][]int
	minEdge [][]int64
}

func NewGomoryHuTree(n int) *GomoryHuTree {
	return &GomoryHuTree{
		n:       n,
		treeAdj: make([][]TreeEdge, n),
		depth:   make([]int, n),
		up:      make([][]int, n),
		minEdge: make([][]int64, n),
	}
}

func (ght *GomoryHuTree) AddEdge(u, v int, w int64) {
	ght.rawEdges = append(ght.rawEdges, [3]int64{int64(u), int64(v), w})
}

// Thuật toán Gusfield xây dựng Gomory-Hu Tree
func (ght *GomoryHuTree) Build() {
	parent := make([]int, ght.n)
	weight := make([]int64, ght.n)

	for i := 1; i < ght.n; i++ {
		parent[i] = 0
	}

	for s := 1; s < ght.n; s++ {
		t := parent[s]

		// Khởi tạo đồ thị Dinic mới từ các cạnh ban đầu
		dinic := NewDinic(ght.n)
		for _, e := range ght.rawEdges {
			dinic.AddUndirectedEdge(int(e[0]), int(e[1]), e[2])
		}

		cutCap := dinic.MaxFlow(s, t)
		weight[s] = cutCap
		cutSet := dinic.GetCutSet(s)

		for j := s + 1; j < ght.n; j++ {
			if cutSet[j] && parent[j] == t {
				parent[j] = s
			}
		}
	}

	// Dựng cây từ mảng parent và weight
	for i := 1; i < ght.n; i++ {
		p := parent[i]
		w := weight[i]
		ght.treeAdj[i] = append(ght.treeAdj[i], TreeEdge{to: p, weight: w})
		ght.treeAdj[p] = append(ght.treeAdj[p], TreeEdge{to: i, weight: w})
	}

	// Tiền xử lý Binary Lifting
	for i := 0; i < ght.n; i++ {
		ght.up[i] = make([]int, MAXLOG)
		ght.minEdge[i] = make([]int64, MAXLOG)
	}
	ght.dfsTree(0, 0, 0, INF)
}

func (ght *GomoryHuTree) dfsTree(u, p, d int, costToParent int64) {
	ght.depth[u] = d
	ght.up[u][0] = p
	ght.minEdge[u][0] = costToParent

	for k := 1; k < MAXLOG; k++ {
		anc := ght.up[u][k-1]
		ght.up[u][k] = ght.up[anc][k-1]
		ght.minEdge[u][k] = min(ght.minEdge[u][k-1], ght.minEdge[anc][k-1])
	}

	for _, edge := range ght.treeAdj[u] {
		if edge.to != p {
			ght.dfsTree(edge.to, u, d+1, edge.weight)
		}
	}
}

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

// Truy vấn lát cắt cực tiểu giữa u và v trong O(log N)
func (ght *GomoryHuTree) QueryMinCut(u, v int) int64 {
	if u == v {
		return 0
	}
	var res int64 = INF
	if ght.depth[u] < ght.depth[v] {
		u, v = v, u
	}

	// Nhảy u lên cùng độ sâu với v
	diff := ght.depth[u] - ght.depth[v]
	for k := 0; k < MAXLOG; k++ {
		if (diff & (1 << k)) != 0 {
			res = min(res, ght.minEdge[u][k])
			u = ght.up[u][k]
		}
	}

	if u == v {
		return res
	}

	// Nhảy đồng thời u và v lên dưới LCA
	for k := MAXLOG - 1; k >= 0; k-- {
		if ght.up[u][k] != ght.up[v][k] {
			res = min(res, ght.minEdge[u][k])
			res = min(res, ght.minEdge[v][k])
			u = ght.up[u][k]
			v = ght.up[v][k]
		}
	}

	res = min(res, ght.minEdge[u][0])
	res = min(res, ght.minEdge[v][0])
	return res
}

func main() {
	// Khởi tạo đồ thị gồm 6 đỉnh (0 đến 5)
	n := 6
	ght := NewGomoryHuTree(n)

	// Các cạnh và trọng số:
	ght.AddEdge(0, 1, 1)
	ght.AddEdge(0, 2, 7)
	ght.AddEdge(1, 2, 1)
	ght.AddEdge(1, 3, 3)
	ght.AddEdge(1, 4, 2)
	ght.AddEdge(2, 4, 4)
	ght.AddEdge(3, 4, 1)
	ght.AddEdge(3, 5, 6)
	ght.AddEdge(4, 5, 2)

	// 1. Xây dựng cây Gomory-Hu
	ght.Build()

	fmt.Println("Cây Gomory-Hu đã được xây dựng thành công!")
	fmt.Println("Các cạnh của cây Gomory-Hu:")
	for u := 0; u < n; u++ {
		for _, e := range ght.treeAdj[u] {
			if u < e.to {
				fmt.Printf("Cạnh (%d <---> %d) với trọng số (Cut Capacity): %d\n", u, e.to, e.weight)
			}
		}
	}

	// 2. Kiểm tra truy vấn lát cắt cực tiểu giữa các cặp đỉnh
	testPairs := [][2]int{
		{0, 5},
		{2, 3},
		{0, 2},
		{3, 5},
	}

	fmt.Println("\nKết quả truy vấn Lát cắt cực tiểu (Max-Flow):")
	for _, pair := range testPairs {
		u, v := pair[0], pair[1]
		cutVal := ght.QueryMinCut(u, v)
		fmt.Printf("- Min-Cut giữa đỉnh %d và đỉnh %d = %d\n", u, v, cutVal)
	}
}

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

Thao tác	Thuật toán	Độ phức tạp thời gian	Chi phí bộ nhớ
Xây dựng Cây (Gusfield)	$(N - 1)$ lần chạy Dinic Max-Flow	$O(V \cdot V^2 E) = O(V^3 E)$	$O(V + E)$
Tiền xử lý RMQ	Binary Lifting trên cây	$O(V \log V)$	$O(V \log V)$
Truy vấn $\lambda(u, v)$	Nhảy nhị phân tìm $\min$ cạnh	$O(\log V)$ (hoặc $O(1)$ với RMQ)	$O(1)$
So sánh với cách ngây thơ	$\binom{V}{2}$ lần chạy Dinic	$O(V^4 E)$	$O(V + E)$

Độ tăng tốc: Giảm số lần chạy thuật toán mạng luồng từ $\Theta(V^2)$ xuống đúng $V - 1$ lần (giảm một bậc $V$ về độ phức tạp). Với đồ thị gồm $1.000$ đỉnh, số lần tính luồng giảm từ xấp xỉ $500.000$ lần xuống chỉ còn $999$ lần.

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

Phân tích Băng thông Cổ chai Mạng diện rộng (WAN Bottleneck Analysis): Trong mạng viễn thông phân tán, cây Gomory-Hu cho phép người quản trị xác định ngay lập tức băng thông truyền tải tối đa giữa bất kỳ hai trung tâm dữ liệu nào mà không cần mô phỏng lại luồng mạng từ đầu.
Thuật toán Phân cụm Phân cấp (Hierarchical Clustering via Min-Cut): Cắt bỏ dần các cạnh có trọng số nhỏ nhất trên cây Gomory-Hu sẽ phân chia đồ thị thành các cụm (clusters) có độ kết nối nội bộ cao nhất, tương tự như thuật toán Single-linkage clustering nhưng tối ưu hóa theo độ bền lát cắt.
Tối ưu hóa Độ tin cậy và Khả năng chịu lỗi Đa điểm: Định vị các cạnh có trọng số nhỏ nhất trên cây Gomory-Hu giúp chỉ ra các liên kết hạ tầng quan trọng nhất mà nếu bị quá tải hoặc đứt gãy sẽ gây sụt giảm khả năng kết nối của nhiều cặp đỉnh nhất trong toàn hệ thống.

cấu trúc dữ liệu