অয়লার পথ হলো এমন একটি পথ, যার মাধ্যমে আমরা প্রতিটি এজকে ঠিক একবার দিয়ে যেতে পারি। আমরা একই ভার্টেক্সগুলোকে একাধিকবার ব্যবহার করতে পারি। অয়লার সার্কিট হলো অয়লার পথের একটি বিশেষ ধরন। যখন অয়লার পথের শুরুর ভার্টেক্স সেই পথের শেষ ভার্টেক্সের সাথে সংযুক্ত থাকে, তখন তাকে অয়লার সার্কিট বলা হয়।
একটি গ্রাফ অয়লারিয়ান কিনা তা যাচাই করতে দুটি শর্ত পরীক্ষা করতে হয় −
- গ্রাফটি সংযুক্ত (connected) হতে হবে।
- প্রতিটি ভার্টেক্সের ইন-ডিগ্রি এবং আউট-ডিগ্রি একই হতে হবে।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স। 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 আউটপুট: অয়লার সার্কিট পাওয়া গেছে।
এলগরিদম
traverse(u, visited)
ইনপুট: শুরুর নোড u এবং ভিজিটেড নোড যাতে বুঝতে পারা যায় কোন নোড ভিজিটেড।
আউটপুট: সব সংযুক্ত ভার্টেক্স ট্রাভার্স করুন।
শুরু
u কে ভিজিটেড চিহ্নিত করুন
u-র সাথে সন্নিহিত সব ভার্টেক্স v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
traverse(v, visited)
শেষ লুপ
শেষ
isConnected(graph)
ইনপুট: গ্রাফ।
আউটপুট: গ্রাফ সংযুক্ত থাকলে true।
শুরু
ভিজিটেড অ্যারে সংজ্ঞায়িত করুন
গ্রাফের সব ভার্টেক্স u এর জন্য, করুন
সব নোডকে অনভিজিটেড করুন
traverse(u, visited)
যদি কোনো অনভিজিটেড নোড অবশিষ্ট থাকে, তবে
return false
শেষ লুপ
return true
শেষ
isEulerCircuit(Graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: একটি অয়লার সার্কিট পাওয়া গেলে true।
শুরু
যদি isConnected() false হয়, তবে
return false
প্রতিটি নোডের ইনওয়ার্ড এবং আউটওয়ার্ড এজ কাউন্টের একটি লিস্ট সংজ্ঞায়িত করুন
গ্রাফের সব ভার্টেক্স i এর জন্য, করুন
sum := 0
i-র সাথে সংযুক্ত সব ভার্টেক্স j এর জন্য, করুন
ভার্টেক্স i-এর ইনওয়ার্ড এজ বাড়ান
sum বাড়ান
শেষ লুপ
ভার্টেক্স i-এর আউটওয়ার্ডের সংখ্যা হলো sum
শেষ লুপ
যদি ইনওয়ার্ড লিস্ট এবং আউটওয়ার্ড লিস্ট একই হয়, তবে
return true
অন্যথায় return false
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 0, 1, 0, 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;
}
bool isEulerCircuit() {
if(isConnected() == false) {
// যখন গ্রাফ সংযুক্ত নয়
return false;
}
vector<int> inward(NODE, 0), outward(NODE, 0);
for(int i = 0; i < NODE; i++) {
int sum = 0;
for(int j = 0; j < NODE; j++) {
if(graph[i][j]) {
inward[j]++; // গন্তব্য ভার্টেক্সের ইনওয়ার্ড এজ বাড়ান
sum++; // কতগুলো আউটওয়ার্ড এজ
}
}
outward[i] = sum;
}
if(inward == outward) // যখন প্রতিটি নোডের ইনওয়ার্ড এবং আউটওয়ার্ড এজের সংখ্যা একই
return true;
return false;
}
int main() {
if(isEulerCircuit())
cout << "Euler Circuit Found.";
else
cout << "There is no Euler Circuit.";
}
আউটপুট
Euler Circuit Found.
