Re: [資結]97中央資結

看板Grad-ProbAsk作者square690410 (阿隆)時間17年前 (2009/03/21 13:39)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/5 (看更多)

※ 引述《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

推

flyinsky76

03/21 14:39, , 1^F

03/21 14:39, 1^F

‣ 返回看板[ Grad-ProbAsk ] 研究

‣ 更多 square690410 的文章

文章代碼(AID): #19n7sUtP (Grad-ProbAsk)