नोड्स की संख्या को अधिकतम करें जो सी ++ में ग्राफ़ में किसी भी किनारे का हिस्सा नहीं हैं

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

हम एक पूरा ग्राफ बनाने की कोशिश करके ऐसा करेंगे जहां नोड्स की संख्या n है तो वहां n(n-1)/2 किनारे होंगे।

edge=n(n-1)/2 (यहां n नोड्स के लिए)

2*किनारे=n(n-1). एक बार n(n-1)> नहीं। किनारों के तो हमारे पास अतिरिक्त नोड हैं। इसलिए i=1 से i=n तक पुनरावृति करें।

i(i-1)>2*किनारे तक। परिणाम के रूप में n-i लौटें।

आइए उदाहरणों से समझते हैं -

इनपुट -नोड्स=5, किनारों=2

आउटपुट - नोड्स की अधिकतम संख्या जो ग्राफ़ में किसी भी किनारे का हिस्सा नहीं हैं - 2

स्पष्टीकरण -

2 किनारों में न्यूनतम 3 नोड और अधिकतम 4 नोड हो सकते हैं।

3 नोड्स के लिए बिना किसी किनारे के अधिकतम बाएं नोड्स=2

इनपुट -नोड्स=2, किनारों=1

आउटपुट - नोड्स की अधिकतम संख्या जो ग्राफ़ में किसी भी किनारे का हिस्सा नहीं हैं - 0

स्पष्टीकरण -

किनारे बनाने के लिए कम से कम 2 नोड्स की आवश्यकता होती है। इस मामले में दोनों का कब्जा है। कोई नोड नहीं बचा है।

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

• हम उपलब्ध डेटा के लिए दो चर नोड्स और किनारों को लेते हैं।

• फंक्शन मैक्सिमम (इंट नोड्स, इंट एज) नहीं लेता है। नोड्स और किनारों के पैरामीटर के रूप में और अधिकतम नोड्स की गिनती देता है जो ग्राफ़ में किसी भी किनारे का हिस्सा नहीं हैं

• चर i, अस्थायी और अधिकतम लें।

• i=0 से i<=nodes

  . तक के लिए लूप प्रारंभ करें

• अस्थायी गणना करें=i*(i-1)

• चर कुल की गणना 2*किनारों के रूप में करें

• जब भी तापमान कुल से अधिक हो जाए, तो FOR

  . को तोड़ दें

• अधिकतम की गणना max=nodes-i

  . के रूप में करें

• परिणाम को अधिकतम के रूप में लौटाएं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int maximum(int nodes, int edges){
   int i, temp = 0, max;
   for (i = 0; i <= nodes; i++){
      temp = i * (i - 1);
      int total = 2* edges;
      if (temp >= total){
         break;
      }
   }
   max = nodes - i;
   return max;
}
int main(){
   int nodes = 10;
   int edges = 5;
   cout<<"Maximize number of nodes which are not part of any edge in a Graph are:"<<maximum(nodes, edges) << endl;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -

Maximize number of nodes which are not part of any edge in a Graph are: 6