हमें किनारों की संख्या Noe और शीर्षों की संख्या Nov दी गई है। लक्ष्य ऐसे ग्राफ में संभव न्यूनतम और अधिकतम पृथक शीर्षों की संख्या ढूंढना है जिनमें कोई किनारे नहीं हैं और शीर्षों की संख्या Nov है।
एक पृथक शीर्ष वह है जिससे कोई किनारा जुड़ा नहीं है।
- न्यूनतम पृथक शीर्षों के लिए
हम यह सुनिश्चित करेंगे कि हर किनारा पृथक हो। (कोई दो किनारे सामान्य शीर्ष साझा नहीं करते) प्रत्येक किनारे को केवल 2 शीर्षों की आवश्यकता होती है। इसलिए,
गैर-पृथक शीर्षों की संख्या = 2 * किनारों की संख्या
पृथक शीर्षों की संख्या = कुल शीर्ष - गैर-पृथक शीर्षों की संख्या।
यदि शीर्षों की संख्या <= 2 * किनारों की संख्या है, तो सभी शीर्षों से एक किनारा जुड़ा है। इसलिए पृथक शीर्षों की संख्या 0 है।
- अधिकतम पृथक शीर्षों के लिए
इसके लिए हम एक बहुभुज बनाने की कोशिश करेंगे जिससे सभी किनारे न्यूनतम शीर्षों से जुड़े हों। यह तब संभव है जब हमारे पास एक बहुभुज हो जहां प्रत्येक शीर्ष जोड़ी के बीच विकर्ण भी हो।
दिए गए 5 शीर्षों और 6 किनारों के लिए, वर्ग वह बहुभुज है जिसमें 2 विकर्णों के साथ 6 किनारे हैं ताकि केवल 4 शीर्ष घिरे हों। 1 शीर्ष पृथक हो जाता है और यह अधिकतम है।
एक शीर्ष से दूसरे शीर्ष तक n भुजाओं वाले बहुभुज में विकर्णों की संख्या n*(n-3)/2 है। कुल किनारे = n*(n-1)/2
इनपुट
शीर्षों की संख्या 5, किनारे 6
आउटपुट
न्यूनतम पृथक शीर्ष 0। अधिकतम पृथक शीर्ष 1।
व्याख्या
ऊपर दिए गए चित्र में दिखाया गया है।
इनपुट: शीर्षों की संख्या 2, किनारे=1
आउटपुट: न्यूनतम पृथक शीर्ष 0। अधिकतम पृथक शीर्ष 0।
व्याख्या: एक किनारा कम से कम दो शीर्षों के बीच बनता है।
प्रयुक्त दृष्टिकोण
- पूर्णांक noe और nov में किनारों और शीर्षों की संख्या होती है।
- फ़ंक्शन findisolatedvertices(int v, int e) किनारों और शीर्षों को पैरामीटर के रूप में लेता है और संभावित न्यूनतम और अधिकतम पृथक शीर्षों को प्रिंट करता है।
- यदि शीर्षों की संख्या <= 2*e है, तो कोई पृथक शीर्ष नहीं। अन्यथा गैर-पृथक शीर्ष 2*e हैं (अधिकतम), इसलिए न्यूनतम पृथक v-2*e होंगे।
- अधिकतम पृथक शीर्षों की गणना के लिए, i=1 से शीर्षों की संख्या तक शुरू करें, यदि (i * (i - 1) / 2 >= e) तो ब्रेक करें क्योंकि केवल i शीर्ष e किनारों के लिए पर्याप्त हैं।
- i संभावित अधिकतम पृथक शीर्षों को संग्रहीत करता है।
उदाहरण कोड
#include <bits/stdc++.h> using namespace std; void findisolatedvertices(int v, int e){ //एक किनारे में 2 शीर्ष होते हैं if (v <= 2 * e) //मतलब सभी शीर्षों से एक जुड़ा हुआ किनारा है cout << "न्यूनतम पृथक शीर्षों की संख्या: " << 0 << endl; else { int niso=2*e; //अधिकतम गैर-पृथक शीर्ष cout << "न्यूनतम पृथक शीर्षों की संख्या: " << v - niso << endl; } // अधिकतम पृथक शीर्षों का पता लगाने के लिए // लूप जुड़े हुए शीर्षों की संख्या का मान खोजने के लिए int i; for (i = 1; i <= v; i++) { if (i * (i - 1) / 2 >= e) break; } cout <<endl<< "अधिकतम पृथक शीर्षों की संख्या: " <<v-i; } int main(){ // शीर्षों की संख्या int nov = 5; // किनारों की संख्या int noe = 2; // अधिकतम और न्यूनतम पृथक शीर्षों की संख्या के लिए फ़ंक्शन कॉल findisolatedvertices(nov, noe); return 0; } आउटपुट
न्यूनतम पृथक शीर्षों की संख्या: 1 अधिकतम पृथक शीर्षों की संख्या: 2
