C++ में द्विभाजित ग्राफ में अधिकतम एज की संख्या

समस्या कथन

एक पूर्णांक N दिया गया है जो शीर्षों की संख्या दर्शाता है। कार्य N शीर्षों के द्विभाजित ग्राफ में संभव अधिकतम एज की संख्या ढूंढना है।

द्विभाजित ग्राफ

• एक द्विभाजित ग्राफ वह है जिसमें शीर्षों के 2 सेट होते हैं।
• सेट ऐसे होते हैं कि एक ही सेट के शीर्ष कभी भी उनके बीच एज साझा नहीं करेंगे।

उदाहरण

यदि N = 10 तो कुल 25 एज होंगे -

• दोनों सेट में 5 शीर्ष होंगे और पहले सेट का प्रत्येक शीर्ष दूसरे सेट के हर दूसरे शीर्ष से जुड़ा होगा
• इसलिए कुल एज 5 * 5 = 25 होंगे

एल्गोरिदम

• एज की संख्या अधिकतम होगी जब किसी दिए गए सेट का प्रत्येक शीर्ष दूसरे सेट के हर दूसरे शीर्ष से जुड़ा हो यानी एज = m * n जहां m और n दोनों सेट में एज की संख्या हैं
• एज की संख्या को अधिकतम करने के लिए, m, n के बराबर या जितना संभव हो उतना करीब होना चाहिए
• इसलिए, अधिकतम एज की संख्या निम्न सूत्र से निकाली जा सकती है -

(n * 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