作者ianwuzack (不求回报)
看板Grad-ProbAsk
标题Re: [理工] [离散]-图的基本性质
时间Thu Aug 13 02:35:10 2009
※ 引述《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
1F：推 nowar100:谢谢 我再想想看 08/13 10:50