問題タブ [minimum-spanning-tree]

加重エッジ最小スパニング ツリー MST (直接エッジがない場合はゼロ) を表す 2 次元対称行列 "myMSTdata[][]" があり、2 つのサブツリー パーティションがあるように最大加重でエッジ上の MST をカットする必要があります。 (パート 1、パート 2)。安くて簡単にできる方法はありませんか？または、そのために使用できるライブラリはありますか?

Kruskal のアルゴリズムを使用して最小全域木を生成しましたが、パスを格納する方法を知りたいと思っていました。

これは私の最小スパニングツリーです

Kruskal アルゴリズムを使用してこの最小スパニング ツリーを生成しましたが、2 つのノード間のパスを生成するのに苦労しました。誰かが擬似コードで私を助けることができますか? Adjacency List と Adjacency Matrix を使ってみた

MST がドローニー三角形分割のサブセットであることは理解していますが、最小スパニング ツリーを見つけるのにどのように役立つのでしょうか? MST にドローニー三角形分割のエッジを使用すると、どのような意味がありますか? これは、MST を見つける前に一連のポイントを三角測量しないこととどう違うのですか?

したがって、エッジが最小スパニングツリーにあるかどうかを判断することは、エッジが特定のサイクルの最も重いエッジであるかどうかという問題にまで減らすことができるようです。DFSを使用して、エッジがサイクル内にあるかどうかを検出する方法を知っていますが、それがそのサイクルで最も重いエッジであるかどうかを判断する方法はありますか？サイクルを見つけて、その中で最も重いエッジを選択するだけですか？

動的な最小全域木を作りたいです。n 個の頂点にまたがる既存の MS ツリーがあり、この新しい頂点から既存のすべての頂点にもう 1 つの頂点とエッジを追加します。新しいグラフの MST を効率的に更新するにはどうすればよいですか? O(n) が最適です。頂点の削除操作も効率化できますか?

MST を使用したグラフ (正の重みのエッジ) 一部のエッジ e が新しい値に変更された場合、完全に再作成せずに MST を更新する最良の方法は何ですか。これは線形時間で実行できると思います。また、1) e が既に MST の一部であるかどうか、および 2) 新しいエッジ e が元よりも大きいか小さいかに基づいて、別のアルゴリズムが必要になるようです。

連結グラフGが与えられた場合、グラフをGaとGbに分割します。GaとGbの最小スパニングツリー（それぞれXaとXbと呼ばれる）を見つけた場合、最小の重み付きエッジでXaをXbに接続しても、スパニングツリーが形成されますか？そのスパニングツリーは最小スパニングツリーですか？

これが私のこれまでの論理です。XaをXbに接続すると、ほぼ定義上、少なくともスパニングツリーが形成されると思います。（カウンターサンプルがある場合は便利ですが）ただし、グラフの構造によっては、XaまたはXbからエッジを削除できる場合があるため、常に最小スパニングツリーが形成されるとは限りません。次に、それらを接続するエッジを追加しますが、それでもツリーがあります。これは、同じ重みの複数のエッジが異なる頂点でXaとXbを接続する状況の場合です。

私の論理は今のところ正しいですか？

私が書いた検索アルゴリズムと比較するための最適な検索ケースを決定しようとしています。

「必須」とマークされたノードと「開始」とマークされたノードのセットがあり、残りは「オプション」とマークされています。最初の拡張が「開始」ノードである場合、必要なすべてのノードを検出するために拡張する必要があるノードの最適な数を見つけたいと思います。

• 私が探しているのは最小スパニングツリーだと思いますが、「必須」ノードで終わらないすべてのブランチを剪定します。これはシュタイナー木問題ですか？
• グラフが重み付けされていない場合、シュタイナーツリーと最小スパニングツリーのサイズは同じですか？
• 木の大きさについて何か言えることはありますか？つまり、（最小スパニングツリーサイズのサイズ=平均最短パス*＃必要なノード...これは真実ではないと思いますが、接続性などに基づいて平均を計算できると便利です）のようなものです。

いくつかの注意：

1. 必要な各ノード間にパスが存在する必要がないため、これは巡回セールスマン問題ではありません。必要な各ノードを検出するだけです。
2. 私のグラフは無向で重み付けされていません（またはそのことについては均等に重み付けされています）
3. 私のグラフには、平均して約100の必須ノードがあり、場合によっては数千のオプションノードがあります。