Cấu trúc dữ liệu và Giải thuật Bài 90: Chu trình Euler và Đường đi Hamilton - Bài toán Người đưa thư qua lăng kính Đồ thị hiện đại.

Lĩnh vực Logistics và Giao nhận tại Hasaki thường xuyên phải đối mặt với các bài toán tối ưu lộ trình. Tùy thuộc vào bản chất của nhiệm vụ, yêu cầu của hệ thống sẽ khác nhau hoàn toàn:

1. Xe dọn rác, xe phun nước rửa đường, hoặc nhân viên kiểm tra cáp quang: Nhiệm vụ của họ là phải đi qua tất cả các con đường (Mỗi đường đi đúng 1 lần) để hoàn thành công việc.

2. Shipper giao hàng (Hasaki): Nhiệm vụ của shipper là phải ghé thăm tất cả các trạm/khách hàng (Mỗi khách hàng ghé đúng 1 lần) để giao kiện hàng, không cần quan tâm đến việc đi hết các con đường trên bản đồ.

Trong Lý thuyết Đồ thị, hai kịch bản này tương ứng với hai khái niệm kinh điển bậc nhất: Chu trình Euler (Eulerian Circuit) và Đường đi Hamilton (Hamiltonian Path). Dù nghe có vẻ giống nhau, nhưng khoảng cách độ phức tạp giữa chúng là khoảng cách giữa một bài toán giải trong nháy mắt và một trong những bài toán thiên niên kỷ không có lời giải hoàn hảo.

1. Chu trình Euler: Vẽ một nét không nhấc bút

Chu trình Euler (Eulerian Circuit) là một đường đi trên đồ thị bắt đầu từ một đỉnh, đi qua mọi cạnh (Edge) đúng một lần duy nhất, và quay trở lại đỉnh xuất phát. Nếu không yêu cầu quay lại đỉnh xuất phát, ta gọi đó là Đường đi Euler (Eulerian Path).

Bài toán này bắt nguồn từ năm 1736 khi Leonhard Euler chứng minh rằng không thể đi qua 7 cây cầu ở Königsberg mà không lặp lại.

Điều kiện tồn tại (Cực kỳ đơn giản):

Một đồ thị vô hướng và liên thông có Chu trình Euler khi và chỉ khi: Tất cả các đỉnh đều có bậc chẵn (Bậc = số lượng cạnh nối vào đỉnh).

Lý do: Cứ mỗi lần bạn đi vào một đỉnh bằng một cạnh, bạn bắt buộc phải có một cạnh khác để đi ra khỏi đỉnh đó. Do đó, các cạnh tại một đỉnh luôn phải đi theo từng cặp (Vào - Ra), nghĩa là tổng số cạnh phải là số chẵn.

Thuật toán Hierholzer ($O(V + E)$):

Để tìm ra chu trình Euler, thuật toán Hierholzer sử dụng DFS kết hợp với Ngăn xếp (Stack):

1. Bắt đầu từ một đỉnh bất kỳ, đi ngẫu nhiên theo các cạnh chưa bị thăm cho đến khi bị "kẹt" (không còn đường ra). Vì mọi đỉnh đều có bậc chẵn, nơi duy nhất bạn có thể bị kẹt chính là đỉnh xuất phát. Quá trình này tạo ra một vòng lặp cơ sở.

2. Quét lại vòng lặp đó. Nếu phát hiện một đỉnh trên vòng lặp vẫn còn cạnh chưa đi, tiếp tục rẽ nhánh đi bừa từ đỉnh đó tạo thành một vòng lặp phụ, rồi gộp vòng lặp phụ vào vòng lặp chính.

3. Lặp lại cho đến khi đi hết cạnh.

2. Đường đi Hamilton: Ác mộng của Khoa học Máy tính

Đường đi Hamilton (Hamiltonian Path) là một đường đi đi qua mọi đỉnh (Vertex) đúng một lần duy nhất. Nếu đường đi này quay lại đỉnh xuất phát, ta gọi là Chu trình Hamilton (Hamiltonian Circuit / Cycle).

Mặc dù phát biểu bài toán cực kỳ giống Euler, nhưng cho đến tận hôm nay, không có bất kỳ dấu hiệu toán học đơn giản nào để kiểm tra nhanh xem một đồ thị có chứa chu trình Hamilton hay không. Tệ hơn nữa, không có thuật toán nào có thể tìm ra đường đi Hamilton trong thời gian đa thức.

Đường đi Hamilton thuộc lớp bài toán NP-Đầy đủ (NP-Complete). Bài toán Người chào hàng (Traveling Salesman Problem - TSP) chính là một dạng mở rộng của Chu trình Hamilton khi có thêm trọng số trên các cạnh.

Để giải bài toán Hamilton, chúng ta buộc phải sử dụng:

• Vét cạn (Backtracking / Quay lui): Thử mọi con đường, độ phức tạp $O(V!)$. Với 20 khách hàng, CPU sẽ tính đến hàng tỷ năm.

• Quy hoạch động kết hợp Bitmask (DP with Bitmask): Ép độ phức tạp xuống $O(2^V \cdot V^2)$, có thể giải được với $V \le 20$. Lớn hơn nữa, hệ thống đành bó tay.

• Thuật toán xấp xỉ (Heuristic/Genetic Algorithm): Chấp nhận một đường đi "đủ tốt" thay vì hoàn hảo nhất để có kết quả trong thời gian thực.

