[理工] [DS] 關於圖論的幾個性質

[christianSK (AG)]

幾個關於graph的基本性質 想請問大家會不會證明

(i)

N 個 node 的 BST 平均高度 log(N)

(ii)

N 個 node 的 tree 至少含 N-1 個 edge

想不太到要怎麼做 謝謝大家～

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.123.117
→ killersky:你第二個應該是要問 至少含N-1個"edge"吧
謝謝提醒
→ ai305428d:tree的edge不是一定就是n-1嗎?
是阿～ 我只是想看看能不能證明這件事
※ 編輯: christianSK     來自: 140.114.123.117      (01/28 13:11)
→ tabinoyume:第2個直覺想到用反證法
→ ai305428d:因為是Tree,所以一定connected
→ ai305428d:connected graph有個必要條件:e>=v-1
→ ai305428d:證明過程是對n做數學歸納法
→ christianSK:謝謝幾位, 我再試試看
→ privatewind:e=v-1 證法是數歸法
→ privatewind:取點數為1,為2的tree  再用左右子樹推
推 FRAXIS:第一題 #1BTtVAwB
→ christianSK:謝謝~
→ sneak: e>=v-1 https://daxiv.com