C++ में यूलर सर्किट बनाने के लिए आवश्यक न्यूनतम किनारे

अवधारणा

दिए गए b नोड्स और a किनारों वाले एक अप्रत्यक्ष ग्राफ के संबंध में, कार्य दिए गए ग्राफ में यूलर सर्किट बनाने के लिए आवश्यक न्यूनतम किनारों को निर्धारित करना है।

उदाहरण

इनपुट

b = 3, a = 2 Edges[] = {{1, 2}, {2, 3}}

आउटपुट

1

1 को 3 से जोड़कर, हम एक यूलर सर्किट बना सकते हैं।

विधि

ग्राफ में यूलर सर्किट के अस्तित्व के लिए हमें आवश्यकता है कि प्रत्येक नोड की डिग्री सम हो क्योंकि तब एक किनारा मौजूद होता है जिसका उपयोग नोड में प्रवेश करने के बाद बाहर निकलने के लिए किया जा सकता है।

अब, दो मामले हो सकते हैं:

ग्राफ में एक जुड़ा हुआ घटक

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

ग्राफ में असंबद्ध घटक

सबसे पहले हम घटक को विषम और सम के रूप में चिह्नित करते हैं। विषम घटक वे हैं जिनमें कम से कम एक विषम डिग्री नोड होता है। अब हम सभी सम घटकों को लेते हैं और प्रत्येक घटक से एक यादृच्छिक शीर्ष चुनते हैं और उन्हें रैखिक रूप से व्यवस्थित करते हैं। आसन्न शीर्षों के बीच एक किनारा जोड़कर, हमने सम घटकों को जोड़ा है और एक समकक्ष विषम घटक बनाया है जिसमें विषम डिग्री वाले दो नोड्स हैं।

परिणामस्वरूप, विषम घटकों से निपटने के लिए यानी कम से कम एक विषम डिग्री नोड वाले घटक, हम इन सभी विषम घटकों को किनारों का उपयोग करके जोड़ सकते हैं जिनकी संख्या असंबद्ध घटकों की संख्या के बराबर है। इसे घटकों को चक्रीय क्रम में रखकर और प्रत्येक घटक से दो विषम डिग्री नोड्स चुनकर और इनका उपयोग दोनों तरफ के घटकों से जोड़कर पूरा किया जा सकता है। अब हमारे पास एक एकल जुड़ा हुआ घटक है जिसके लिए हमने ऊपर चर्चा की है।

C++ कार्यान्वयन

// C++ program to find minimum edge required to make Euler Circuit
#include <bits/stdc++.h>
using namespace std;

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);
}

int minEdge1(int n, int m, int s1[], int d1[]){
    vector<int> g1[n+1], e1, o1;
    int deg1[n+1];
    int vis1[n+1];
    int odd1[n+1];
    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]]++;
    }
    int ans = 0, comp = 0;
    for (int i = 1; i <= n; i++){
        if (vis1[i]==0){
            comp++;
            dfs1(g1, vis1, odd1, deg1, comp, i);
            if (odd1[comp] == 0)
                e1.push_back(comp);
            else
                o1.push_back(comp);
        }
    }
    if (o1.size() == 0 && e1.size() == 1)
        return 0;
    if (o1.size() == 0)
        return e1.size();
    if (e1.size() != 0)
        ans += e1.size();
    for (int i : o1)
        ans += odd1[i]/2;
    return ans;
}

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