यूलर चक्र/सर्किट एक पथ है; जिसके द्वारा हम प्रत्येक एज को ठीक एक बार देख सकते हैं। हम एक ही वर्टेक्स का कई बार उपयोग कर सकते हैं। यूलर सर्किट यूलर पथ का एक विशेष प्रकार है। जब यूलर पथ का प्रारंभिक वर्टेक्स उस पथ के अंतिम वर्टेक्स से भी जुड़ा होता है, तो इसे यूलर सर्किट कहा जाता है।

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