Re: [離散] 最大路徑問題
※ 引述《hcsoso (索索)》之銘言：
: ※ 引述《snoopy0907 (超強氣)》之銘言：
: : 請問一下
: : 黃子嘉老師的離散裡有提到maximal path
: : 並說未必等於longest path 這一點我一直想不通
: : 有可能會發生不等於嗎?
: : 依照定義，已經不會有其它路徑包含maximal path了
: : 那不就等於longest path嗎?
: : 一直卡在這 不知道有沒有人能替小弟解惑一下
: : 謝謝
: 考慮底下這個圖:
: x‧─‧─‧─‧z
: │
: y‧
: path x-y 是條 maximal path,
: 但 path x-z (or path y-z) 才是 longest path.
謝謝，其實是有些用maximal path的證明
小黃都會提 "令p為G的maximal path = v1 v2 v3..vk
因為P為maximal path 所以和v1相鄰的點皆在p中"
我就不懂了
考慮 a---b---c---d---e
b d之間的maxcimal path 應為b---c---d 無法再更長了
那a和b相鄰卻不在p中 矛盾
怎麼回事呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 101.8.150.8
推
10/21 20:16, , 1F
10/21 20:16, 1F
→
10/21 20:18, , 2F
10/21 20:18, 2F
→
10/21 20:47, , 3F
10/21 20:47, 3F
討論串 (同標題文章)