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

Khái niệm

Cho đồ thị vô hướng, kiểm tra xem nó có chứa tập độc lập kích thước l hay không. Nếu tồn tại, in 'Yes', ngược lại 'No'. Tập độc lập là tập các đỉnh không kết nối trực tiếp với nhau.

Đầu vào

L = 4, graph = [[1, 0, 1, 0, 0], [0, 1, 1, 0, 0],[1, 1, 1, 1, 1], [0, 0, 1, 1, 0],[0, 0, 1, 0, 1]]

Đầu ra

Yes

Đồ thị chứa tập độc lập kích thước 4 (đỉnh 0, 1, 3, 4 không kết nối trực tiếp). Kết quả 'Yes'.

Đầu vào

L = 4, graph =[[1, 1, 1, 0, 0],[1, 1, 1, 0, 0],[1, 1, 1, 1, 1],[0, 0, 1, 1, 0],[0, 0, 1, 0, 1]]

Đầu ra

No

Đồ thị không chứa tập độc lập kích thước 4. Kết quả 'No'.

Phương pháp

• Khởi tạo biến sol = false.
• Tìm tất cả tập con đỉnh kích thước L từ đồ thị.
• Nếu tìm thấy tập độc lập kích thước l, đặt sol = true và trả về.
• Ngược lại tiếp tục kiểm tra các tập khác.
• Cuối cùng, nếu sol true in 'Yes', ngược lại 'No'.

Ví dụ

// C++ kiểm tra đồ thị có tập độc lập kích thước k
#include <bits/stdc++.h>
using namespace std;

bool check1(int[][5], vector<int>&, int);

bool func(int graph1[][5], vector<int>&arr1, int l, int index1, bool sol1[]){
    if (l == 0){
        if (check1(graph1, arr1, arr1.size())){
            sol1[0] = true;
            return true;
        }
    }
    else{
        if (index1 >= l){
            vector<int> newvec(arr1.begin(), arr1.end());
            newvec.push_back(index1);
            return (func(graph1, newvec, l - 1, index1 - 1, sol1) or func(graph1, arr1, l, index1 - 1, sol1));
        }
        else{
            arr1.push_back(index1);
            return func(graph1, arr1, l - 1, index1 - 1, sol1);
        }
    }
}

bool check1(int graph1[][5], vector<int>&arr1, int n1){
    for (int i = 0; i < n1; i++)
        for (int j = i + 1; j < n1; j++)
            if (graph1[arr1[i]][arr1[j]] == 1)
                return false;
    return true;
}

int main(){
    int graph1[][5] = {{1, 0, 1, 0, 0},{0, 1, 1, 0, 0},{1, 1, 1, 1, 1},{0, 0, 1, 1, 0}, {0, 0, 1, 0, 1}};
    int l = 4;
    vector<int> arr1;
    bool sol1[] = {false};
    int n1 = sizeof(graph1) / sizeof(graph1[0]);
    func(graph1, arr1, l, n1 - 1, sol1);
    if (sol1[0]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Đầu ra

Yes