[理工] 107清大计科!

楼主: Aa841018 (andrew)   2020-01-19 23:56:26
https://i.imgur.com/CHkpyVS.jpg
请问 2.(a)
详解做法是用degree算出edge,再用E=V-1这个公式,然后求出n
但我的想法是,利用2n+3n+n=6n(vertex)
2n+3n*2+n*3+1=11n+1
(branch+root)
https://i.imgur.com/QOXiw7g.jpg
但这样n<0
请问我哪里做错了吗?
作者: Zhu81801 (Zhu81801)   2020-01-20 00:12:00
degree会是边数的两倍 n应该是2所以11n(total degree)/2=6n-1(点数-1)
作者: MASAGA (和泉千晶我老婆)   2020-01-20 00:25:00
branch+root那边有点重复计算了吧
楼主: Aa841018 (andrew)   2020-01-20 00:25:00
恩,我知道,但那是解答的做法,我想请问我的做法有什么问题?请问哪里重复计算了?
作者: mistel (Mistel)   2020-01-20 00:26:00
资结那个定理本质上就是e=v-1的衍生而已...
作者: MASAGA (和泉千晶我老婆)   2020-01-20 00:26:00
这里degree是相邻点个数 不是child个数
作者: mistel (Mistel)   2020-01-20 00:27:00
而且你考卷上都写这边叫做leaf了,怎么还会这样算
作者: MASAGA (和泉千晶我老婆)   2020-01-20 00:27:00
所以1个node叫A 他有两个child A就会被多算一次
楼主: Aa841018 (andrew)   2020-01-20 00:29:00
恩…谢谢!
作者: MASAGA (和泉千晶我老婆)   2020-01-20 00:32:00
打完发现我叙述的有点怪XD 有不懂再说
作者: mistel (Mistel)   2020-01-20 00:33:00
他说这是tree 没说这是binary tree 所以也不能默认degree为3的点有几个儿子所以这样像资结那样列式也不成立 因为degree=3个点你不确定会不会有一个节点是root有三个儿子但在写n*2时就默认了degree为3的点都不是roothttps://i.imgur.com/JHvXBvo.jpg 反例

Links booklink

Contact Us: admin [ a t ] ucptt.com