問題タブ [spanning-tree]

スパニング ツリー プロトコルがパスの冗長性をどのように提供するかに関連する非常に基本的な質問があります。

あなたの見解はどうですか？

「この質問がSOに属していることを確認してください」は、そうでない場合は無視します。

指定されたツリーがMSTである場合、線形時間O（n）をチェックインするにはどうすればよいですか？

すべての最小スパニング ツリーを見つけたいわけではありませんが、それらがいくつあるかを知りたいのですが、これが私が検討した方法です。

• プリムまたはクラスカルのアルゴリズムを使用して 1 つの最小スパニング ツリーを見つけてから、すべてのスパニング ツリーの重みを見つけ、最小スパニング ツリーの重みと等しい場合にランニング カウンターをインクリメントします。

すべてのスパニング ツリーの重みを見つける方法が見つかりませんでした。また、スパニング ツリーの数が非常に多い可能性があるため、この方法は問題に適していない可能性があります。最小スパニング ツリーの数は指数関数的であるため、数え上げるのは得策ではありません。

• すべての重みは正になります。
• また、グラフに 3 回以上表示される重みはないと仮定することもできます。
• 頂点の数は 40,000 以下になります。
• エッジの数は 100,000 以下になります。

頂点の重みが異なるグラフ内の最小全域木は 1 つだけです。最小全域木の数を求める最良の方法は、この性質を利用したものに違いないと思います。

編集：

この問題の解決策を見つけましたが、なぜ機能するのかわかりません。誰か説明してくれませんか。

解決策: 最小スパニング ツリーの長さを求める問題は、かなりよく知られています。最小スパニング ツリーを見つけるための 2 つの最も単純なアルゴリズムは、Prim のアルゴリズムと Kruskal のアルゴリズムです。これら 2 つのうち、Kruskal のアルゴリズムは重みの昇順でエッジを処理します。ただし、Kruskal のアルゴリズムには考慮すべき重要なポイントがあります。重みで並べ替えられたエッジのリストを検討する場合、エッジを貪欲にスパニング ツリーに追加できます (ただし、何らかの方法で既に接続されている 2 つの頂点を接続しない限り)。 ）。

ここで、クルスカルのアルゴリズムを使用して部分的に形成されたスパニング ツリーを考えます。長さが N 未満のいくつかのエッジを挿入したので、長さが N のエッジをいくつか選択する必要があります。アルゴリズムは、可能であれば、長さが N を超えるエッジの前にこれらのエッジを挿入する必要があると述べています。これらのエッジを任意の順序で挿入します。また、挿入するエッジに関係なく、グラフの接続性はまったく変更されないことに注意してください。(頂点 A から頂点 B へのエッジがあるグラフとないグラフの 2 つの可能なグラフを考えてみましょう。2 番目のグラフは、同じ接続コンポーネントの一部として A と B を持っている必要があります。そうでない場合、A から B へのエッジはワンポイント。）

これら 2 つの事実は一緒に、Kruskal のアルゴリズムを使用して長さ K のエッジを挿入する方法の数の積になることを意味します (K の可能な値ごとに)。任意の長さのエッジが最大で 3 つあるため、さまざまなケースが力ずくで実行される可能性があり、接続されたコンポーネントは通常どおり各ステップの後に決定できます。

重み付きグラフGの最小ボトルネックスパニングツリーは、スパニングツリー内の任意のエッジの最大重みを最小化するようなGのスパニングツリーです。MBSTは、必ずしもMST（最小スパニングツリー）である必要はありません。

これらのステートメントが意味をなす例を挙げてください。

重みのないエッジを持つ無向連結グラフがあります。すべてのノードの深さの合計が最小になるように、スパニングツリーを構築するにはどうすればよいですか（ソリューションは一意ではない可能性があります）？エッジの「重み」は実際には子供の深さによって異なるため、これは明らかに最小スパニングツリーを見つけていません。

根が指定されていれば、子として接続できるものすべてを幅優先で各ノードに貪欲に接続することで、深さの合計が最小のツリーを形成できると思います。したがって、これと同じ手順をN回適用し、N個のノードのそれぞれをルートとして指定し、N個の候補の中から最小のものを選択することによって、合計の深さが最小のツリーを見つけます。これは有効なアルゴリズムですか？それが間違っているかどうか、またはより効率的なものが存在するかどうかを指摘してください。

G = (V,E)接続された無向グラフに対して深さ優先検索 (DFS) アルゴリズムを実行すると、スパニング ツリーが提供されます。グラフで DFS を実行しているときに、次数が 1 より大きい頂点に到達すると、つまり、複数のエッジが接続されている場合、続行するエッジをランダムに選択します。続行するエッジ (または頂点) を選択するオプションで、DFS を使用して特定のグラフのすべてのスパニング ツリーを実際に作成できるかどうかを知りたいですか?

最小積スパニング ツリーは、最小和スパニング ツリーとは異なりますか? plzは説明してください（可能であれば例を挙げて）。つまり、最小値に追加されるエッジには最小値の積もあるはずです（？）。

スパニングツリーに基づく質問に出くわしました：

エッジ分離スパニング ツリーとはどういう意味ですか? それは、すべてのツリーで同じエッジを持たないような異なるツリーを意味しますか?ばらばらであることは共通点がないことを意味します。説明してください。また、その答えは何ですか？

スパニング ツリー データ構造が使用されている実世界のアプリケーションを知っている人はいますか?