3. Trực quan hóa sự khác biệt giữa Euler và Hamilton

Mô phỏng dưới đây sẽ cho thấy sự khác biệt về bản chất khi thuật toán cố gắng thỏa mãn điều kiện "Đi hết cạnh" so với "Đi hết đỉnh".

4. Triển khai Thuật toán Hierholzer tìm Chu trình Euler bằng Golang

Dưới đây là mã nguồn sử dụng thuật toán Hierholzer để tìm chu trình Euler (hoặc đường đi Euler) trên một đồ thị có hướng. Thuật toán tận dụng Stack để tự động gộp các vòng lặp phụ một cách thanh lịch trong thời gian $O(V + E)$.

Go

package main

import (
	"fmt"
)

// Tìm Chu trình/Đường đi Euler trên đồ thị có hướng bằng thuật toán Hierholzer
func findEulerianPath(n int, edges [][]int) []int {
	// Khởi tạo đồ thị dưới dạng danh sách kề
	graph := make(map[int][]int)
	inDegree := make([]int, n)
	outDegree := make([]int, n)

	for _, edge := range edges {
		u, v := edge[0], edge[1]
		graph[u] = append(graph[u], v)
		outDegree[u]++
		inDegree[v]++
	}

	// 1. Tìm đỉnh bắt đầu
	// Nếu tồn tại 1 đỉnh có (outDegree - inDegree == 1), đó phải là đỉnh bắt đầu.
	// Nếu không, có thể bắt đầu từ bất kỳ đỉnh nào có bậc ra > 0.
	startNode := 0
	for i := 0; i < n; i++ {
		if outDegree[i]-inDegree[i] == 1 {
			startNode = i
			break
		} else if outDegree[i] > 0 {
			startNode = i
		}
	}

	var path []int
	var stack []int
	stack = append(stack, startNode)

	// 2. DFS với Stack (Hierholzer's Algorithm)
	for len(stack) > 0 {
		curr := stack[len(stack)-1]

		// Nếu từ đỉnh hiện tại vẫn còn đường để đi
		if len(graph[curr]) > 0 {
			// Lấy cạnh đầu tiên và xóa nó khỏi đồ thị
			next := graph[curr][0]
			graph[curr] = graph[curr][1:]
			// Đẩy đỉnh tiếp theo vào ngăn xếp
			stack = append(stack, next)
		} else {
			// Bị kẹt (Hết đường ra): Đẩy đỉnh vào mảng kết quả và Pop khỏi Stack
			path = append(path, curr)
			stack = stack[:len(stack)-1]
		}
	}

	// 3. Kết quả lấy ra từ Stack bị ngược, cần đảo ngược lại mảng
	reverse(path)
	return path
}

func reverse(arr []int) {
	for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}
}

func main() {
	// Đồ thị mô phỏng một lộ trình có Chu trình Euler
	n := 4
	edges := [][]int{
		{0, 1}, {1, 2}, {2, 0}, // Vòng lặp chính 0-1-2-0
		{1, 3}, {3, 1},         // Vòng lặp phụ 1-3-1
	}

	path := findEulerianPath(n, edges)
	fmt.Printf("Lộ trình Euler (Đi qua mọi cạnh 1 lần): %v\n", path)
	// Kết quả mong đợi: [0 1 3 1 2 0] hoặc các biến thể tương đương
}

5. Áp dụng Thực tiễn tại Hệ thống Enterprise

Việc phân biệt rõ ràng bản chất giữa bài toán "Đỉnh" (Hamilton) và bài toán "Cạnh" (Euler) giúp kỹ sư định hướng giải pháp chính xác:

• Tối ưu lộ trình gom rác / Rửa đường (Eulerian Path): Các thuật toán như Hierholzer có thể giải quyết nhanh chóng lộ trình cho các phương tiện công ích, đảm bảo không một con đường nào trong khu đô thị bị bỏ sót, giúp tiết kiệm triệt để lượng nhiên liệu di chuyển.

• Phân tích DNA (Tin sinh học): Việc tái tạo trình tự Gen (Genome Sequencing) từ hàng triệu mảnh ghép nhỏ ban đầu được quy về bài toán tìm đường đi Hamilton (rất chậm). Sau đó, các nhà khoa học đã dùng đồ thị De Bruijn để biến nó thành bài toán tìm Chu trình Euler, cho phép ráp nối Gen trong thời gian tuyến tính $O(N)$.

• Lộ trình Giao hàng & Vận tải hành khách (Hamiltonian / TSP): Định tuyến xe tải giao hàng cho Hasaki hoặc Grab. Vì đây là bài toán NP-Hard, trong môi trường Production, người ta hiếm khi cố gắng tìm lời giải chính xác tuyệt đối. Thay vào đó, hệ thống backend sử dụng thuật toán như Ant Colony Optimization (Thuật toán Kiến), Simulated Annealing (Luyện kim nhân tạo) hoặc Dynamic Programming (Mô hình OR-Tools của Google) để tìm ra một lộ trình "gần như tốt nhất" trong vòng vài giây.

Chúng ta đã trải qua một chặng đường dài và bao quát gần như toàn bộ các Cấu trúc dữ liệu và Thuật toán nền tảng của Khoa học máy tính. Mọi thuật toán tìm kiếm, quy hoạch động hay lý thuyết đồ thị đều là công cụ để tối ưu hóa việc phân bổ tài nguyên.