यूलर पथ एक पथ है, जिसके द्वारा हम प्रत्येक किनारे को ठीक एक बार देख सकते हैं। हम एक ही शीर्षों का कई बार उपयोग कर सकते हैं। यूलर सर्किट यूलर पथ का एक विशेष प्रकार है। जब यूलर पथ का प्रारंभिक शीर्ष उस पथ के अंतिम शीर्ष से भी जुड़ा होता है, तो इसे यूलर सर्किट कहा जाता है।
यह जांचने के लिए कि कोई ग्राफ यूलरियन है या नहीं, हमें दो शर्तों की जांच करनी होगी -
- ग्राफ जुड़ा हुआ होना चाहिए।
- प्रत्येक शीर्ष की इन-डिग्री और आउट-डिग्री समान होनी चाहिए।
इनपुट और आउटपुट
इनपुट: ग्राफ का आसन्नता मैट्रिक्स। 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)
इनपुट: ग्राफ।
आउटपुट: ग्राफ जुड़ा हुआ है तो सच।
शुरू देखी गई सरणी परिभाषित करें ग्राफ में सभी शीर्ष u के लिए, करें सभी नोड्स को अनदेखा करें traverse(u, visited) यदि कोई अनदेखा नोड अभी भी शेष है, तो वापस करें गलत किया वापस करें सच अंत
isEulerCircuit(Graph)
इनपुट: दिया गया ग्राफ।
आउटपुट: जब एक यूलर सर्किट मिला तो सच।
शुरू यदि isConnected() गलत है, तो वापस करें गलत प्रत्येक नोड के लिए आवक और जावक किनारे गिनती की सूची परिभाषित करें ग्राफ में सभी शीर्ष i के लिए, करें sum := 0 i के साथ जुड़े सभी शीर्ष j के लिए, करें शीर्ष i के लिए आवक किनारे बढ़ाएं sum बढ़ाएं किया शीर्ष i की जावक संख्या sum है किया यदि आवक सूची और जावक सूची समान हैं, तो वापस करें सच अन्यथा गलत वापस करें अंत
उदाहरण
#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
आउटपुट
Euler Circuit Found.
