একটি গ্রাফকে বাইপার্টাইট গ্রাফ বলা হয়, যখন সেই গ্রাফের ভার্টেক্সগুলোকে দুটি স্বাধীন সেটে ভাগ করা যায় যাতে গ্রাফের প্রতিটি এজ হয় প্রথম সেট থেকে শুরু হয়ে দ্বিতীয় সেটে শেষ হয়, অথবা দ্বিতীয় সেট থেকে শুরু হয়ে প্রথম সেটে সংযুক্ত হয়। অন্য কথায়, কোনো এজ একই সেটের ভিতরে পাওয়া যায় না।
বাইপার্টাইট গ্রাফ যাচাই করা সম্ভব ভার্টেক্স কালারিং ব্যবহার করে। যখন একটি ভার্টেক্স একই সেটে থাকে, তখন उसका একই রঙ থাকে, অন্য সেটের জন্য রঙটি পরিবর্তন হয়।
ইনপুট এবং আউটপুট
ইনপুট: অ্যাডজেসেন্সি ম্যাট্রিক্স। 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 আউটপুট: গ্রাফটি বাইপার্টাইট।
এলগরিদম
isBipartite(source)
ইনপুট: সোর্স ভার্টেক্স।
আউটপুট: গ্রাফ বাইপার্টাইট হলে true।
শুরু
একটি খালি কিউ qu এবং একটি কালার লিস্ট colorArray সংজ্ঞায়িত করুন
প্রাথমিকভাবে কোনো নোড যেকোনো রঙে কালার করা নেই
সোর্স ভার্টেক্সকে লাল রঙ দিন
সোর্সকে qu-তে যোগ করুন
যতক্ষণ qu খালি নয়, করুন
qu থেকে আইটেম সরিয়ে u-তে নিন
যদি কোনো সেলফ-লুপ থাকে, তবে
return false
u-র সাথে সংযুক্ত সব ভার্টেক্স v এর জন্য, করুন
যদি v-র কোনো রঙ নেই, তবে
যদি colorArray[u] = red, তবে
colorArray[v] := blue
অন্যথায় যদি colorArray[u] = blue, তবে
colorArray[v] := red
v কে কিউতে যোগ করুন
যদি colorArray[v] = colorArray[u], তবে
return false
শেষ লুপ
শেষ লুপ
return true
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <string>
#include <queue>
#define NODE 6
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 0}
};
bool isBipartite(int source) {
queue<int> qu;
string colorArray[NODE];
for(int i = 0; i < NODE; i++)
colorArray[i] = "No Color"; // প্রাথমিকভাবে সব ভার্টেক্সের জন্য কোনো রঙ সেট করা নেই
colorArray[source] = "Red"; // সোর্স ভার্টেক্সের সাথে লাল রঙ অ্যাসাইন করুন
qu.push(source); // সোর্সকে কিউতে যোগ করুন
while(!qu.empty()) {
int u = qu.front(); qu.pop();
if(graph[u][u] == 1) // সেলফ-লুপ আছে
return false;
for(int v = 0; v < NODE; v++) {
if(graph[u][v] != 0 && colorArray[v] == "No Color") {
if(colorArray[u] == "Red") // সন্নিহিত লিস্টকে أل্টারনেট রঙ দিন
colorArray[v] = "Blue";
else if(colorArray[u] == "Blue")
colorArray[v] = "Red";
qu.push(v); // নতুন সন্নিহিত নোড কিউতে যোগ করুন
} else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
return false; // যখন u এবং সন্নিহিত একই রঙের
}
}
}
return true;
}
int main() {
bool check;
check = isBipartite(0);
if(check)
cout << "The graph is bipartite." << endl;
else
cout << "The graph is not bipartite." << endl;
}
আউটপুট
The graph is bipartite.
