แนวคิด
ในส่วนของกราฟที่ไม่ได้กำหนดทิศทาง ให้ตรวจสอบว่ามีชุดขนาด l อิสระหรือไม่ หากมีชุดขนาดอิสระ l พิมพ์ 'ใช่' มิฉะนั้นให้พิมพ์ 'ไม่ใช่' โปรดทราบว่าชุดอิสระในกราฟถูกกำหนดเป็นชุดของจุดยอดซึ่งไม่ได้เชื่อมต่อโดยตรงต่อกัน
อินพุต
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]];
ผลลัพธ์
Yes
กราฟด้านบนประกอบด้วยชุดอิสระขนาด 4 (จุดยอด 0, 1, 3, 4 ไม่เชื่อมต่อกันโดยตรง) ดังนั้นผลลัพธ์ที่ได้คือ 'ใช่'
อินพุต
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]];
ผลลัพธ์
No
ในแผนภาพ กราฟด้านบนไม่มีชุดขนาด 4 ที่เป็นอิสระ ดังนั้นเอาต์พุตจึงเป็น "ไม่"
วิธีการ
- ในตอนแรก ให้เริ่มต้นตัวแปรโซลด้วยค่าบูลีนที่เป็นเท็จ
- กำหนดชุดจุดยอดที่เป็นไปได้ทั้งหมดที่มีขนาด L จากกราฟที่กำหนด
- พบว่าหากพบชุดขนาด l อิสระ ให้เปลี่ยนค่าของ sol เป็น True แล้วคืนค่า
- ไม่เช่นนั้นให้ตรวจสอบชุดอื่นๆ ที่เป็นไปได้ต่อไป
- สุดท้าย ถ้าโซลเป็น True ให้พิมพ์ 'Yes' หรืออื่น ๆ ให้พิมพ์ 'No'
ตัวอย่าง
// 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;
} ผลลัพธ์
Yes
