Số cây khung rời rạc cạnh tối đa từ đồ thị hoàn chỉnh trong C++

Cho đồ thị hoàn chỉnh N đỉnh. Đếm số cây khung (spanning tree) rời rạc cạnh (edge-disjoint spanning trees) tối đa. Hai cây khung rời rạc cạnh nghĩa là không có cạnh chung.

Ví dụ N=4 → 2 cây khung rời rạc cạnh.

Công thức: số cây khung rời rạc cạnh tối đa = ⌊N/2⌋.

Ví dụ

#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);
}

Kết quả

Maximum Edge Disjoint Spanning Tree: 2