C++ 中從完備圖中獲取最大可能的邊不相交生成樹

假設我們有一個完備圖；我們需要計算邊不相交生成樹的數量。邊不相交生成樹是生成樹，其中集合中的任何兩棵樹都沒有一個共同的邊。假設 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

Arnab Chakraborty

更新於： 21-十月-2019

182 次瀏覽

開啟您的 職業生涯

完成課程以獲得認證

開始