证明:若r是有向图G的根,则G必含有一个以r为根的有向支撑树。
证明:若r是有向图G的根,则G必含有一个以r为根的有向支撑树。
发布时间：2025-05-21 20:39:32
请在 下方输入 要搜索的题目：
推荐参考答案 (
由 快搜搜题库 官方老师解答 )
答案：证明:设P(G)的元数为n,由于r是G的根。所以做如下规定:令G’={r},则按照一定的顺序对G’进行扩充,在G’中添加点u,如果u≠r且存在由u到r的弧ur,并且将弧ur也添加到G’中得到G’’。假设现在经过一系列扩充得到G(k) (1
相关试题
- 1.证明:若r是有向图G的根,则G必含有一个以r为根的有向支撑树。
- 2.设函数 f：R→R，f(x)=x+3，g：R→R，g(x)=2x+1，则 (g◦f)(x) =（ ）。
- 3.若一个图有支撑树,则该图为( )。A．简单图B．多重图C．连通图D．无向图
- 4.已知有向图 G=(V,E)其中 G 的拓扑序列是（）。
- 5.若图G有环，则G不存在拓扑排序序列
- 6.设无向图G有18条边且每个顶点的度数都是3，则图G有（）个顶点。
- 7.若f(x)=q(x)g(x) r(x), 则(f(x), g(x) )=(g(x), r(x) )。A．正确B．错误
- 8.若f(x)=q(x)g(x) r(x), 则(f(x), g(x) )=(g(x), r(x) )。A.正确B.错误
- 9.设G是一个含有6个顶点的无向图，该图至多有条边
- 10.设G是一棵树，则G 的生成树有( )棵。
