PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 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的点都不是root
https://i.imgur.com/JHvXBvo.jpg
反例
继续阅读
[理工] 离散 图论
lucy35
[理工] 资结 hash
shinle14
101中央 离散一题
chiuchang
[理工] 工数 ode 极座标
rayi0327
[理工] 107交大资工 线性代数15题
Moderator
[理工] 清大108 资料结构算法
enrageme
[商管] 计概 何者无法以16进制表示
violetsa
[理工] 交大 107计系
jean20157
[理工] 中正电机线代
eric17195
[理工] 108台联线代
mtw546
Links
booklink
Contact Us: admin [ a t ] ucptt.com