楼主:
DJWS (...)
2016-03-31 13:53:20※ 引述《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至少有两个“好的边”。
这样对吗？