推 ooww : 感謝大大解惑 05/01 01:59
※ 引述《ooww (選ばれし子どもたち)》之銘言：
: 題目
: https://reurl.cc/R6MYGg
: 若有一棵 k 元樹（k_ary tree）其中分支度（degree）為 i 的節點數為 i 個，
: i = 1, 2, ..., k，
: 請問該 k 元樹其葉節點數 L(k)為何？
: 誠心發問此題目
: 完整回答者，願付300P做為報酬
: (是不是要自己假設樹的高度?)
我先給你個例子 你可以很快得到答案
https://imgur.com/WoveMY2
所以公式 : L(K)=1+1*2+2*3 如果i=3
一般形式為 L(K)=1+ sigma_{2 to i} (i-1)*i
證明:
對於樹而言 有 節點數-1=邊數
邊數
對於deg=i 的點 有i+1個邊與其相連 (一個在上面)
所以共有 sigma_{1 to i} i(i+1) 個邊 (有些重複算等一下討論)
有一個點是根 所以上式 要-1
對於葉點 有一個邊與其相連 所以有 L(K)個點
這樣 就確保每個邊都計算兩次 所以
邊數=( (sigma_{1 to i} i(i+1)) -1 + L(K))/2
節點數
這個簡單一點 題目已經說了
節點數=L(K) + sigma_{1 to i} i
然後利用 節點數-1=邊數
就能解L(K) (當然你要知道sigma的公式)
以上
有錢嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 69.180.5.117 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1619802162.A.78A.html
※ 編輯: RicciCurvatu (69.180.5.117 美國), 05/01/2021 01:14:03