C++의 전체 그래프에서 가능한 최대 간선 분리 스패닝 트리

완전한 그래프가 있다고 가정합니다. Edge Disjoint Spanning tree의 수를 계산해야 합니다. Edge Disjoint Spanning 트리는 스패닝 트리로, 세트의 두 트리가 공통 에지를 갖지 않습니다. 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