অয়লার পথ হলো এমন একটি পথ, যার মাধ্যমে আমরা প্রতিটি এজকে ঠিক একবার দিয়ে যেতে পারি। আমরা একই ভার্টেক্সগুলোকে একাধিকবার ব্যবহার করতে পারি। অয়লার সার্কিট হলো অয়লার পথের একটি বিশেষ ধরন। যখন অয়লার পথের শুরুর ভার্টেক্স সেই পথের শেষ ভার্টেক্সের সাথে সংযুক্ত থাকে, তখন তাকে অয়লার সার্কিট বলা হয়।
পথ এবং সার্কিট শনাক্ত করতে আমাদের এই শর্তগুলো মানতে হবে −
- গ্রাফটি সংযুক্ত (connected) হতে হবে।
- যখন ঠিক দুটি ভার্টেক্সের ডিগ্রি বিজোড় হয়, তবে এটি একটি অয়লার পথ।
- যখন একটি অননির্দেশিত গ্রাফের কোনো ভার্টেক্সের ডিগ্রি বিজোড় নয়, তবে এটি একটি অয়লার সার্কিট।
ইনপুট এবং আউটপুট
ইনপুট: একটি গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স। 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 আউটপুট: গ্রাফটিতে একটি অয়লারিয়ান পথ আছে।
এলগরিদম
traverse(u, visited)
ইনপুট: শুরুর নোড u এবং ভিজিটেড নোড যাতে বুঝতে পারা যায় কোন নোড ভিজিটেড।
আউটপুট: সব সংযুক্ত ভার্টেক্স ট্রাভার্স করুন।
শুরু
u কে ভিজিটেড চিহ্নিত করুন
u-র সাথে সন্নিহিত সব ভার্টেক্স v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
traverse(v, visited)
শেষ লুপ
শেষ
isConnected(graph)
ইনপুট: গ্রাফ।
আউটপুট: গ্রাফ সংযুক্ত থাকলে true।
শুরু
ভিজিটেড অ্যারে সংজ্ঞায়িত করুন
গ্রাফের সব ভার্টেক্স u এর জন্য, করুন
সব নোডকে অনভিজিটেড করুন
traverse(u, visited)
যদি কোনো অনভিজিটেড নোড অবশিষ্ট থাকে, তবে
return false
শেষ লুপ
return true
শেষ
isEulerian(Graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: অয়লারিয়ান না হলে ০, অয়লার পথ হলে ১, অয়লার সার্কিট হলে ২ ফেরত দেয়।
শুরু
যদি isConnected() false হয়, তবে
return false
প্রতিটি নোডের ডিগ্রির একটি লিস্ট সংজ্ঞায়িত করুন
oddDegree := 0
গ্রাফের সব ভার্টেক্স i এর জন্য, করুন
i-র সাথে সংযুক্ত সব ভার্টেক্স j এর জন্য, করুন
ডিগ্রি বাড়ান
শেষ লুপ
যদি ভার্টেক্স i-এর ডিগ্রি বিজোড় হয়, তবে
oddDegree বাড়ান
শেষ লুপ
যদি oddDegree > 2, তবে
return 0
যদি oddDegree = 0, তবে
return 2
অন্যথায়
return 1
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
void traverse(int u, bool visited[]) {
visited[u] = true; // v কে ভিজিটেড চিহ্নিত করুন
for(int v = 0; v < NODE; v++) {
if(graph[u][v]) {
if(!visited[v])
traverse(v, visited);
}
}
}
bool isConnected() {
bool *vis = new bool[NODE];
// সব ভার্টেক্স u কে শুরুর পয়েন্ট ধরে, চেক করুন সব নোড দৃশ্যমান কিনা
for(int u = 0; u < NODE; u++) {
for(int i = 0; i < NODE; i++)
vis[i] = false; // কোনো নোড ভিজিটেড নেই এমনভাবে ইনিশিয়ালাইজ করুন
traverse(u, vis);
for(int i = 0; i < NODE; i++) {
if(!vis[i]) // যদি কোনো নোড ট্রাভার্সাল দিয়ে ভিজিটেড না হয়, গ্রাফ সংযুক্ত নয়
return false;
}
}
return true;
}
int isEulerian() {
if(isConnected() == false) // যখন গ্রাফ সংযুক্ত নয়
return 0;
vector<int> degree(NODE, 0);
int oddDegree = 0;
for(int i = 0; i < NODE; i++) {
for(int j = 0; j < NODE; j++) {
if(graph[i][j])
degree[i]++; // সংযুক্ত এজ পাওয়ার সময় ডিগ্রি বাড়ান
}
if(degree[i] % 2 != 0) // যখন ভার্টেক্সের ডিগ্রি বিজোড়
oddDegree++; // বিজোড় ডিগ্রির ভার্টেক্স গণনা করুন
}
if(oddDegree > 2) // যখন বিজোড় ডিগ্রির ভার্টেক্স ২-এর চেয়ে বেশি
return 0;
return (oddDegree) ? 1 : 2; // যখন oddDegree ০, তখন অয়লার সার্কিট, এবং ২ হলে অয়লার পথ
}
int main() {
int check;
check = isEulerian();
switch(check) {
case 0: cout << "The graph is not an Eulerian graph."; break;
case 1: cout << "The graph has an Eulerian path."; break;
case 2: cout << "The graph has a Eulerian circuit."; break;
}
}
আউটপুট
The graph has an Eulerian path.
