4

|V|のDAGが与えられた = nであり、s個のソースがあるため、各サブグラフが約k1=√|s|になるようにサブグラフを提示する必要があります。ソースとおよそk2=√|n| ノード。

DAGの高さを、あるソースからあるシンクまでの最大パス長と定義するとします。

生成されるすべてのサブグラフの高さがほぼ同じである必要があります。

（サブグラフの）ノードセットの各ペアの共通部分は空です。

添付の写真で右のパーティションの例を見ることができます（グラフの各エッジは上向きです）。

代替テキスト

この例では、36個のノードと8個のシンク[＃10,11,12,13,20,21,22,23]があります。したがって、各サブグラフには6個のノードと2個または3個のシンクが必要です。

アルゴリズムのアイデアはありますか？

どうもありがとうございます

4

1 に答える 1

1

グラフが間接的に接続されていると仮定しても、一部の情報を見逃しているようです。次の例を見てください。
各サブグラフに3つの頂点があるはずですが、頂点6を見てください。5がない場合は、コメントにあるはずのようにグラフが接続されていないため、これで完了です。
もしそうなら-最大で{7,8,9}の1つと一緒でなければならない-それは7と一緒だとしましょう。すなわちU={5,6,7}
ここで8を見てみましょう、それはU'にあるとしましょう。 5はU'にないため、サブセットU'が接続される解決策はありません。
タスクの説明をもう一度見て、詳細を教えてください（または、この例を反例として挙げて、解決できない可能性があることを示してください）
矛盾

于 2011-03-20T17:15:58.040 に答える