推 shaopin: 好的邊的英文是什麼? 04/01 03:15
→ FRAXIS: 感覺很像是 back edge 04/01 08:47
→ DJWS: 應該是他們老師自己定義的 不是常見的專有名詞 04/01 10:33
→ DJWS: 英文可能是good edge, right edge, wonderful edge之類的 04/01 10:35
※ 引述《chenfafa (fafa)》之銘言：
: 這是演算法上課老師請我們想的
: 但是我有點不能理解題目說的意思
: 題目說
: 假設
: G=(V,E) 是一個無向的連通圖
: T是一個G裡面含有根的DFS tree
: T是一個二分樹
: u屬於V，不是T的樹根也不是T的樹葉
: 然後
: 如果G裡的其中一個結束點是T裡的u的祖先，
: 加上G裡的其他點是T裡的u的後代們 這樣會被稱作是一個好的邊
: 證明或反證明 如果u不是一個G裡的關節點 那G會至少有兩個好的邊
: 謝謝
這個敘述有點模糊
如果你可以直接把題目的英文原文貼上來
或者是在紙上畫出圖解、拿手機拍、放到http://imgur.com/、把連結貼上來
這樣有助於釐清問題
我的理解是：
G是無向圖
G是連通的
G的其中一棵DFS tree，叫做T
G的其中一個點，叫做u （但是u不能是T的樹根、樹葉）
針對一個點u，一個「好的邊」定義為：
一個端點是u的祖先，另一個端點是u的子孫。 (祖先和子孫是根據T來決定的)
證明或反證明：
如果u不是關節點，那麼G至少有兩個「好的邊」。
這樣對嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.57.6
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1459403604.A.CD8.html
※ 編輯: DJWS (111.250.57.6), 03/31/2016 13:57:19