グラフ理論の用語について

こんにちは、高校１年生です。

グラフ理論の基礎的な部分を習ったのですが、正しく理解できているのかどうかが分かりません。

これらの用語はこのような理解であっているのでしょうか？

１．「木」というのは、閉路を持たない、連結であるグラフ。
２．「全域木」というのは、グラフ内のすべての点を通る木
3．「最小全域木」というのは、重み付きグラフで、コストが一番低い全域木

という理解であっているでしょうか？

回答宜しくお願いいたします。

No.1 回答者： Tacosan 回答日時： 2022/09/17 03:23

1 は正しいんだけど 2 は間違い. なんらかの (連結な) グラフが与えられたときに, そのグラフの部分グラフでかつ閉路を持たない連結なグラフのことを, もとのグラフの全域木とか全点木とかいう. 「もともとなんらかのグラフが与えられている」こと, そして「その部分グラフ」であることがポイント. というか, その質問文のままだと 1 と 2 はどこが違う?

3 は, 表現としてはあってる. 「重み付きグラフ」がどういうものか理解できているかどうかはわからんけど.