अवधारणा
बी नोड्स और किनारों के दिए गए अप्रत्यक्ष ग्राफ के संबंध में, काम दिए गए ग्राफ में यूलर सर्किट बनाने के लिए आवश्यक न्यूनतम किनारों को निर्धारित करना है।
इनपुट
b = 3,
a = 2
Edges[] = {{1, 2}, {2, 3}} आउटपुट
1
1 से 3 को जोड़कर हम एक यूलर सर्किट बना सकते हैं।
विधि
ग्राफ में मौजूद होने के लिए एक यूलर सर्किट के संबंध में हमें यह चाहिए कि प्रत्येक नोड में सम डिग्री होनी चाहिए क्योंकि तब एक किनारा मौजूद होता है जिसे नोड में प्रवेश करने के बाद बाहर निकलने के लिए लागू किया जा सकता है।
अब, दो मामले हो सकते हैं -
ग्राफ़ में एक कनेक्टेड घटक का अस्तित्व
इस मामले के संबंध में, यदि ग्राफ में सभी नोड्स सम डिग्री से लैस हैं तो हम कहते हैं कि ग्राफ में पहले से ही एक यूलर सर्किट है और हमें इसमें कोई किनारा जोड़ने की आवश्यकता नहीं है। लेकिन अगर विषम डिग्री से लैस कोई नोड है तो हमें किनारों को जोड़ने की आवश्यकता होती है। ग्राफ में विषम डिग्री शिखर की संख्या भी मौजूद हो सकती है। इस घटना को इस तथ्य से आसानी से सत्यापित किया जा सकता है कि सम डिग्री नोड से डिग्री का योग और विषम डिग्री नोड से डिग्री का योग कुल डिग्री से मेल खाना चाहिए जो हमेशा सम होता है क्योंकि हर किनारे इस योग में दो योगदान देता है। इसके परिणामस्वरूप, यदि हम ग्राफ़ में यादृच्छिक विषम डिग्री नोड्स को जोड़ते हैं और उनके बीच एक किनारा जोड़ते हैं तो हम सभी नोड्स को सम डिग्री के लिए बना सकते हैं और इस प्रकार एक यूलर सर्किट का निर्माण कर सकते हैं।
ग्राफ़ में डिस्कनेक्ट किए गए घटकों का अस्तित्व
सबसे पहले हम घटक को विषम और सम के रूप में चिह्नित करते हैं। विषम घटक वे होते हैं जिनमें न्यूनतम एक विषम डिग्री नोड होता है। अब हम सभी सम घटकों को लेते हैं और प्रत्येक घटक से एक यादृच्छिक शीर्ष चुनते हैं और उन्हें रैखिक रूप से व्यवस्थित करते हैं। इसलिए आसन्न कोने के बीच एक किनारे को जोड़ते हुए, हमने सम घटकों को जोड़ा है और एक समान विषम घटक बनाया है जिसमें विषम डिग्री के साथ दो नोड हैं।
इसके परिणामस्वरूप, विषम घटकों यानी न्यूनतम एक विषम डिग्री नोड वाले घटकों से निपटने के लिए, हम किनारों को लागू करने वाले इन सभी विषम घटकों को जोड़ सकते हैं जिनकी संख्या डिस्कनेक्ट किए गए घटकों की संख्या के बराबर है। यह घटकों को चक्रीय क्रम में रखकर और प्रत्येक घटक से दो विषम डिग्री नोड्स का चयन करके और दोनों तरफ घटकों से जुड़ने के लिए इन्हें लागू करके पूरा किया जा सकता है। अब हमारे पास एक ही जुड़ा हुआ घटक है जिसके लिए हमने समझाया है।
उदाहरण
//This C++ program finds minimum edge required
// to make Euler Circuit
#include <bits/stdc++.h>
using namespace std;
// This Depth-First Search finds a connected
// component
void dfs1(vector<int> g1[], int vis1[], int odd1[],
int deg1[], int comp, int v){
vis1[v] = 1;
if (deg1[v]%2 == 1)
odd1[comp]++;
for (int u : g1[v])
if (vis1[u] == 0)
dfs1(g1, vis1, odd1, deg1, comp, u);
}
// We return minimum edge required to build Euler
// Circuit
int minEdge1(int n, int m, int s1[], int d1[]){
// g1 : to store adjacency list
// representation of graph.
// e1 : to store list of even degree vertices
// o1 : to store list of odd degree vertices
vector<int> g1[n+1], e1, o1;
int deg1[n+1]; // Degrees of vertices used
int vis1[n+1]; // To store visited in DFS
int odd1[n+1]; // Number of odd nodes in components
memset(deg1, 0, sizeof(deg1));
memset(vis1, 0, sizeof(vis1));
memset(odd1, 0, sizeof(odd1));
for (int i = 0; i < m; i++){
g1[s1[i]].push_back(d1[i]);
g1[d1[i]].push_back(s1[i]);
deg1[s1[i]]++;
deg1[d1[i]]++;
}
// This 'ans' is result and 'comp' is component id
int ans = 0, comp = 0;
for (int i = 1; i <= n; i++){
if (vis1[i]==0){
comp++;
dfs1(g1, vis1, odd1, deg1, comp, i);
// We check that if connected component
// is odd.
if (odd1[comp] == 0)
e1.push_back(comp);
// We check that if connected component
// is even.
else
o1.push_back(comp);
}
}
// It has been seen that if whole graph is a single connected
// component with even degree.
if (o1.size() == 0 && e1.size() == 1)
return 0;
// It has been seen that if all connected component is even
if (o1.size() == 0)
return e1.size();
//It has been seen that if graph have atleast one even connected
// component
if (e1.size() != 0)
ans += e1.size();
// For all the odd connected component.
for (int i : o1)
ans += odd1[i]/2;
return ans;
}
// Driven Program
int main(){
int b = 3, a = 2;
int source1[] = { 1, 2 };
int destination1[] = { 2, 3 };
cout << minEdge1(b, a, source1, destination1) << endl;
return 0;
} आउटपुट
1