Kiểm tra đồ thị vô hướng có tập độc lập kích thước cho trước trong Python

Cho đồ thị vô hướng, kiểm tra có tập độc lập (independent set) kích thước l không. Tập độc lập: tập đỉnh không có cặp nào kề nhau trực tiếp.

Ví dụ: Đồ thị 5 đỉnh, l=4 → Yes (tìm được tập 4 đỉnh không kề nhau).

Thuật toán Backtracking

1. Hàm is_valid(graph, arr): kiểm tra tập arr có phải independent set không (kiểm tra mọi cặp trong arr không có cạnh).
2. Hàm solve(graph, arr, k, index, sol):
   • Nếu k=0: kiểm tra is_valid, nếu True → sol[0]=True.
   • Nếu index ≥ k: thử chọn index (thêm vào arr, k-1, index-1) HOẶC không chọn (k, index-1).
   • Ngược lại: bắt buộc chọn index.
3. Gọi solve(graph, [], k, n-1, [False]).

Ví dụ code

def is_valid(graph, arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if graph[arr[i]][arr[j]] == 1:
                return False
    return True

def solve(graph, arr, k, index, sol):
    if k == 0:
        if is_valid(graph, arr):
            sol[0] = True
        return
    if index >= k:
        return (solve(graph, arr + [index], k - 1, index - 1, sol) or
                solve(graph, arr, k, index - 1, sol))
    else:
        return solve(graph, arr + [index], k - 1, index - 1, sol)

graph = [
    [1, 1, 0, 0, 0],
    [1, 1, 1, 1, 1],
    [0, 1, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 0, 1]
]
k = 4
arr = []
sol = [False]
solve(graph, arr, k, len(graph) - 1, sol)
print("Yes" if sol[0] else "No")

Input

Ma trận kề 5x5, k=4

Output

Yes