推 pikahacker:This isn't strong induction? 128.12.34.50 01/18
→ pikahacker:我的證法就是這樣 128.12.34.50 01/18
推 pikahacker:但據說有一個將n頂點分成n-k & k 的秒殺法 128.12.47.33 01/18
※ 引述《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