graph-theory - 最小全域木に関する簡単な質問

Question

スパニング ツリー T0 のエッジが最小スパニング ツリー T* に含まれている場合、これは T0 が最小スパニング ツリーでもあることを意味しますか?

現在、そうではないことを証明するために、いくつかのグラフを紙に描こうとしています。そうである場合は修正してください。そうでない場合は、例を見つけるのを手伝ってください。

前もって感謝します。

Answer 1

辺の重みが 2,2,1 の三角形。

編集：

このグラフには、コストが 3 (1+2)、3 (2+1)、および 4 (2+2) の 3 つの異なるスパニング ツリーがあります。コスト 4 のスパニング ツリーのすべてのエッジは、コスト 3 の最小スパニング ツリーの 1 つに含まれており、最小ではありません。