ryamada https://blog.hatena.ne.jp/ryamada/ ryamadaのコンピュータ・数学メモ https://ryamada.hatenadiary.jp/ グラフ 最小全域木 とはいえ、一応、メモ １次元最小全域木では、頂点数に対して、辺の数は(木だから) これは、このように考える 点があって、辺がない状態から、辺を１つ増やすと、点が２つ結ばれる それに連結するように辺を１つ増やすと、連結な点の数が１つ増える したがって、辺の数とつながっている点の数をペアで表せば(1,2),(2,2+1),(3,2+1+1),...,(n-1,n)となり、n-1本でn個の頂点がつながる 連結作業の回数が(n-1)回である ２次元最小全域木では？ 初めに、３頂点を選び、３本の辺、１個の三角形を作るところから始める ついで、この三角形の辺を共有する三角形を連結することで、点を増やすと、… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fryamada.hatenadiary.jp%2Fentry%2F20110909%2F1315273955" title="点の数、辺の数、面の数 - ryamadaのコンピュータ・数学メモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2011-09-09 10:52:35 rich https://ryamada.hatenadiary.jp/entry/20110909/1315273955 1.0 100%