यूलर पथ एक पथ है; जिससे हम हर किनारे पर ठीक एक बार जा सकते हैं। हम एक ही कोने को कई बार इस्तेमाल कर सकते हैं। इस मामले में यूलर सर्किट वाले एक ग्राफ पर भी विचार किया जाता है, क्योंकि इसमें यूलर पथ भी होता है।
यह जांचने के लिए कि एक निर्देशित ग्राफ में यूलर पथ है या नहीं, हमें इन शर्तों की जांच करनी होगी -
- एक एकल शीर्ष होना चाहिए an जहां (इन-डिग्री + 1 =आउट_डिग्री)
- एक सिंगल वर्टेक्स होना चाहिए bn जहां (इन-डिग्री =आउट_डिग्री + 1)
- बाकी सभी शीर्षों में (इन-डिग्री =आउट_डिग्री) होता है यदि इनमें से कोई भी स्थिति विफल हो जाती है, तो ग्राफ़ में कोई यूलर पथ नहीं होता है।
वर्टेक्स बी में (इन-डिग्री 1, आउट-डिग्री 2), वर्टेक्स सी में (इन-डिग्री 2, आउट-डिग्री 1) है। और बाकी शीर्षों के लिए a, d में (इन-डिग्री 2, आउट-डिग्री 2), e के पास (इन-डिग्री 1, आउट-डिग्री 1) है।
इनपुट
ग्राफ़ का आसन्नता मैट्रिक्स।
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
आउटपुट
यूलर पथ मिला।
एल्गोरिदम
ट्रैवर्स(यू, विजिट किया गया)
इनपुट प्रारंभ नोड u और विज़िट किए गए नोड को चिह्नित करने के लिए कि किस नोड का दौरा किया गया है।
आउटपुट सभी जुड़े हुए शीर्षों को पार करता है।
Begin mark u as visited for all vertex v, if it is adjacent with u, do if v is not visited, then traverse(v, visited) done End
कनेक्टेड है(ग्राफ)
इनपुट :ग्राफ़।
आउटपुट:ग्राफ़ कनेक्ट होने पर सही है।
Begin define visited array for all vertices u in the graph, do make all nodes unvisited traverse(u, visited) if any unvisited node is still remaining, then return false done return true End
hasEulerPath(ग्राफ)
दिए गए ग्राफ़ को इनपुट करें।
आउटपुट सही है जब एक यूलर सर्किट पाया जाता है।
Begin an := 0 bn := 0 if isConnected() is false, then return false define list for inward and outward edge count for each node for all vertex i in the graph, do sum := 0 for all vertex j which are connected with i, do inward edges for vertex i increased increase sum done number of outward of vertex i is sum done if inward list and outward list are same, then return true for all vertex i in the vertex set V, do if inward[i] ≠ outward[i], then if inward[i] + 1 = outward[i], then an := an + 1 else if inward[i] = outward[i] + 1, then bn := bn + 1 done if an and bn both are 1, then return true otherwise return false End
उदाहरण कोड
#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 0, 1, 1, 0},
{1, 0, 1, 0, 0},
{0, 0, 0, 1, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 0, 0}};
void traverse(int u, bool visited[]) {
visited[u] = true; //mark v as visited
for(int v = 0; v<NODE; v++) {
if(graph[u][v]) {
if(!visited[v])
traverse(v, visited);
}
}
}
bool isConnected() {
bool *vis = new bool[NODE];
//for all vertex u as start point, check whether all nodes are visible or not
for(int u; u < NODE; u++) {
for(int i = 0; i<NODE; i++)
vis[i] = false; //initialize as no node is visited
traverse(u, vis);
for(int i = 0; i<NODE; i++) {
if(!vis[i]) //if there is a node, not visited by traversal, graph is not connected
return false;
}
}
return true;
}
bool hasEulerPath() {
int an = 0, bn = 0;
if(isConnected() == false){ //when graph is not connected
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]++; //increase inward edge for destination vertex
sum++; //how many outward edge
}
}
outward[i] = sum;
}
//check the condition for Euler paths
if(inward == outward) //when number inward edges and outward edges for each node is same
return true; //Euler Circuit, it has Euler path
for(int i = 0; i<NODE; i++) {
if(inward[i] != outward[i]) {
if((inward[i] + 1 == outward[i])) {
an++;
} else if((inward[i] == outward[i] + 1)) {
bn++;
}
}
}
if(an == 1 && bn == 1) { //if there is only an, and bn, then this has euler path
return true;
}
return false;
}
int main() {
if(hasEulerPath())
cout << "Euler Path Found.";
else
cout << "There is no Euler Circuit.";
} आउटपुट
Euler Path Found.