推 TassTW :因為你只能檢查一個 path 是不是 maximal 10/21 20:16
→ TassTW :沒有 "兩點間的 maximal path" 這種說法 10/21 20:18
→ snoopy0907 :若所有端點都有loop,此極大路徑還存在嗎? 10/21 20:47
※ 引述《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