※ 引述《pikahacker (Beat Cal)》之铭言： : 1. Prove that every tournament contains a Hamiltonian path. : (Tournament map: a directed graph such that for every pair of distinct vertices : u and v, there is either an edge from u to v or v to u, but never both.) : (I can prove this easily by double induction, but I heard there is a classic : proof by strong induction. How?) Assume this holds for all k-tournament Consider first k people in k+1-tournament, by induction hypothesis, there is a k-HamPath, say a1->a2->a3->...->ak If a wins a1, then a ->a1->a2->...->ak is a (k+1)-HamPath k+1 k+1 Similar result could be obtained if a wins a k k+1 If a1->a and a ->ak k+1 k+1 there exists i such that a ->a and a ->a i k+1 k+1 i+1 Thus a1->a2->...->a ->a ->a ->...->ak is a (k+1)-HamPath. Q.E.D. i k+1 i+1 回darkseer，没有interestingly，请爱用it is interesting that...:) -- 人，总是残缺而完美的... 　　 　　残缺的是任谁终其一生都无法得到一切， 　　　 　　　　　完美的是任谁少了一点就不再是他本人了... 残缺的我寻寻觅觅找寻着残缺的你... 且让我们共同拼出一片无间的 完 美 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 24.186.210.99