ধারণা
প্রদত্ত অনির্দেশিত গ্রাফের সাপেক্ষে, এটি 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 এ পরিবর্তন করুন এবং রিটার্ন করুন।
- অন্যথায় অন্যান্য সম্ভাব্য সেটের জন্য চেক করা চালিয়ে যান।
- অবশেষে, যদি সল সত্য হয়, তবে 'হ্যাঁ' প্রিন্ট করুন অন্যথা 'না' প্রিন্ট করুন।
উদাহরণ
// 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
