समस्या कथन
एक पूर्णांक N दिया गया है जो शीर्षों की संख्या का प्रतिनिधित्व करता है। कार्य N शीर्षों के द्विदलीय ग्राफ़ में किनारों की अधिकतम संभव संख्या ज्ञात करना है।
द्विपक्षीय ग्राफ़
- द्विपक्षीय ग्राफ वह होता है जिसमें शीर्षों के 2 सेट होते हैं।
- सेट ऐसे होते हैं कि एक ही सेट के कोने कभी भी उनके बीच एक किनारा साझा नहीं करेंगे।
उदाहरण
यदि N =10 है तो कुल 25 किनारे होंगे -
- दोनों सेटों में 5 शीर्ष होंगे और पहले सेट के प्रत्येक शीर्ष का दूसरे सेट के प्रत्येक शीर्ष से किनारा होगा
- इसलिए कुल किनारे 5 * 5 =25 होंगे
एल्गोरिदम
- किनारों की संख्या तब अधिकतम होगी जब किसी दिए गए सेट के प्रत्येक शीर्ष का दूसरे सेट के हर दूसरे शीर्ष से एक किनारा होता है यानी किनारे =m * n जहां m और n दोनों सेटों में किनारों की संख्या होती है
- किनारों की संख्या को अधिकतम करने के लिए, m जितना संभव हो n के बराबर या उसके करीब होना चाहिए
- इसलिए, किनारों की अधिकतम संख्या की गणना सूत्र द्वारा की जा सकती है -
(एन * एन) / 4
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int getMaxEdges(int n) {
return floor((n * n) / 4);
}
int main() {
int n = 7;
cout << "Maximum edges = " << getMaxEdges(n) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Maximum edges = 12