推 nowar100:謝謝 我再想想看 08/13 10:50
※ 引述《nowar100 (拋磚引玉)》之銘言：
: 小黃上冊四版 P.6-35 推廣2
: 證明部分
: "因此 v1 - v2 - ... - vi - v1 為G的一個長度 i >= k+1 的環路"
: 這句我不懂，光從上一句只知道 存在 i >= k+1 使得 v1 與 vi 相鄰
: 這樣的話頂多變成 vi - v1 - v2 - ... - vk 阿，怎麼變出他那句結論的
: 謝謝
每點不是至少k嗎
要是v1之其他鄰點不在這條最長的路徑上則與假設矛盾
所以v1與P上其他點相連 但是v2~vk只有k-1個點
所以"至少"再加上一個其他點vi使形成一個環路v1-v2-....vi-v1
(注意vi是要在他的環路上，否則會違背最長路徑是從v1~vk)
不知道這樣說有沒有錯orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.114.98.32