离散图论性质 houallan5478 PTT批踢踢实业坊

楼主: houallan5478 (houallan5478) 2019-07-25 22:25:25

https://i.imgur.com/RRmwAkB.jpg
想请问划线地方是因为
1.只要是component图的degree都会小于图的点数-1吗？
2.这是一个定理吗？？
感谢各位大大帮忙解惑了!

作者: mathtsai (mathtsai) 2019-07-25 22:40:00

你的第一题要不要重新描述一次？完全看不懂想问什么这题比较像是逻辑问题

作者: ok8752665 (dd8752665) 2019-07-25 23:27:00

疴举例来说五个点的图里面的每个点 degree最大不就4你是要问这个吗?不过他好像把图都假设成没有自己连自己?

楼主: houallan5478 (houallan5478) 2019-07-26 18:22:00

对!如同ok的解释的样子。是想确认degree最大可以是点数-1,是不是和component有关。主要是不太懂为什么可以直接设点数-1

作者: ok8752665 (dd8752665) 2019-07-26 19:07:00

记得老师说过没特别指定简单或多重图通常是指简单图那简单无向图不会有loopcomponent没啥特别的意思也是一个简单无向图简单无向图的degree本来就<=点数-1

作者: DLHZ ( ) 2019-07-26 23:53:00

我最多个incident edge的数量不就是除了自己以外的点都连

楼主: houallan5478 (houallan5478) 2019-07-27 00:42:00

懂了懂了感谢

继续阅读