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

C++で完全グラフから求める辺素な全域木の最大数

完全グラフが与えられたとき、そのグラフから構成できる辺素な全域木（Edge Disjoint Spanning Tree）の数を求める方法を解説します。辺素な全域木とは、集合に含まれるどの2つの木も互いに共通の辺を1本も持たない全域木のことです。

例えば、頂点数Nが4の場合、答えは2になります。4つの頂点を持つ完全グラフは以下のようになります。

C++で完全グラフから求める辺素な全域木の最大数

このグラフから構成できる2つの辺素な全域木は以下の通りです。

C++で完全グラフから求める辺素な全域木の最大数

辺素な全域木の最大数の求め方

N個の頂点を持つ完全グラフから構成できる辺素な全域木の最大数は、次の式で求められます。

⌊n/2⌋

この式が成り立つ理由は以下の通りです。

  • 完全グラフの辺の総数は n(n-1)/2 本
  • 1つの全域木を構成するには n-1 本の辺が必要
  • したがって、最大の全域木の数は n(n-1)/2 ÷ (n-1) = n/2 となり、小数点以下は切り捨て

C++での実装例

#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++で完全二分木のノード数を効率的に数える方法

    完全二分木のノード数を数える問題 完全二分木（Complete Binary Tree）が与えられたとき、その木に含まれるノードの総数を求めるのがこの問題の目的です。例えば、次のような木があった場合、出力は 6 になります。 すべてのノードを一つずつ訪問して数えれば O(n) で解けますが、完全二分木の性質をうまく利用すると、より少ない計算量でノード数を求めることができます。 解法のアプローチ ここでは再帰的なアプローチを採用します。鍵となるのは、「ある部分木について左端の高さと右端の高さが一致しているなら、その部分木は完全な満木（パーフェクトバイナリツリー）である」という完全二分木の性質で

  2. C++で二分木の最大スパイラル和を求める方法

    この記事では、二分木が与えられたときに、その最大スパイラル和（Maximum Spiral Sum）を求めるプログラムをC++で作成します。 スパイラル和とは？ スパイラル和とは、二分木をスパイラル（ジグザグ）順に走査したときに通るノードの値の合計のことです。 スパイラル走査では、ノードを根（ルート）から葉に向かって辿ります。第1レベルは左から右へ、次のレベルは右から左へ、さらにその次はまた左から右へと、レベルごとに走査方向を交互に切り替えながら進むのが特徴です。 問題の例 例として、次のような二分木を考えてみましょう。 1 / \