Cấu trúc dữ liệu và Giải thuật Bài 87: Luồng cực đại trong Mạng lưới (Max Flow / Min Cut) với thuật toán Ford-Fulkerson.

Khi vận hành hệ thống thu phí tự động (AFC) của tuyến Metro, dữ liệu giao dịch từ hàng chục nhà ga (Nguồn - Source) cần được đồng bộ liên tục về máy chủ trung tâm (Đích - Sink). Tuy nhiên, mạng lưới cáp quang kết nối giữa các trạm trung chuyển không đồng đều; mỗi đoạn cáp chỉ chịu tải được một băng thông tối đa nhất định (Capacity).

Bài toán đặt ra: Làm sao để bơm một lượng dữ liệu lớn nhất (Max Flow) qua mạng lưới này trong một đơn vị thời gian mà không làm tắc nghẽn bất kỳ đoạn cáp nào?

Đây là bài toán Luồng cực đại trong mạng lưới (Maximum Flow). Giải pháp nền tảng cho lớp bài toán này là thuật toán Ford-Fulkerson, dựa trên một cơ chế vô cùng thông minh: Liên tục tìm đường đi và "rút lại" quyết định sai lầm.

1. Mô hình Toán học của Mạng nén luồng

Một mạng lưới luồng (Flow Network) là một đồ thị có hướng, trong đó:

Mỗi cạnh $(u, v)$ có một Sức chứa (Capacity - $C$ ), biểu diễn giới hạn tối đa có thể truyền qua.
Mỗi cạnh có một Luồng hiện tại (Flow - $F$ ), luôn thỏa mãn $0 \le F \le C$ .
Định luật bảo toàn luồng: Ngoại trừ đỉnh Nguồn ( $S$ ) và đỉnh Đích ( $T$ ), tổng lượng luồng đi vào một đỉnh bất kỳ luôn phải bằng tổng lượng luồng đi ra khỏi đỉnh đó ( $\sum F_{in} = \sum F_{out}$ ).

2. Thuật toán Ford-Fulkerson và Đồ thị Thặng dư (Residual Graph)

Chiến thuật ngây thơ nhất là cứ dùng BFS/DFS tìm bừa một đường từ $S$ đến $T$ , xem đoạn cáp nào có băng thông nhỏ nhất (Nút thắt cổ chai - Bottleneck), rồi bơm luồng bằng đúng giá trị đó. Lặp lại đến khi không còn đường đi.

Tuy nhiên, nếu chọn sai đường ở những bước đầu, luồng dữ liệu có thể chặn mất các con đường tối ưu hơn sau đó, dẫn đến một kết quả chưa phải là cực đại.

Thuật toán Ford-Fulkerson giải quyết sự "ngây thơ" này bằng cách tạo ra một Đồ thị Thặng dư (Residual Graph).

Bất cứ khi nào bạn bơm $X$ đơn vị luồng qua cạnh $(u, v)$ , thuật toán lập tức tạo ra một cạnh ngược chiều $(v, u)$ với sức chứa đúng bằng $X$ . Cạnh ngược này đóng vai trò như một "nút Undo" (Hoàn tác).

Các bước thực thi:

Khởi tạo: Luồng ban đầu $F = 0$ trên tất cả các cạnh.
Đường tăng luồng (Augmenting Path): Tìm một đường đi từ $S$ đến $T$ trên Đồ thị thặng dư sao cho sức chứa của mọi cạnh trên đường đó đều $> 0$ .
Bơm luồng: Tìm sức chứa nhỏ nhất $M$ trên đường đi vừa tìm được (Bottleneck).
Cập nhật thặng dư:
- Cộng $M$ vào luồng thuận.
- Trừ $M$ khỏi sức chứa ngược (cho phép thuật toán sau này có thể "đẩy ngược" dòng chảy lại nếu tìm được đường tốt hơn).
Lặp lại bước 2 cho đến khi không thể tìm thêm bất kỳ đường tăng luồng nào từ $S$ đến $T$ .

3. Định lý Luồng Cực Đại - Lát Cắt Cực Tiểu (Max-Flow Min-Cut Theorem)

Có một sự thật toán học tuyệt đẹp phía sau thuật toán này: Khi Ford-Fulkerson dừng lại (không tìm được đường đi nữa), giá trị Luồng cực đại vừa tìm được chính xác bằng giá trị của Lát cắt cực tiểu (Minimum Cut).

Lát cắt cực tiểu là cách bạn cắt đứt một vài đoạn cáp sao cho $S$ và $T$ bị ngắt kết nối hoàn toàn, với tổng băng thông của các đoạn cáp bị cắt là nhỏ nhất. Mạng lưới truyền tải của bạn mạnh đến đâu phụ thuộc hoàn toàn vào "nút thắt" yếu nhất này.

