একটি দ্বিভাজ্য গ্রাফ হল এমন গ্রাফ যেখানে গ্রাফ কলারিং (Graph Coloring) দুটি রঙ ব্যবহার করে সম্ভব। অর্থাৎ, একটি সেটের ভের্টেক্সগুলো একই রঙ দিয়ে রঙ করা যায়। এটি একটি সি++ প্রোগ্রাম যা BFS ব্যবহার করে গ্রাফটি দ্বিভাজ্য কিনা তা যাচাই করে।
অ্যালগরিদম
শুরু ফাংশন Bipartite(): ১) সোর্স ভের্টেক্সকে একটি রঙ অ্যাসাইন করুন ২) প্রথম রঙ ব্যতীত সব পড়োশি কে অন্য একটি রঙ দিন। ৩) পড়োশির পড়োশিদের প্রথম রঙ দিন। ৪) এইভাবে সব ভের্টেক্সকে রঙ দিন যাতে k-ওয়ে কলারিং সমস্যা (k = 2) এর সব কনস্ট্রেইন্ট মেনে চলে। ৫) রঙ দিয়ে সময়, যদি কোনো পড়োশি বর্তমান ভের্টেক্সের মতো একই রঙে থাকে, তবে গ্রাফ ২ রঙ দিয়ে রঙ করা সম্ভব নয় অর্থাৎ গ্রাফটি দ্বিভাজ্য নয়। শেষ
উদাহরণ
#include <iostream> #include <queue> #define V 5 using namespace std; bool Bipartite(int G[][V], int s) { int colorA[V]; for (int i = 0; i < V; ++i) colorA[i] = -1; colorA[s] = 1; //সোর্স ভের্টেক্সকে একটি রঙ অ্যাসাইন করুন queue <int> q; //ভের্টেক্স নম্বরের একটি কিউ তৈরি করুন এবং BFS ট্রাভার্সালের জন্য সোর্স ভের্টেক্স ইনকিউ করুন q.push(s); while (!q.empty()) { int w = q.front(); //একটি ভের্টেক্স ডিকিউ করুন q.pop(); for (int v = 0; v < V; ++v) //সব নন-কলারড সংলগ্ন ভের্টেক্স খুঁজুন { if (G[w][v] && colorA[v] == -1) //w থেকে v-তে একটি এজ আছে এবং গন্তব্য v রঙ করা নেই { colorA[v] = 1 - colorA[w]; //w-এর এই সংলগ্ন v-কে অল্টারনেট রঙ দিন q.push(v); } else if (G[w][v] && colorA[v] == colorA[w]) //w থেকে v-তে একটি এজ আছে এবং গন্তব্য //v,u-এর মতো একই রঙে রঙ করা আছে return false; } } return true; //যদি সব সংলগ্ন ভের্টেক্স অল্টারনেট রঙ দিয়ে রঙ করা যায় } int main() { int G[][V] = {{ 0, 1, 0, 0}, { 1, 0, 0, 0}, { 0, 0, 0, 1}, { 1, 0, 1, 0}}; if (Bipartite(G, 0)) cout << "The Graph is Bipartite"<<endl; else cout << "The Graph is Not Bipartite"<<endl; return 0; }
আউটপুট
The Graph is Bipartite
