Re: [圖論] tree的pendant vertices
※ 引述《wsx02 ()》之銘言：
: Let T=(V,E) be a tree with V={v1, v2, ..., vn}, for n >= 2
: Prove that the number of pendant vertices in T is equal to
: 2 + Σ (deg(vi)-2)
: deg(vi)>=3
: 請問這題要怎麼證呢?
: 謝謝
Let t be the number of leaves in T
2(n-1) = 2e(T) = \sum_{v_i\in V} deg(v_i)
= \sum_{v_i:deg(v_i\ge 2)} deg(v_i) + t
so t = 2t-t = \sum_{v_i:deg(v_i\ge 2)} deg(v_i) -2(n-t) + 2
= \sum_{v_i:deg(v_i\ge 2)} (deg(v_i)-2)
= \sum_{v_i:deg(v_i\ge 3)} (deg(v_i)-2)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.195.141
推
03/09 20:18, , 1F
03/09 20:18, 1F