证明:若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.若图G有环，则G不存在拓扑排序序列
- 4.已知有向图 G=(V,E)其中 G 的拓扑序列是（）。
- 5.以下说法错误的有? G是一棵根树，那么它只有一个顶点的出度为0|二分图一定是树，树也一定是二分图 |正则二分图总能找到完全匹配 |根树一定是强连通的
- 6.连通图G有n个点，其支撑树是T,则有（ ）。
- 7.若图G有一条路经过图中每个结点恰好一次,则G( ).
- 8.R(s) EsG(s)G(s图
- 9.设G是连通平面图，有v个结点，e条边，r个面，则r=
- 10.设有图G=(V(G),E(G))和图H=(V(H),E(H)) ，若V(G)=V(H)，E(H)⊆E(G)，则称图H是图G的一个_________。
