C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++の完全グラフから可能な最大のエッジの互いに素なスパニングツリー

完全グラフがあるとします。 EdgeDisjointSpanningツリーの数を数える必要があります。 Edge Disjoint Spanningツリーは、セット内の2つのツリーに共通のエッジがないスパニングツリーです。 N（頂点の数）が4であるとすると、出力は2になります。4つの頂点を使用した完全グラフは次のようになります-

C++の完全グラフから可能な最大のエッジの互いに素なスパニングツリー

2つのエッジのばらばらなスパニングツリーは-

のようなものです

C++の完全グラフから可能な最大のエッジの互いに素なスパニングツリー

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

  1. C++で完全なツリーノードをカウントする

    完全な二分木があるとすると、ノードの数を数える必要があります。したがって、ツリーが次のような場合- したがって、出力は6になります。 これを解決するために、次の手順に従います これは再帰的アプローチを使用します。このメソッド、countNodes（）は引数としてルートを取ります。 hr：=0およびhl：=0 ルートとして2つのノードlとrを作成します lが空でない間 hlを1増やします l：=lの左側 rが空でない間 r：=rの権利 時間を1増やします hl =hrの場合、（2 ^ hl）–1を返します return 1 + countNodes（ルートの左側）

  2. C++のバイナリツリーの最大スパイラル合計

    この問題では、二分木が与えられます。私たちのタスクは、C++のバイナリツリーで最大スパイラル合計を見つけるプログラムを作成することです。 スパイラルサム 二分木のスパイラルトラバーサルで遭遇するノードの合計です。 ツリーのスパイラルトラバーサルでは、ノードはルートからリーフノードにトラバースされます。トラバーサルは左から右に行われ、次のレベルでは右から左に、以下同様に次のレベルで行われます。 例 − 出力 −5 説明 − ツリーの第2レベルの最初のノードまでスパイラルトラバーサルを検討します。 1+ 5 = 5. 3行目の合計要素は（1-9 + 6-4 =-6）であり