作者square690410 (阿隆)
看板Grad-ProbAsk
標題Re: [資結]97中央資結
時間Sat Mar 21 13:39:41 2009
※ 引述《square690410 (阿隆)》之銘言：
: ※ 引述《flyinsky76 (小雞)》之銘言：
: : http://140.115.130.224:8080/~arhui/cexamn/exam/MA02_97_04.pdf
: : 想請問大家第7題該如何證明比較好?
: : 謝謝
: 跑兩次DFS，第一次跑的結果為
: A->B->C->D->H->E->F->G
: 第二次再從G為起點跑一次DFS
: G->E->A->B->......
: 兩次的DFS就可得知(將頭尾連起來)，此圖為strongly connected
XD......原來是第七題...XD
E = 2N + I用歸納證...
(1)當N等於0時，為空樹...E=I=0
(2)令N <= n-1時成立
(3)當N=n時，假設左子樹有nl個內部節點，右子樹有nr個
Il為左子樹的Internal path length，Ir為右子樹的
El為左子樹的external path ......
所以整個樹的I與E為
I = Il + Ir + nl + nr (因為全部少一個level，所以加上nl,nr)
E = El + Er + (nl+1) + (nr+1) (用n0 = n2+1，與I同理)
因為nl,nr均<= n-1，所以代入歸納假設
所以 E = (Il+2nl) + (Ir+2nr) + (nl+1) + (nr+1)
E = I + 2N
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.124.113.121
1F：推 flyinsky76:謝謝 03/21 14:39