木の性質 | Notion

木 := 閉路のない連結なグラフ。

下記の性質を一つでも満たしていればそのグラフは木であり、必然的に他の性質も満たす。

木の性質

葉 := 次数が1つしかない頂点のこと。

この問題で木の性質を考える。

葉と葉から伸びている辺を削除しても木のままである。

N点からなる木の辺数はN-1

以上より削除の操作を行った後の頂点数は $N-1$ , 辺の数は $N-2$ よって削除後のグラフも木である。

つまり指定された頂点を持つ最小の連結グラフ(最小の木)は削除できる葉を削除しきれば残りが答えの最小の木である。

以下はDPの考え方を使ってDFSによって部分木の大きさを求めている。

実は部分木でも上記の問題は求められる。むしろそのほうが思いつきやすい(と私は考えている)。