私は、無向グラフG =（V、E）を持ちます。ここで、Vはノードを表し、Eはエッジを表します。 Dijkstraアルゴリズムを使って、ソースノードsをルートとし、グラフGのすべてのノードVにまたがる最短パスツリーTs =（s、V）を得ました。次に、サブツリーTm =（s、K）を選択しましたすべてのV個のノードのうち、s個をK個のノードのみに接続する最短経路木Ts =（s、V）のサブセットであり、すなわち、サブツリーTmは最短経路木Tsのサブセットである。最短パスツリーのサブツリーも最短のツリーですか？
私の質問は、今、最短パスツリーTsのこのサブツリーTmも最短の木であることを、引数または補題/定理によって証明することができますか？前もって感謝します。
まあ、このSPT（最短パスツリー）は、ソースから他のノードまでのエッジを持つ単なるツリーだと思います（この方法でなければ、サイクルを含むかもしれません）。
その後、あなたは元SPTのいくつかのサブツリーを選択した場合、あなたは木の性質を維持する必要があります、そして、我々はいくつかのケースを持っている：
簡易ツリー：ちょうど1つのノードがありませんエッジ
no problems in here, it's a SPT (empty)
ノントリビアルツリー：エッジが2つ以上あることは明らかです。
this is kind of tricky.
if you suppose that this sub-tree is rooted on source, then its easy
to see that the sub-tree will be a set of shortest paths between
the source and the other nodes, making it be a SPT ROOTED ON SOURCE.
otherwise, it wont be a SPT, cause if its rooted on some other node
(instead of source), the path from the root to other node (different
from source) may not be minimum.
私はそれはそれはのサブツリーだとしてサブツリーは（最短経路のみが含まれていることを確認するのは簡単ですよりも、あなたは、ソースに根ざしているサブツリーに興味があると思うとSPT自体）、SPTになります。
「マルチキャストツリー」の定義は正確には何ですか。具体的にどのような構成ですか？ 「新しい結果の木」とは、あなたがしていることを明確にするには不十分です。 –