ขอบที่เป็นไปได้สูงสุด Disjoint Spanning Tree จากกราฟที่สมบูรณ์ใน C++

สมมติว่าเรามีกราฟที่สมบูรณ์ เราต้องนับจำนวนต้น Edge Disjoint Spanning Edge Disjoint Spanning tree เป็นต้นไม้ที่แผ่ขยายออกไป ซึ่งไม่มีต้นไม้สองต้นในชุดที่มีขอบเหมือนกัน สมมติว่า 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