यूलर पथ एक पथ है, जिसके द्वारा हम प्रत्येक किनारे को ठीक एक बार देख सकते हैं। हम एक ही शीर्षों का कई बार उपयोग कर सकते हैं। यूलर सर्किट यूलर पथ का एक विशेष प्रकार है। जब यूलर पथ का प्रारंभिक शीर्ष उस पथ के अंतिम शीर्ष से भी जुड़ा होता है, तो इसे यूलर सर्किट कहा जाता है।
पथ और सर्किट का पता लगाने के लिए, हमें इन शर्तों का पालन करना होगा -
- ग्राफ जुड़ा हुआ होना चाहिए।
- जब ठीक दो शीर्षों की डिग्री विषम हो, तो यह एक यूलर पथ है।
- अब जब एक अनिर्देशित ग्राफ के किसी भी शीर्ष की डिग्री विषम नहीं है, तो यह एक यूलर सर्किट है।
इनपुट और आउटपुट
इनपुट: एक ग्राफ का आसन्नता मैट्रिक्स। 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)
इनपुट: ग्राफ।
आउटपुट: ग्राफ जुड़ा हुआ है तो सच।
शुरू देखी गई सरणी परिभाषित करें ग्राफ में सभी शीर्ष u के लिए, करें सभी नोड्स को अनदेखा करें traverse(u, visited) यदि कोई अनदेखा नोड अभी भी शेष है, तो वापस करें गलत किया वापस करें सच अंत
isEulerian(Graph)
इनपुट: दिया गया ग्राफ।
आउटपुट: 0 वापस करता है जब यूलरियन नहीं, 1 जब यूलर पथ हो, 2 जब यूलर सर्किट मिला।
शुरू यदि isConnected() गलत है, तो वापस करें गलत प्रत्येक नोड के लिए डिग्री की सूची परिभाषित करें oddDegree := 0 ग्राफ में सभी शीर्ष i के लिए, करें i के साथ जुड़े सभी शीर्ष j के लिए, करें डिग्री बढ़ाएं किया यदि शीर्ष i की डिग्री विषम है, तो oddDegree बढ़ाएं किया यदि oddDegree > 2, तो वापस करें 0 यदि oddDegree = 0, तो वापस करें 2 अन्यथा वापस करें 1 अंत
उदाहरण
#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} }; /* int graph[NODE][NODE] = { {0, 1, 1, 1, 1}, {1, 0, 1, 0, 0}, {1, 1, 0, 0, 0}, {1, 0, 0, 0, 1}, {1, 0, 0, 1, 0} }; */ //यूलर सर्किट जांचने के लिए अनकमेंट करें /* int graph[NODE][NODE] = { {0, 1, 1, 1, 0}, {1, 0, 1, 1, 0}, {1, 1, 0, 0, 0}, {1, 1, 0, 0, 1}, {0, 0, 0, 1, 0} }; */ //गैर-यूलरियन ग्राफ जांचने के लिए अनकमेंट करें void traverse(int u, bool visited[]) { visited[u] = true; //v को देखा गया चिह्नित करें for(int v = 0; v 2) //जब विषम डिग्री वाले शीर्ष 2 से अधिक हों return 0; return (oddDegree)?1:2; //जब oddDegree 0 हो, तो यह यूलर सर्किट है, और जब 2 हो, तो यह यूलर पथ है } 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.
