問題タブ [minimum-spanning-tree]

これは質問です、私はこれが宿題の質問であることを認めます、私は答えを探していませんが、むしろ私が正しい方向に進んでいるかどうか、そして私が親切に正しい方向に私を向けていないかどうかを知りたいです。

質問：重み付きグラフの2つのエッジに同じ重みがない場合、頂点vに付随する重みが最小のエッジがすべての最小全域木（MST）に含まれることを示します。

私の答え：頂点（V）と重み付きグラフ（G）が与えられた場合、∃（存在する）とエッジ（E）がVに関連付けられていることに注意してください。これは、最も重みの少ないエッジです。同じ最小重みのエッジを持つ2つの異なる頂点があることに注意してください。これは私たちにとって問題ではありません。頂点の1つが最小全域木に含まれている場合、もう1つは問題になります。MSTの構築を開始した場合、MSTを取得するには、エッジが最小の頂点の1つ（または両方）を含める必要があるため、ある場合には、重みが最小のエッジをMSTに含める必要があります（ MSTは、ルートからすべての頂点への最短経路を見つける必要があると述べています）

私の答えが正しいかどうかはわかりませんが、それで十分であることをどのように証明できると思いますか？

三角形の不等式に従うグラフで TSP の 3/2 近似を取得するためのクリストフィデス アルゴリズムを実装しています。Kruskal のアルゴリズムと隣接行列を使用して最小全域木を計算するためのコードは既にあります。

ここで、エッジを 2 倍にし、オイラー ツアーを見つけて、複製ノードをショートカットすることで、Christofides を実装したいと考えています。この手順を実行するにはどうすればよいですか? アルゴリズムと (オプションで) C コードが欲しいです。

ありがとう！

全て、

すべてのペアの最短経路と行列乗算の関係について読んでいます。

加重隣接行列とそれ自体の乗算を考えてみましょう。ただし、この場合、行列乗算の乗算演算を加算に置き換え、加算演算を最小化に置き換えます。加重隣接行列とそれ自体の積は、任意のノード ペア間の長さ 2 の最短パスを含む行列を返すことに注意してください。

この引数から、A の n 乗にはすべての最短経路が含まれることになります。

質問番号 1:

私の質問は、グラフでは、パス内の 2 つのノード間に最大で n-1 個のエッジがあるということです。著者は、長さ「n」のパスについてどのような根拠で議論していますか?

次のスライド

www.infosun.fim.uni-passau.de/br/lehrstuhl/.../Westerheide2.PPT

スライド 10 では、次のように述べられています。

質問 2: 著者が式 1 から式 2 をどのように結論付けたか。

アルゴリズムの紹介に関するCormenらの本では、次のように言及されています。

実際の最短経路の重み delta(i, j) は? グラフに負の重みのサイクルが含まれていない場合、すべての最短パスは単純であり、最大で n - 1 個のエッジを含みます。n - 1 を超えるエッジを持つ頂点 i から頂点 j へのパスは、i から j への最短パスよりも重みを小さくすることはできません。したがって、実際の最短経路の重みは次の式で与えられます。

デルタ(i,j) = d(i,j) パワー (n-1) = (i,j) パワー (n) = (i,j) パワー (n+1) = ...

質問 3: 上記の式では、作成者は n, n+1 個のエッジをどのように作成しましたか? また、上記の割り当てはどのように機能しますか?

ありがとう！

Mathematica を使用して最小スパン ツリーを見つけようとしていますが、Combinatorica の MinimumSpanningTree 関数を使用したいと考えています。次のコードを使用しています。

ここで、m は行列です。ただし、MinimumSpanningTree は赤くなり、機能しません。出力は

MinimumSpanningTree を機能させるにはどうすればよいですか? なぜ赤くなるのですか？

これは、私が苦労している模擬試験の問題です。

G = (V, E) を、正の重みを持つ重み付き無向連結グラフとします (重みが異なると仮定してもかまいません)。与えられた実数 r に対して、部分グラフ Gr = (V, {e in E | w(e) <= r}) を定義します。たとえば、G0 にはエッジがなく (明らかに接続されていません)、Ginfinity = G (仮定により接続されています) です。問題は、Gr が接続されるような最小の r を見つけることです。

BFS または DFS を繰り返し適用して問題を解決する O(mlogn) 時間アルゴリズムを説明してください。

本当の問題は、O(mlogn) でそれを行うことです。これが私が持っているものです：

それはなんと O(m^2 + mn) です。O(mlogn) に下げるためのアイデアはありますか? ありがとう！

無向かつ無加重 (またはすべてのエッジの加重が 1) の非巡回グラフ (G=VxE) があります。このグラフのノードのいくつかは sV (sV は V のサブセット) として選択されます。問題は、選択したすべてのノードをカバーするサブグラフを見つけたいということです。当然ながら、選択されていないノードをカバーすることもできます。ただし、目的のサブグラフにないノードは制限されます。これらの制限されたノードは、選択した 2 つのノード間の 1 つのパス上にある場合を除き、ソリューション サブグラフに含めるべきではありません。例：

A、B、C、D はノード、+ はエッジの包含を表します。このグラフでは、B と D が選択されたノードです。この例に必要なソリューションは次のとおりです。サブグラフは、ノード B、C、D とエッジ (B、C)、(C、D) * で構成されます。A は意図したとおりにサブグラフに含まれていないことに注意してください。このタイプのサブグラフを見つけるには、どのようなアプローチが役立ちますか? アイデアをありがとう。

*(X,Y) は、ノード X と Y の間のエッジを表します。

TSPの近似の1つは、次のことを行うことです。-最小スパニングツリー（MST）を計算する-MSTのDFSを実行する

TSPを解決する目的は、すべての頂点に1回だけアクセスすることです。旅行者はポイント「A」から開始し、グラフ上の他のすべてのポイントにアクセスしてポイント「A」に戻る必要があります（この句が存在しない場合もあります）。各ポイントが1回だけアクセスされるようにします。

グラフGのMST'T'が次のようになっていると仮定します。

このMSTのDFSはABCEDです。

私の質問はTSPを解決することです。旅行者が訪問しなければならないすべての都市（ポイント）のリストが必要です。明らかに、MSTには「E」から「D」へのパスはありません。では、これはどのように問題を解決しますか？

0からU-1までの範囲の非負の整数エッジ長を持つ有向グラフがあるとします。このグラフの最小全域木を計算するための最速のアルゴリズムは何ですか？クラスカルのアルゴリズムO（m log n））やプリムのアルゴリズム（O（m + n log n））など、既存の最小スパニングツリーアルゴリズムを引き続き使用できます。ただし、Uが小さい場合は、もっとうまくできるはずだと思います。

エッジの長さが一定の範囲に制限されているという事実を利用できる、従来のMSTアルゴリズムと競合するアルゴリズムはありますか？

ありがとう！

エッジの重みを表すエッジまたは実際の値がない場合、値が0の最小スパニングツリーMSTを表すポイントの対称2D配列 "myMSTdata [] []"があり、このツリーを2つに分割する必要があります。サブツリー（part1、part2）。ここで、切断基準は最大の重みを持つエッジです。次に、大きいサイズのサブツリー内の残りのノード数がKになるまで、大きいサイズのサブツリー（つまり、ノード数が多いサブツリー）を繰り返し分割し続けます。