作者Aa841018 (andrew)
看板Grad-ProbAsk
标题[理工] 107清大计科！
时间Sun Jan 19 23:56:26 2020
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
请问我哪里做错了吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 110.28.64.164 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579449388.A.A0E.html
※ 编辑: Aa841018 (110.28.64.164 台湾), 01/20/2020 00:06:00
1F：推 Zhu81801: degree会是边数的两倍 n应该是2 01/20 00:12
2F：推 Zhu81801: 所以11n(total degree)/2=6n-1(点数-1) 01/20 00:18
3F：→ MASAGA: branch+root那边有点重复计算了吧 01/20 00:25
4F：→ Aa841018: 恩，我知道，但那是解答的做法，我想请问我的做法有什 01/20 00:25
5F：→ Aa841018: 麽问题？ 01/20 00:25
6F：→ Aa841018: 请问哪里重复计算了？ 01/20 00:26
7F：推 mistel: 资结那个定理本质上就是e=v-1的衍生而已... 01/20 00:26
8F：→ MASAGA: 这里degree是相邻点个数 不是child个数 01/20 00:26
9F：→ mistel: 而且你考卷上都写这边叫做leaf了，怎麽还会这样算 01/20 00:27
10F：→ MASAGA: 所以1个node叫A 他有两个child A就会被多算一次 01/20 00:27
11F：→ Aa841018: 恩…谢谢！ 01/20 00:29
12F：→ MASAGA: 打完发现我叙述的有点怪XD 有不懂再说 01/20 00:32
13F：推 mistel: 他说这是tree 没说这是binary tree 所以也不能预设degree 01/20 00:33
14F：→ mistel: 为3的点有几个儿子 01/20 00:33
15F：推 mistel: 所以这样像资结那样列式也不成立 因为degree=3个点你不确 01/20 00:37
16F：→ mistel: 定会不会有一个节点是root有三个儿子 01/20 00:37
17F：→ mistel: 但在写n*2时就预设了degree为3的点都不是root 01/20 00:38