N個のノード（各ノードの最大次数は3）から1つのエッジを削除して、結果として得られる2つのツリーがN / 2にできるだけ近くなるように、ツリーを分割するアルゴリズムを探しています。 。「最も中心にある」エッジを見つけるにはどうすればよいですか？
ツリーは、アルゴリズムの前の段階からの入力として提供され、グラフとして入力されます。したがって、バランスが取れておらず、どのノードがルートであるかが明確ではありません。
私の考えは、ツリー内で最長のパスを見つけてから、最長のパスの中央にあるエッジを選択することです。それは機能しますか？
最適には、どちらのツリーにも2N/3ノードを超えないようにすることができるソリューションを探しています。
回答ありがとうございます。
コメントで述べた理由で、最初のアルゴリズムが機能するとは思わない。ただし、修正されたDFSを使用すると、O（n）の時間と空間でこれを解決できると思います。
グラフをたどって、ノードの総数を数えることから始めます。これをnと呼びます。ここで、任意のノードを選択し、そのノードでツリーをルート化します。ここで、ルートから開始してツリーを再帰的に探索し、サブツリーごとに、各サブツリーにあるノードの数を計算します。これは、単純な再帰を使用して実行できます。
この時点で、各エッジについて、そのエッジを削除することでどの分割が得られるかがわかります。そのエッジの下のサブツリーにk個のノードがある場合、こぼれるのは（k、n --k）になるためです。したがって、すべてのノードを反復処理し、（k、n-k）のバランスが最も均等なノードを探すことで、最適なカットを見つけることができます。
ノードのカウントにはO（n）時間かかり、再帰を実行すると、各ノードとエッジに最大でO（1）回アクセスするため、O（n）時間もかかります。O（n）のネットランタイムの場合、最適なカットを見つけるにはさらにO（n）時間がかかります。サブツリーノード数を格納する必要があるため、O（n）メモリも必要です。
お役に立てれば！
ツリーの分割統治アルゴリズムに対する私の答えを見ると、ツリーを2つのほぼ等しいサイズのツリーに分割するノード（ボトムアップアルゴリズム）が見つかります。ここで、のエッジの1つを選択する必要があります。このノードはあなたが望むことをします。
現在のアプローチは機能していません。完全なバイナリツリーがあると仮定して、リーフ3*log nの1つに長さのパスを追加します（リーフと名付けます）。最長のパスは、このリーフbadに接続されたパスの最後まで、他のリーフの1つ内になります。bad、および中間エッジはこのパス内にあり（実際には、不良リーフを通過した後）、このエッジでベースを分割するとO(log n)、サイズの一部と別の部分がありますO(n)。