একটি দ্বিভাজ্য গ্রাফ হল এমন গ্রাফ যেখানে গ্রাফ কলারিং (Graph Coloring) দুটি রঙ ব্যবহার করে সম্ভব। অর্থাৎ, একটি সেটের ভের্টেক্সগুলো একই রঙ দিয়ে রঙ করা যায়। এটি একটি সি++ প্রোগ্রাম যা ২ রঙ অ্যালগরিদম ব্যবহার করে গ্রাফটি দ্বিভাজ্য কিনা তা যাচাই করে।
ফাংশন ও সিউডোকোড
শুরু ১. isSafe() ফাংশন ডেভেলপ করুন যাতে ভের্টেক্স v-এর জন্য বর্তমান রঙ অ্যাসাইনমেন্ট সেফ কিনা তা চেক করা যায়, অর্থাৎ এজ আছে কিনা। যদি থাকে, তবে পরবর্তীতে চেক করুন যে নতুন ভের্টেক্সে ভরা হয়নি যেটা তার সংলগ্ন ভের্টেক্সগুলো ব্যবহার করেছে। ২. ফাংশন graphColoringtil(bool g[V][V], int k, int col[], int v) : g[V][V] = এটি একটি ২ডি অ্যারে যেখানে V হল গ্রাফের ভের্টেক্স সংখ্যা k = ব্যবহার করা যেতে পারে সর্বোচ্চ রঙের সংখ্যা। col[] = একটি রঙ অ্যারে যাতে ১ থেকে m পর্যন্ত নম্বর থাকবে। if v == V return true For c = 1 to k if (isSafe(v, g, col, c)) col[v] = c if (graphColoringtil (g, k, col, v+1) == true) return true col[v] = 0 return false ৩.ফাংশন graphColoring(bool g[V][V], int k): for i = 0 to V-1 color[i] = 0 if (graphColoringtil(g, k, color, 0) == false) return false return true
উদাহরণ
#include <iostream> #include <cstdio> #define V 4 using namespace std; bool isSafe (int v, bool g[V][V], int col[], int C) //m কলারিং সমস্যা সমাধান করতে { for (int i = 0; i < V; i++) if (g[v][i] && C == col[i]) return false; return true; } bool graphColoringtil(bool g[V][V], int k, int col[], int v) { if (v == V) //যদি সব ভের্টেক্সে রঙ অ্যাসাইন করা হয়ে যায় return true; for (int c = 1; c <= k; c++) //এই ভের্টেক্স v বিবেচনা করুন এবং বিভিন্ন রঙ ট্রাই করুন { if (isSafe(v, g, col, c)) //চেক করুন v-তে রঙ c অ্যাসাইন করা ঠিক আছে কিনা { col[v] = c; if (graphColoringtil (g, k, col, v+1) == true) //বাকি ভের্টেক্সগুলোর রঙ অ্যাসাইন করতে রিকার্সন return true; col[v] = 0; //যদি রঙ c অ্যাসাইন করা সমাধানে না जाये তবে সরিয়ে দিন } } return false; }
আউটপুট
The graph is Bipartite
