C++ এ অয়লার সার্কিট তৈরি করতে ন্যূনতম প্রান্ত যোগ করতে হবে

ধারণা

বি নোড এবং একটি প্রান্তগুলির একটি প্রদত্ত অনির্দেশিত গ্রাফের ক্ষেত্রে, কাজটি হল প্রদত্ত গ্রাফে অয়লার সার্কিট তৈরির জন্য প্রয়োজনীয় ন্যূনতম প্রান্তগুলি নির্ধারণ করা৷

ইনপুট

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

আউটপুট

C++ এ অয়লার সার্কিট তৈরি করতে ন্যূনতম প্রান্ত যোগ করতে হবে

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