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