Chu trình Euler và chu trình Hamilton

NỘI DUNG

Khái niệm

Chu trình Euler là một chu trình trên đồ thị vô hướng hoặc đồ thị có hướng mà đi qua mỗi cạnh của đồ thị một lần và trở về đỉnh xuất phát. Đồ thị được gọi là Euler nếu nó có chu trình Euler. Điều kiện cần để một đồ thị có chu trình Euler là mỗi đỉnh trong đồ thị đó phải có bậc chẵn. Một vài ví dụ về đồ thị Euler bao gồm đồ thị đầy đủ, đồ thị hai phía và đồ thị mạng:

Đồ thị đầy đủ: Đây là đồ thị vô hướng có mọi cặp đỉnh đều nối với nhau bằng một cạnh. Ví dụ: đồ thị với 4 đỉnh A, B, C, D và 6 cạnh AB, AC, AD, BC, BD, CD.
Đồ thị hai phía: Đây là đồ thị có thể chia thành hai tập đỉnh sao cho mỗi cạnh trong đồ thị nối một đỉnh trong tập này với một đỉnh trong tập kia. Ví dụ: đồ thị với 6 đỉnh A, B, C, D, E, F và 7 cạnh AB, AC, BD, BE, CD, DE, EF.
Đồ thị mạng: Đây là đồ thị có hướng, trong đó mỗi cạnh được gán một giá trị số nguyên gọi là trọng số. Ví dụ: đồ thị với 4 đỉnh A, B, C, D và 5 cạnh A→B (trọng số 2), A→C (trọng số 3), B→C (trọng số 1), C→D (trọng số 4), D→A (trọng số 5).

Chu trình Hamilton là một chu trình trên đồ thị vô hướng hoặc đồ thị có hướng mà đi qua mỗi đỉnh của đồ thị một lần và trở về đỉnh xuất phát. Đồ thị được gọi là Hamilton nếu nó có chu trình Hamilton. Tuy nhiên, điều kiện để một đồ thị có chu trình Hamilton là khá phức tạp và chưa được tìm ra một cách tổng quát. Một vài ví dụ về đồ thị Hamilton bao gồm đồ thị đầy đủ, đồ thị hai phía và đồ thị ngũ giác đều.

Thuật toán Chu trình Euler

Thuật toán Chu trình Euler được sử dụng để tìm kiếm một chu trình Euler trên một đồ thị vô hướng hoặc có hướng. Điều kiện cần để một đồ thị có chu trình Euler là mỗi đỉnh trong đồ thị đó phải có bậc chẵn. Các bước của thuật toán như sau:

Chọn một đỉnh bất kỳ trong đồ thị và bắt đầu đi theo một cạnh bất kỳ.
Nếu đang đi trên một cạnh (u, v) và v không phải là đỉnh cuối cùng của chu trình, thì chọn một cạnh khác đi qua v.
Nếu v đã là đỉnh cuối cùng của chu trình, kiểm tra xem tất cả các đỉnh trong đồ thị đã được đi qua. Nếu chưa, chọn một đỉnh mới chưa đi qua và bắt đầu một chu trình mới từ đó.
Lặp lại các bước 2 và 3 cho đến khi tìm thấy chu trình Euler trên đồ thị hoặc không có chu trình Euler trên đồ thị.

Để tìm kiếm chu trình Euler trên đồ thị có hướng, ta cần sử dụng thuật toán tương tự nhưng có một số điểm khác biệt nhất định. Nói chung, thuật toán Chu trình Euler cho đồ thị có hướng có thể phức tạp hơn thuật toán cho đồ thị vô hướng.

Cài đặt Chu trình Euler với Python

Dưới đây là một ví dụ về cách cài đặt thuật toán Chu trình Euler bằng Python để tìm kiếm chu trình Euler trên một đồ thị vô hướng:

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def dfs(self, v, visited):
        visited[v] = True
        for i in self.graph[v]:
            if visited[i] == False:
                self.dfs(i, visited)

    def is_eulerian(self):
        visited = [False] * self.V
        for i in range(self.V):
            if len(self.graph[i]) % 2 != 0:
                return False
        self.dfs(0, visited)
        for i in range(self.V):
            if visited[i] == False and len(self.graph[i]) > 0:
                return False
        return True

    def print_eulerian_path(self):
        if self.is_eulerian() == False:
            print("Không có chu trình Euler trên đồ thị này.")
            return
        else:
            print("Chu trình Euler trên đồ thị này là:")
        stack = []
        curr_vertex = 0
        while len(stack) > 0 or len(self.graph[curr_vertex]) > 0:
            if len(self.graph[curr_vertex]) == 0:
                path.append(curr_vertex)
                curr_vertex = stack.pop()
            else:
                stack.append(curr_vertex)
                next_vertex = self.graph[curr_vertex].pop()
                self.graph[next_vertex].remove(curr_vertex)
                curr_vertex = next_vertex
        path.append(curr_vertex)
        for vertex in reversed(path):
            print(vertex, end=" ")

