2

こんにちは。テストの準備をしています。パートbとcを理解する必要があります。パートaが真実であり、それを証明できることはわかっていますが、パートbとcのアルゴリズムを見つけることは、現在私にはわかりません。

コストが最大のエッジがボトルネックと呼ばれる最小のボトルネックツリーについて、以下を解決します。（a）Gのすべての最小スパニングツリーはGの最小スパニングツリーですか？あなたの主張を証明してください。

（b）与えられたコストcに対して、O（n + m）時間のアルゴリズムを与えて、Gの最小ボトルネックスパニングツリーのボトルネックコストがc以下であるかどうかを調べます。

（c）Gの最小ボトルネックスパニングツリーを見つけるためのアルゴリズムを見つけます。

私を助けてくれる人に事前に感謝します

4

3 に答える 3

3

（b）の場合：

cよりもコストがかかるGのすべてのエッジを消去してから、左側のグラフがまだ接続されているかどうかを確認します。

（c）の場合：

（b）を分割条件として解いたアルゴリズムを使用して、cで二分探索を実行します。

（b）の証明：

Gからcよりもコストがかかるエッジを削除した後に得られたグラフがG'であるとしましょう。それで：

  1. G'が接続されている場合、 G 'にスパニングツリーTが存在する必要があります。G'のエッジのコストがcを超えることはないため、Tのエッジのコストがcを超えることはありません。したがって、 TはG'の全域木であり、ボトルネックが最大でcであるGでもあります。
  2. G'が接続されていない場合、G 'にはスパニングツリーがまったくありません。G - G'のすべてのエッジのコストがcを超え、 GのスパニングツリーにG - G 'のエッジが少なくとも1つ含まれることがわかっているため、ボトルネックが< = c

そしてもちろん、グラフが接続されているかどうかを検出するには、O（n + m）のコストがかかります

（c）の証明：

たとえば、 （b）で使用したアルゴリズムはF（G、c）です。

次に、

あるcについてF（G、c） = Trueの場合、 c'> = cを持つすべてのc'に対してF（G、c'） = True

一部のcについてF（G、c）= Falseの場合、c ' < = cを持つすべてのc'に対してF（G、c'） = False

したがって、 cで二分探索を行うことができます:)

于 2012-10-29T17:08:54.320 に答える
1 
Ans. a)False,every minimum bottleneck spanning tree of graph G is not a minimum spanning tree of G.

b)To check whether the value of minimum bottleneck spanning tree is atmost c,you can apply depth first search by selecting any vertex from the set of vertices in graph G.

***Algorithm:*** 


check_atmostvalue(Graph G,int c)
{

for each vertex v belongs to V[G] do {
visited[v]=false;
}

DFS(v,c); //v is any randomly choosen vertex in Graph G
for each vertex v belongs to V[G] do {
if(visited[v]==false) then
return false;
}
return true;
}



DFS(v,c)
{
visited[v]=true;

for each w adjacent to v do {
if(visited[w]=false and weight(v,w)<=c) then
DFS(w,c);
}
visited[w]=true;
}


This algorithm works in O(V+E) in the worst case as running timr for depth first search DFS is O(V+E).
于 2012-12-15T05:42:45.010 に答える
0

この問題は、グラフのMSTを見つけるだけで解決できます。これは、次の主張に基づいています
。MSTは、連結グラフのMBSTです。
MSTの場合、MSTで最大エッジeを選択すると、エッジeはMSTを2つのセットSとTに分割します。次に、カットプロパティから、エッジeはSとTを接続するエッジ間の最小の重みである必要があります
。 MBSTの場合、SとTを接続するエッジe'が必要です。その場合、w（e'）はw（e）以上である必要があります。したがって、MSTはMBSTでなければならないことがわかります。

ただし、最小のボトルネックを決定する別の方法があります。MBSTをコンピューター化する必要はありません。あなたの質問では、あなたは実際に最小のボトルネックの単調さを暗示しています。そのため、接続アルゴリズムと組み合わせた二分探索を使用して、最小のボトルネックを見つけることができます。私は他の場合に単一性の使用を見てきました。ここでも同様の手法が使えることに少し驚いています！

于 2016-11-05T02:39:04.707 に答える