私は木の分割アルゴリズム&を書くことを試みています。分割ステップでは、ノードを削除することによって、n個のノードとm個のエッジを持つ与えられた無向グラフG =（V、E）をサブツリーに分割するアルゴリズムが必要です。すべてのサブグラフには、n/2個のノード（ツリーはできるだけ等しく分割する必要があります）を超えないプロパティが必要です。最初にツリーからすべての葉を再帰的に削除して最後の残りのノードを見つけようとしましたが、Gで最長のパスを見つけようとしました。下記のグラフは、両方のアプローチが動作しないことを示しています木の分割征服アルゴリズム
私は（上記の場合におけるノードHを返します）何をしたいんいくつかの作業アルゴリズムがあります。
私はあなたがこのようなアルゴリズムでそれを行うことができると思います。rootで
スタート（ツリーが根付いていない場合、任意のノードを選択）。
各ステップで、最大のサブツリーを持つ子ノードに降下しようとします（ノードの数が「最大」です）。
これを実行すると、ノードの数がn/2より大きくなります。停止する場合は、その子を続行します。
このアルゴリズムは、ツリーが合理的にバランスされており、ノードごとに事前に計算されたサブツリーのサイズを持つ場合、O（log n）でなければなりません。これらの条件の1つが適用されない場合、O（n）になります。
無向ツリーのルートとは何ですか？また、サブツリーの大きさを知るにはどうすればよいですか？ – Listing
私が言ったように、あなたが与えられたルートを持っていないならば、ルートとして任意のノードを選ぶことができます。また、サブツリーの大きさを知るためには、結果をキャッシュすることが理想的です。その結果を複数回カウントする必要はありません。 – svick
これは確かにO（n）以上です。この例ではノードAから始めるとします。最初にサブツリー全体をスキャンし、次にBに移動してCに移動するなど、より多くの時間を与えるサブツリー全体をスキャンするたびに実行します。 – Listing
一つの正確なアルゴリズムは、このよう葉から
スタートで、（実際にはすべてがK1ている）、各段階で、この葉の親を見つけ、それぞれのステップで、新しいツリーにマージ互いに素グラフを作成しますノードxがrの既知の子であり、ノードの次数がj = r+1である場合、xの子ノードに存在しないノードは、現在のノードの親ノードであり、この場合、ノードxはniceであり、そうでなければ、この場合、ノードxはbadとなります。
niceノードを関連する親ノードに接続します。それぞれのステップでは、各ステップでも少なくとも1つの素敵なノードがあります（リーフから開始するため）sum of {degree of parent nice nodes}がわかります。アルゴリズムはO（n）それは完全に行われますが、削除すべきノードを見つけるために、実際には各ステップで二重点リスト（サブツリーリスト）のサイズを確認する必要があります。これは構築中のO（1）で行うことができます。リストのサイズがn/2以上であれば、関連するniceノードを選択します。 （実際には、この条件を満たす最小限のリストで素敵なノードを見つける）。
明らかに、ツリーを良い方法で分割することができれば（各部分には最大でn/2ノードあります）、このアルゴリズムで行うことができますが、そうでない場合は実際には2つに分割できませんまたはn/2より小さいサイズの部分）、これは良い近似を与えます。また、あなたが見ることができるように、入力ツリーには仮定がありません。
注：1つのノードを削除することで、n/2より小さいサイズのいくつかの部分に分割することは不可能なようなツリーを持つことはできません。
この問題は、オブジェクトのcenter of massを見つけるのと同じように見えます。 各ノードが等しい質量（重量）の点質量であり、その位置がグラフの位置によって与えられているとします。あなたのアルゴリズムは質量の重心、すなわち、接続されたすべてのサブツリーにノードの類似した累積重みを持つノードを見つけることを試みます。
各ノードのすべてのサブツリーの累積重みを計算できます。最もバランスのとれたものを選択してください。サブツリーの重量はn/2以上ではありません。おそらく、これはいくつかの動的プログラミングの仕事です。
「H」を削除すると、9個のサブツリーが得られます。 – Shahbaz
はいここではわかりませんが、私は多くのサブツリーを得ることができますが、私はグラフの半分よりも大きくしたいわけではありません。 – Listing
さらにもう1つ、「ツリーをできるだけ均等に分割する」を計算可能な値にするにはどうすればよいですか？ – Shahbaz