g = Graph(5)
g.add_edge(1, 0)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(0, 3)
g.add_edge(3, 4)
g.print_eulerian_path()

Ở đây, chúng ta sử dụng lớp Graph để đại diện cho đồ thị và các phương thức của nó để kiểm tra xem đồ thị có chu trình Euler hay không và in ra chu trình đó. Trong hàm is_eulerian(), chúng ta kiểm tra xem tất cả các đỉnh trong đồ thị có bậc chẵn hay không và kiểm tra xem đồ thị liên thông hay không bằng cách thực hiện một DFS từ đỉnh 0 và kiểm tra xem tất cả các đỉnh đã được đi qua hay không. Trong hàm print_eulerian_path(), chúng ta sử dụng một stack và một vòng lặp để xây dựng chu trình Euler từ đồ thị.

Thuật toán Chu trình Hamilton

Thuật toán Chu trình Hamilton là một thuật toán tìm kiếm để tìm ra chu trình Hamilton trên một đồ thị vô hướng hoặc có hướng. Chu trình Hamilton là một chuỗi các đỉnh trong đồ thị sao cho mỗi đỉnh trong đó đều được đi qua đúng một lần và kết thúc ở đỉnh xuất phát.

Một số thuật toán tìm kiếm như Duyệt theo chiều rộng (BFS), Duyệt theo chiều sâu (DFS), Quay lui (Backtracking) được sử dụng để tìm chu trình Hamilton trên đồ thị. Tuy nhiên, do vấn đề về tính toán, việc tìm kiếm chu trình Hamilton trên đồ thị là một bài toán NP-khó.

Dưới đây là một thuật toán tìm kiếm chu trình Hamilton đơn giản bằng DFS trên một đồ thị vô hướng:

Bắt đầu từ một đỉnh bất kỳ của đồ thị.
Chọn một đỉnh kế tiếp sao cho đỉnh đó chưa được đi qua và được kết nối với đỉnh hiện tại.
Đi tiếp đến đỉnh kế tiếp này và đánh dấu nó là đã đi qua.
Nếu tất cả các đỉnh đều được đi qua, kiểm tra xem đỉnh cuối cùng có kết nối với đỉnh xuất phát không.
Nếu có, in ra chu trình Hamilton đó. Nếu không, trở về đỉnh trước đó và thử một đường khác.

Cài đặt Chu trình Hamilton

Dưới đây là một ví dụ cài đặt Chu trình Hamilton bằng Python:

def hamiltonian_cycle(graph, start_vertex):
    path = [start_vertex]

    def dfs(vertex):
        nonlocal path
        if len(path) == len(graph):
            if graph[path[-1]][path[0]] == 1:
                return True
            else:
                return False

        for v in range(len(graph)):
            if graph[vertex][v] == 1 and v not in path:
                path.append(v)
                if dfs(v) == True:
                    return True
                path.pop()

        return False

    if dfs(start_vertex) == True:
        return path
    else:
        return None

Trong ví dụ này, chúng ta sử dụng hàm dfs() để thực hiện việc tìm kiếm chu trình Hamilton. Hàm này thực hiện việc đi qua tất cả các đỉnh và kiểm tra xem một chu trình có tồn tại hay không. Nếu có, hàm trả về chu trình Hamilton. Nếu không, hàm trả về None. Chúng ta sử dụng một mảng path để lưu trữ chu trình các đỉnh đã đi qua và kiểm tra các đỉnh tiếp theo để tạo ra chu trình Hamilton.

Để kiểm tra xem đỉnh cuối cùng có kết nối với đỉnh xuất phát hay không, chúng ta kiểm tra giá trị của phần tử đầu tiên và cuối cùng trong mảng path. Nếu chúng kết nối với nhau, thì chu trình Hamilton tồn tại và hàm trả về True. Ngược lại, hàm trả về False.

Trong ví dụ này, chúng ta sử dụng một đồ thị vô hướng được biểu diễn bằng ma trận kề. Tuy nhiên, thuật toán này cũng có thể được sử dụng trên các loại đồ thị khác như đồ thị có hướng hoặc đồ thị có trọng số.

Tuy nhiên, chúng ta cần lưu ý rằng, vì đây là một bài toán NP-khó, nên đối với các đồ thị lớn, việc tìm kiếm chu trình Hamilton sẽ mất rất nhiều thời gian tính toán. Do đó, các phương pháp tìm kiếm khác như thuật toán quay lui có thể được sử dụng để tìm kiếm chu trình Hamilton trong các trường hợp lớn hơn.

Lập trình Python