離散圖論性質 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

懂了懂了感謝

繼續閱讀