4. Triển khai thuật toán bằng Golang

Thuật toán Ford-Fulkerson cơ bản dùng DFS để tìm đường có thể chạy khá chậm. Trong kỹ thuật phần mềm thực tế, chúng ta sử dụng Thuật toán Edmonds-Karp, bản chất chính là Ford-Fulkerson nhưng sử dụng BFS (Tìm kiếm theo chiều rộng) để tìm đường đi ngắn nhất (ít số cạnh nhất) trên đồ thị thặng dư.

package main

import (
	"fmt"
	"math"
)

// Hàm BFS tìm đường tăng luồng trên Đồ thị thặng dư
// Trả về true nếu tìm được đường từ S đến T
func bfs(rGraph [][]int, s, t, V int, parent []int) bool {
	visited := make([]bool, V)
	queue := []int{s}
	visited[s] = true
	parent[s] = -1

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

		for v := 0; v < V; v++ {
			// Nếu chưa thăm v VÀ sức chứa thặng dư > 0
			if !visited[v] && rGraph[u][v] > 0 {
				if v == t {
					parent[v] = u
					return true // Đã chạm đến đích
				}
				queue = append(queue, v)
				parent[v] = u
				visited[v] = true
			}
		}
	}
	return false
}

// Thuật toán Edmonds-Karp (Biến thể tối ưu của Ford-Fulkerson)
func EdmondsKarp(graph [][]int, s, t, V int) int {
	// Khởi tạo đồ thị thặng dư rGraph hệt như đồ thị gốc
	rGraph := make([][]int, V)
	for i := 0; i < V; i++ {
		rGraph[i] = make([]int, V)
		copy(rGraph[i], graph[i])
	}

	parent := make([]int, V)
	maxFlow := 0

	// Lặp lại việc tìm đường tăng luồng bằng BFS
	for bfs(rGraph, s, t, V, parent) {
		// 1. Tìm nút thắt cổ chai (bottleneck) trên đường đi vừa tìm được
		pathFlow := math.MaxInt32
		for v := t; v != s; v = parent[v] {
			u := parent[v]
			if rGraph[u][v] < pathFlow {
				pathFlow = rGraph[u][v]
			}
		}

		// 2. Cập nhật sức chứa thặng dư cho cả cạnh thuận và cạnh ngược
		for v := t; v != s; v = parent[v] {
			u := parent[v]
			rGraph[u][v] -= pathFlow // Trừ sức chứa chiều thuận
			rGraph[v][u] += pathFlow // Tăng sức chứa chiều ngược (cho phép Undo)
		}

		// Cộng dồn vào luồng cực đại
		maxFlow += pathFlow
	}

	return maxFlow
}

func main() {
	// Giả lập mạng lưới gồm 6 đỉnh (0 = Nguồn, 5 = Đích)
	// Ma trận kề lưu trữ băng thông tối đa (Capacity)
	V := 6
	graph := [][]int{
		{0, 16, 13, 0, 0, 0},
		{0, 0, 10, 12, 0, 0},
		{0, 4, 0, 0, 14, 0},
		{0, 0, 9, 0, 0, 20},
		{0, 0, 0, 7, 0, 4},
		{0, 0, 0, 0, 0, 0},
	}

	source := 0
	sink := 5

	fmt.Printf("Luồng cực đại của hệ thống là: %d\n", EdmondsKarp(graph, source, sink, V))
	// Mong đợi: 23
}

5. Phân tích Hiệu năng (Big-O)

Thời gian thực thi (Ford-Fulkerson cơ bản bằng DFS): $O(E \cdot F^*)$ với $E$ là số cạnh và $F^*$ là luồng cực đại. Nếu $F^*$ rất lớn (băng thông hàng tỷ byte), DFS sẽ nhích từng bước một và cực kỳ chậm.
Thời gian thực thi (Edmonds-Karp bằng BFS): $O(V \cdot E^2)$ . Số lần tìm đường tăng luồng được đảm bảo không bao giờ vượt quá $V \cdot E / 2$ , bất chấp băng thông lớn đến đâu, giúp hệ thống ổn định tuyệt đối trong môi trường Enterprise.
Không gian (Space): $O(V^2)$ để duy trì ma trận kề cho đồ thị thặng dư. Nếu đồ thị thưa (ít cạnh), có thể tối ưu bộ nhớ xuống $O(V + E)$ bằng danh sách kề (Adjacency List).

Với kiến trúc giải quyết bài toán Max Flow vững chắc này, chúng ta có thể mở rộng để xử lý việc phân công công việc tối ưu giữa hệ thống máy chủ và các tác vụ (Job Assignments) — một bài toán đặc thù mang tên Đối sánh đồ thị hai phía (Bipartite Matching).

cấu trúc dữ liệu