सी ++ में ग्राफ में अधिकतम और न्यूनतम पृथक शिखर

हमें किनारों की संख्या Noe और शीर्षों की संख्या नवंबर दी गई है। लक्ष्य ऐसे ग्राफ़ में संभव न्यूनतम और अधिकतम अलग-अलग शीर्षों को खोजना है, जिनमें कोई किनारा नहीं है और कोई शीर्ष नहीं है।

एक पृथक शीर्ष वह है जिसका कोई किनारा नहीं जुड़ा है।

• न्यूनतम पृथक शीर्षों के लिए

हम यह सुनिश्चित करेंगे कि हर किनारा अलग-थलग हो। (किसी भी दो किनारों के समान शीर्ष नहीं होते हैं) प्रत्येक किनारे के लिए केवल 2 शीर्षों की आवश्यकता होती है। तो ,

गैर पृथक शीर्षों की संख्या =2 * नहीं। किनारों के

अलग-अलग शीर्षों की संख्या =कुल शीर्ष - गैर पृथक शीर्षों की संख्या।

यदि नं. शीर्षों का <=2 * नहीं है। किनारों का, इसका मतलब है कि सभी कोने में एक किनारा जुड़ा हुआ है। तो नहीं। अलग-अलग शीर्षों की संख्या 0 है।

• अधिकतम पृथक शीर्षों के लिए

इसके लिए हम एक ऐसा बहुभुज बनाने का प्रयास करेंगे जिससे सभी किनारे न्यूनतम शीर्षों से जुड़े हों। यह तब संभव है जब हमारे पास एक ऐसा बहुभुज हो जिसमें प्रत्येक शीर्ष युग्म के बीच विकर्ण भी हों।

दिए गए 5 शीर्षों और 6 किनारों के लिए, वर्ग वह बहुभुज है जिसमें 2 विकर्णों के साथ 6 किनारे होते हैं ताकि केवल 4 कोने लगे हों। 1 शीर्ष अलग हो जाता है और यह अधिकतम होता है।

n भुजा वाले बहुभुज में एक शीर्ष से दूसरे शीर्ष पर विकर्णों की संख्या n*(n-3)/2 है। कुल किनारे=n*(n-1)/2

इनपुट

No. of vertices 5, edges 6

आउटपुट

Minimum isolated vertices 0. Maximum isolated vertices 1.

स्पष्टीकरण

जैसा कि ऊपर चित्र में दिखाया गया है।

इनपुट - नहीं। शीर्षों का 2, किनारा=1

आउटपुट - न्यूनतम पृथक शीर्ष 0. अधिकतम पृथक शीर्ष 0.

स्पष्टीकरण − कम से कम दो शीर्षों के बीच एक किनारा बनता है।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

• पूर्णांक noe और nov में संख्या होती है। किनारों और शीर्षों का।

• फ़ंक्शन अलग-अलग कोने ढूंढता है (इंट वी, इंट ई) किनारों और कोने को पैरामीटर के रूप में लेता है और न्यूनतम और अधिकतम अलग-अलग कोने संभव प्रिंट करता है।

• अगर नहीं। शीर्षों का <=2*e है, अर्थात कोई पृथक शीर्ष नहीं है। अन्य गैर-पृथक शीर्ष 2*e(अधिकतम) हैं, इसलिए न्यूनतम विलगित शीर्ष v-2*e होगा।

• अधिकतम पृथक शीर्षों की गणना के लिए, i=1 से शुरू होकर नहीं तक। शीर्षों का, यदि (i * (i - 1) / 2>=e) टूटता है क्योंकि केवल i शीर्ष ही e किनारों के लिए पर्याप्त हैं।

• मैं अधिकतम संभव पृथक शीर्षों को संग्रहीत करता हूं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void findisolatedvertices(int v, int e){
   //one edge has 2 vertices
   if (v <= 2 * e) //means all veritces have a connected edge
      cout << "Minimum no. of isolated vertices: " << 0 << endl;
   else {
      int niso=2*e; //maximum non isolated vertices
      cout << "Minimum no. of isolated vertices: " << v - niso << endl;
   }
   // To find out maximum number of isolated
   // vertices
   // Loop to find out value of number of
   // vertices that are connected
   int i;
   for (i = 1; i <= v; i++) {
      if (i * (i - 1) / 2 >= e)
         break;
   }
   cout <<endl<< "Maximum no. of isolated vertices: " <<v-i;
}
int main(){
   // Number of vertices
   int nov = 5;
   // Number of edges
   int noe = 2;
   // Calling the function to maximum and
   // minimum number of isolated vertices
   findisolatedvertices(nov, noe);
   return 0;
}

आउटपुट

Minimum no. of isolated vertices: 1
Maximum no. of isolated vertices: 2