作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 求神人解一题 证明是不是关节点
时间Thu Mar 31 13:53:20 2016
※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1459403604.A.CD8.html
※ 编辑: DJWS (111.250.57.6), 03/31/2016 13:57:19
1F：推 shaopin: 好的边的英文是什麽? 04/01 03:15
2F：→ FRAXIS: 感觉很像是 back edge 04/01 08:47
3F：→ DJWS: 应该是他们老师自己定义的 不是常见的专有名词 04/01 10:33
4F：→ DJWS: 英文可能是good edge, right edge, wonderful edge之类的 04/01 10:35