मान लीजिए हमारे पास एक पूरा ग्राफ है; हमें एज डिसजॉइंट स्पैनिंग ट्री की संख्या गिननी है। एज डिसजॉइंट स्पैनिंग पेड़ फैले हुए पेड़ हैं, जहां सेट में कोई भी दो पेड़ आम तौर पर किनारे नहीं होते हैं। मान लीजिए कि N (शीर्षों की संख्या) 4 है, तो आउटपुट 2 होगा। 4 शीर्षों का उपयोग करने वाला पूरा ग्राफ नीचे जैसा है -
दो किनारे असंबद्ध फैले हुए पेड़ जैसे होते हैं -
N शीर्षों के साथ एक पूर्ण ग्राफ़ से किनारे के असंबद्ध फैले हुए वृक्षों की अधिकतम संख्या $[\frac{n}{2}]$
होगीउदाहरण
#include <iostream>
#include <cmath>
using namespace std;
int maxEdgeDisjointSpanningTree(int n){
return floor(n/2);
}
int main() {
int n = 4;
cout << "Maximum Edge Disjoint Spanning Tree: " <<
maxEdgeDisjointSpanningTree(n);
} आउटपुट
Maximum Edge Disjoint Spanning Tree: 2