Re: [問題] 求神人解一題 證明是不是關節點
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間8年前 (2016/03/31 13:53)推噓1(1推 0噓 3→)留言4則, 3人參與討論串2/2 (看更多)
※ 引述《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
推
04/01 03:15, , 1F
04/01 03:15, 1F
→
04/01 08:47, , 2F
04/01 08:47, 2F
→
04/01 10:33, , 3F
04/01 10:33, 3F
→
04/01 10:35, , 4F
04/01 10:35, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
