Khái niệm
Đối với một đồ thị vô hướng đã cho, hãy xác minh xem nó có chứa một tập hợp kích thước độc lập l. Nếu tồn tại một tập hợp độc lập có kích thước l thì in ‘Có’, còn không thì in ‘Không’. Cần lưu ý rằng tập hợp độc lập trong biểu đồ được định nghĩa là một tập các đỉnh mà các đỉnh không được 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ị trên chứa tập hợp kích thước 4 độc lập (các đỉnh 0, 1, 3, 4 không nối trực tiếp với nhau). Do đó, kết quả đầu ra là "Có".
Đầ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
Trong biểu đồ, biểu đồ trên không chứa tập hợp kích thước độc lập 4. Do đó, kết quả đầu ra là "Không".
Phương pháp
- Lúc đầu, hãy khởi tạo một biến sol với giá trị boolean False.
- Xác định tất cả các bộ đỉnh có thể có của kích thước L từ đồ thị đã cho.
- Người ta thấy rằng nếu tìm thấy một tập hợp độc lập có kích thước l, hãy thay đổi giá trị của sol thành True và trả về.
- Nếu không, hãy tiếp tục kiểm tra các nhóm khả thi khác.
- Cuối cùng, nếu sol là True, hãy in "Có", nếu không thì in "No".
Ví dụ
// C++ code to check if a given graph
// contains an independent set of size k
#include <bits/stdc++.h>
using namespace std;
// Shows function prototype
bool check1(int[][5], vector<int>&, int);
// Shows function to construct a set of given size l
bool func(int graph1[][5], vector<int>&arr1,
int l, int index1, bool sol1[]){
// Verify if the selected set is independent or not.
// Used to change the value of sol to True and return
// if it is independent
if (l == 0){
if (check1(graph1, arr1, arr1.size())){
sol1[0] = true;
return true;
}
}
else{
// Now set of size l can be formed even if we don't
// include the vertex at current index.
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));
}
// Now set of size l cannot be formed if we don't
// include the vertex at current index.
else{
arr1.push_back(index1);
return func(graph1, arr1, l - 1,
index1 - 1, sol1);
}
}
}
// Shows function to verify if the given set is
// independent or not
// arr --> set of size l (contains the
// index of included vertex)
bool check1(int graph1[][5], vector<int>&arr1, int n1){
// Verify if each vertex is connected to any other
// vertex in the set or not
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;
}
// Driver Code
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; // Empty set
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