木の分割統治アルゴリズムを書こうとしています。分割ステップでは、ノードを削除することにより、n個のノードとm個のエッジを持つ特定の無向グラフG =（V、E）をサブツリーに分割するアルゴリズムが必要です。すべてのサブグラフには、 n / 2を超えるノードが含まれないというプロパティが必要です（ツリーは可能な限り均等に分割する必要があります）。最初に、ツリーからすべての葉を再帰的に削除して最後に残っているノードを見つけようとしました。次に、Gで最長のパスを見つけて、その中央のノードを削除しようとしました。以下のグラフは、両方のアプローチが機能しないことを示しています。
私が望むことを実行するいくつかの動作するアルゴリズムはありますか（上記の場合はノードHを返します）。
私はあなたがこのようなアルゴリズムでそれを行うことができると思います：
ルートから開始します（ツリーがルート化されていない場合は、任意のノードを選択します）。
各ステップで、最大のサブツリーを持つ子ノードに降りてみてください（サブツリーの「下」にあるノードの数が最大です）。
そうすることでノードの「上」の数がn/2より大きくなる場合は停止し、そうでない場合はその子を続行します。
ツリーが適度にバランスが取れていて、ノードごとにサブツリーのサイズが事前に計算されている場合、このアルゴリズムはO（log n）である必要があります。これらの条件の1つが当てはまらない場合は、O（n）になります。
正確なアルゴリズムの1つは、次のとおりです。
リーフから開始し、ばらばらのグラフ（実際にはすべてK1）を作成し、各ステップでこのリーフの親を見つけて、新しいツリーにマージします。ノードxにr既知の子があり、ノードの次数がj単純j = r+1にの子ノードにないノードはx、この場合は現在のノードの親であり、そうでない場合は、関連するルート化されたサブツリーが構築されないような子があります。この場合、ノードはです。xnicexbad
したがって、各ステップでniceノードを関連する親に接続します。各ステップでsum of {degree of parent nice nodes}も、少なくとも1つの適切なノードがあることは明らかです（リーフから開始するため）。したがって、アルゴリズムはO（n）であり、実行されます。完全に、しかし削除されるべきノードを見つけるために、実際には各ステップで二結合リスト（サブツリーリスト）のサイズをチェックする必要があります、これは構築中のO（1）で行うことができます、またリストのサイズが等しい場合またはn/2より大きい場合は、関連するniceノードを選択します。（実際、この条件を満たす最小リストで素敵なノードを見つけてください）。
明らかなことは、ツリーを適切に分割できる場合（各部分には最大でn / 2のノードがあります）、このアルゴリズムで実行できますが、そうでない場合（実際には、ツリーを2つ以上の部分に分割することはできません） n / 2よりも小さいサイズ）これにより、適切な近似値が得られます。また、ご覧のとおり、入力ツリーには仮定がありません。
注：1つのノードを削除しても、n/2よりも小さいサイズの一部に分割できないようなツリーを作成できるかどうかはわかりません。
この問題は、オブジェクトの重心を見つけることに似ているようです。各ノードが等しい質量（重量）の点質量であり、その位置がグラフ内の位置によって与えられると仮定します。アルゴリズムは、重心、つまり、接続されているすべてのサブツリーでノードの累積重みが同じであるノードを見つけようとします。
各ノードのすべてのサブツリーの累積重みを計算できます。次に、最もバランスの取れたものを選択します。サブツリーの重みが。を超えることはありませんn/2。おそらく、これはいくつかの動的計画法のタスクです。
これが私が使用してテストした方法です。
ツリーのルートを見つけることから始めます。これを行うには、すべてのノードを含むセットを作成し、対応するインデックスを格納した各ノードのネイバーの数を使用して別の配列NeighboursNumber[]を作成します。次に、セットを反復処理してリーフ（NeighboursNumber [i] == 1を持つノードi）を削除し、それらのノードを別のセットRemovedSetに追加して（更新の問題を回避するため）、各反復後にRemovedSetを実行して減少させます。セットの各要素のすべてのネイバーのNeighboursNumber[]エントリ。最後に、ルートノードが作成されます。（ケースを実装することを確認してください。2つのノードと1つのネイバーが残っています）。ルートを見つけたら、各サブツリーのサイズを見つけます。ここでの秘訣は、ルートを探しながらこれを行うことです。最初の反復でリーフを削除する前に、配列SubTreeSize[]を作成することから始め、セットからノードを削除するたびに、そのノードの値+1を親の値に追加します。SubTreeSize[parent]= SubTreeSize [parent] + SubTreeSize [removedNode] + 1; このように、ルートを見つけると、各サブツリーのサイズもわかります。次に、ルートから開始し、各ネイバーのサブツリーのサイズ+1>ノード/2を確認します。はいの場合は、そのノードを選択して再起動します。すべての子ノードのサイズが<=ノード/2の場合、ループを中断してそのノードを出力します。次に、ルートから開始し、各ネイバーのサブツリーのサイズ+1>ノード/2を確認します。はいの場合は、そのノードを選択して再起動します。すべての子ノードのサイズが<=ノード/2の場合、ループを中断してそのノードを出力します。次に、ルートから開始し、各ネイバーのサブツリーのサイズ+1>ノード/2を確認します。はいの場合は、そのノードを選択して再起動します。すべての子ノードのサイズが<=ノード/2の場合、ループを中断してそのノードを出力します。
この方法は、10^5ノードのツリーで1秒もかかりませんでした。