ধরুন আমাদের একটি কমপ্লিট গ্রাফ আছে; আমাদের এজ-ডিজয়েন্ট স্প্যানিং ট্রির সংখ্যা গণনা করতে হবে। এজ-ডিজয়েন্ট স্প্যানিং ট্রি হলো স্প্যানিং ট্রিগুলোর সেট যেখানে কোনো দুটি ট্রির কোনও কমন এজ নেই। ধরুন N (ভার্টেক্স সংখ্যা) = 4, তবে আউটপুট ২। ৪ ভার্টেক্স দিয়ে কমপ্লিট গ্রাফ নিচের মত:
দুটি এজ-ডিজয়েন্ট স্প্যানিং ট্রি নিচের মত:
N ভার্টেক্স বিশিষ্ট কমপ্লিট গ্রাফ থেকে সর্বোচ্চ এজ-ডিজয়েন্ট স্প্যানিং ট্রির সংখ্যা হবে ⌊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
