Cài đặt thuật toán Karger trong lập trình

Trong lĩnh vực thiết kế và phân tích thuật toán, Karger Algorithm là một trong những thuật toán nổi tiếng và hữu ích được sử dụng để giải quyết bài toán cắt nhỏ nhất (Minimum Cut) trong đồ thị. Thuật toán được đặt theo tên của David Karger, người đã phát triển thuật toán này vào năm 1993. Karger Algorithm là một thuật toán ngẫu nhiên, và vì lý do này, việc thực hiện thuật toán này có thể cho kết quả khác nhau mỗi lần chạy.

Cơ bản về Karger Algorithm

Thuật toán cắt nhỏ nhất của Karger hoạt động dựa trên nguyên tắc đơn giản: liên tục co rút các cạnh của đồ thị cho đến khi chỉ còn lại hai đỉnh. Số lượng các cạnh giữa hai đỉnh cuối cùng sẽ là trọng số của cắt nhỏ nhất. Thuật toán này có tính ngẫu nhiên: tại mỗi bước, một cạnh ngẫu nhiên trong đồ thị được chọn và hai đỉnh của cạnh đó được hợp nhất lại thành một đỉnh, mà không có cạnh lặp lại hoặc việc hợp nhất đỉnh gây ra sự cắt những cạnh còn lại.

Các bước thực hiện

1. Khởi tạo: Bắt đầu với đồ thị ban đầu với các đỉnh và cạnh ban đầu.
2. Chọn cạnh ngẫu nhiên: Chọn một cạnh ngẫu nhiên từ đồ thị.
3. Hợp nhất đỉnh: Hợp nhất hai đỉnh của cạnh đã chọn thành một đỉnh duy nhất.
4. Loại bỏ cạnh vòng lặp: Loại bỏ các cạnh tự vòng lặp (self-looping edges).
5. Lặp lại: Tiếp tục quá trình trên cho đến khi chỉ còn lại hai đỉnh trong đồ thị.
6. Kết quả: Trọng số của cắt nhỏ nhất sẽ là số cạnh còn lại giữa hai đỉnh cuối cùng.

Mã giả

Dưới đây là mã giả cho Karger Algorithm:

Cài đặt Karger(Graph G):
    Trong khi (G có nhiều hơn 2 đỉnh):
        Chọn một cạnh ngẫu nhiên (u, v) từ G
        Hợp nhất u và v thành một đỉnh mới w
        Cập nhật danh sách các cạnh của w tương ứng
        Loại bỏ các cạnh tự vòng lặp tại w

    Trả về số lượng các cạnh còn lại trong G, đó là trọng số của cắt nhỏ nhất

Minh họa cài đặt trong Python

Dưới đây là một ví dụ về việc cài đặt thuật toán Karger bằng ngôn ngữ lập trình Python:

import random
import copy

class Graph:
    def __init__(self, vertices, edges):
        self.vertices = vertices  # Danh sách các đỉnh
        self.edges = edges  # Danh sách các cạnh (u, v)

    def find_min_cut(self):
        # Clone the graph to prevent modifications to the original graph
        temp_graph = copy.deepcopy(self)
        while len(temp_graph.vertices) > 2:
            # Chọn cạnh ngẫu nhiên
            u, v = random.choice(temp_graph.edges)
            # Hợp nhất hai đỉnh u và v
            temp_graph.contract(u, v)
        return len(temp_graph.edges)

    def contract(self, u, v):
        # Hợp đỉnh v vào đỉnh u
        new_edges = []
        for edge in self.edges:
            if edge == (u, v) or edge == (v, u):
                continue  # Loại bỏ cạnh cũ u-v
            elif edge[0] == v:
                new_edges.append((u, edge[1]))  # Đổi v thành u
            elif edge[1] == v:
                new_edges.append((edge[0], u))  # Đổi v thành u
            else:
                new_edges.append(edge)
        self.edges = new_edges
        # Xóa đỉnh v
        self.vertices.remove(v)

# Ví dụ sử dụng
vertices = [1,2,3,4]
edges = [(1,2), (1,3), (2,3), (2,4), (3,4)]
graph = Graph(vertices, edges)
min_cut = graph.find_min_cut()
print(f"Minimum cut of the graph is: {min_cut}")

Kết luận

Karger Algorithm là một công cụ mạnh mẽ và thực hiện rất tốt nhiệm vụ tìm cắt nhỏ nhất trong đồ thị. Mặc dù tính ngẫu nhiên của nó có thể dẫn đến việc chạy nhiều lần để đảm bảo kết quả chính xác, tính hiệu quả về thời gian của nó khiến nó trở thành lựa chọn lý tưởng cho các bài toán đồ thị lớn.