一个图的根顶点生成树的顶点是图的根顶点什么顶点

来源：蜘蛛抓取(WebSpider) 时间：2012-06-12 12:05 标签： 图的根顶点
> 问题详情
考虑下图： (1)从顶点A出发，求它的深度优先生成树。 (2)从顶点E出发，求它的广度优先生成树。 (
悬赏：0&答案豆
提问人：匿名网友
发布时间：
考虑下图：(1)从顶点A出发，求它的深度优先生成树。 (2)从顶点E出发，求它的广度优先生成树。 (3)根据普利姆(Prim)算法，求它的最小生成树。【上海交通大学1999六(12分)】请帮忙给出正确答案和分析，谢谢！
我有更好的答案
论文写作技巧
相关考试课程
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……查看: 6976|回复: 13
如果具有n个顶点的图是一个环，则它有几棵生成树？
主题帖子积分
王道论坛中级道友, 积分 577, 距离下一级还需 423 积分
王道论坛中级道友, 积分 577, 距离下一级还需 423 积分
考研年份2012
报考学校东北大学
本科学校大连理工
我认为有n棵，答案说有2n棵。答案考虑了方向，但是书上貌似没发现有向图有生成树的说法啊？
主题帖子积分
考研年份2013
报考学校华南理工大学
本科学校福建卫生职业技术学院
这不是有向图的问题，你去一个点后，怎么确定哪一个为根呢？那就是两个都有可能为根结点。
Practice is the sole criterion for testing truth.
主题帖子积分
王道论坛初级道友, 积分 119, 距离下一级还需 81 积分
王道论坛初级道友, 积分 119, 距离下一级还需 81 积分
考研年份2011
报考学校北京航空航天大学
本科学校山东科大
没说是有向图呀
主题帖子积分
考研年份2013
报考学校华南理工大学
本科学校福建卫生职业技术学院
其实我倒是觉得每个点都有成为根结点的可能，我选的答案就是n的2次方
Practice is the sole criterion for testing truth.
主题帖子积分
考研年份2008
报考学校Nil
本科学校Nil
你这种假设是不成立的。
如果是有向图，那以那个点开始遍历呢？每个点开始遍历的生成树一样么？
第4期王道安卓方向已开放报名（5月中旬开班）。
报名地址：
第13期王道C/C++方向开放报名（3月初开班）。
报名地址：
主题帖子积分
考研年份2012
报考学校北京航空航天大学
本科学校The Open University
& & 如果是有向图才是N呢
主题帖子积分
王道论坛初级道友, 积分 119, 距离下一级还需 81 积分
王道论坛初级道友, 积分 119, 距离下一级还需 81 积分
考研年份2011
报考学校北京航空航天大学
本科学校山东科大
嗯，我也觉得无向图的话是n^2,
有向图是N（采用去一条边，无前趋的那个节点为根）
主题帖子积分
王道论坛中级道友, 积分 577, 距离下一级还需 423 积分
王道论坛中级道友, 积分 577, 距离下一级还需 423 积分
考研年份2012
报考学校东北大学
本科学校大连理工
答案的解释今天又看了一遍，意思是对于图中每个结点都有逆时针和顺时针两颗生成树。
主题帖子积分
王道论坛中级道友, 积分 577, 距离下一级还需 423 积分
王道论坛中级道友, 积分 577, 距离下一级还需 423 积分
考研年份2012
报考学校东北大学
本科学校大连理工
答案的解释今天又看了一遍，意思是对于图中每个结点都有逆时针和顺时针两颗生成树。所以有2n
主题帖子积分
王道论坛初级道友, 积分 96, 距离下一级还需 104 积分
王道论坛初级道友, 积分 96, 距离下一级还需 104 积分
答案的解释今天又看了一遍，意思是对于图中每个结点都有逆时针和顺时针两颗生成树。所以有2n
流水清风 发表于
& & 嗯，就是这么理解的嘛！不过我觉得如果n=2的时候就不对了，所以我认为n应该大于2.
蓝蓝的天，白白的云，青青的山，绿绿的水！我在哪呢？嘿嘿！
主题帖子积分
王道论坛初级道友, 积分 22, 距离下一级还需 178 积分
王道论坛初级道友, 积分 22, 距离下一级还需 178 积分
考研年份2013
报考学校北京工业大学
本科学校南京信息工程大学
大神，你在哪本书上看的答案啊，我怎么看见1800题里答案是n啊？？？
主题帖子积分
王道论坛中级道友, 积分 577, 距离下一级还需 423 积分
王道论坛中级道友, 积分 577, 距离下一级还需 423 积分
考研年份2012
报考学校东北大学
本科学校大连理工
& & 哦，忘记了。
主题帖子积分
王道论坛中级道友, 积分 231, 距离下一级还需 769 积分
王道论坛中级道友, 积分 231, 距离下一级还需 769 积分
考研年份2013
报考学校北京航空航天大学
本科学校中北大学
首先生成树是对无向图而言，其次：分析本题中并不涉及普利姆算法和克鲁斯卡尔。
本题其实是考察图的层次遍历，因为从图的任一个节点出发进行层次遍历是分两种情况（可以从左向右，也可以从右向左），N各节点故有2N种情况。
仅个人观点，方便理解
主题帖子积分
考研年份2013
报考学校电子科大
本科学校电子科大
& &风华哥，我第一批买的王道书，P155页10题跟这个一样，答案怎么是n？1.树的等价命题
2.树的性质
3.生成树个数
3.最小生成树
树是很重要的一个数学概念，同时也是一个很重要的计算机概念。很多图的性质如果不方便验证，都会先在树上面验证。
1.树的等价定义
假设T至少有两个顶点，下述命题等价
a.无圈连通图
b.无圈且m=n-1
c.连通且m=n-1
d.连通图删去任意边不连通
e.增加任意边有且仅有一个圈
f.任意两个节点间有且仅有一个道理连通
其中m是T的边数，n是顶点个数
a=&b只需要证明m=n-1，归纳证明
n=2时，成立。
n&2时，假设结论对一个含有n个顶点的树成立，此时m=n-1。现证明结论对一个含有n+1个顶点的树也成立。对于含有n+1个顶点的树T，他必含有度数为1的顶点v，我们去点v和其关联的边形成的删点子图T-v是一个含有n个顶点的树，根据假设有m=n-1，并且T-v比T少一个顶点和一个边，因此对于T有。m+1=(n+1)-1.
2.树具有哪些性质呢？
& 性质1.任何顶点数大于等于2的数，至少含有两个叶子节点
& 深度优先和广度优先可以求生成树
3.生成树个数
方法1：用cayley定理求
方法2:用矩阵树求
4.最小生成树
&用cruskal算法求最小生成树&
5.最短路 径
我们首先应该明白什么是可平面图，然后知道如何判定一个图是否是平面图。如果一个图是平面图，如何画出这个平面图。
第一个问题是平面图的定义。第二个问题是平面图的判定，第三个问题是平面图的算法。最后还应该了解平面图的性质，平面图最重要的性质就是欧拉公式。
1.可平面图
现在来回答什么是平面图，我们说一个图是平面图，指的是这个图可以画在一个平面上，且任意两个不同边不相见(顶点处除外)。
图G可平面嵌入的充分必要条件是G可球面嵌入。
K5，K3，3可环面嵌入，但是不能平面嵌入。曲面嵌入是一个比平面嵌入更一般的概念。
2.欧拉公式及其推广
& &连通平面图G有n-m+f=2.其中n是G的点数，m是边数，f是面数。
这个定理的证明需要对f进行归纳。首先证明f=1时定理成立，然后假设f&k成立，证明f=k+1成立。
3.极大平面图
4.kuratowsky定理,G是可平面图当且仅当G不含于K5,K3,3同胚的子图
一个图如果不是可平面图，可以考虑将这个图放到几个平面上，使得每个平面内的边不交叉。也就是将图G的边集划分成几个小边集的并集，并且两两无交集，然后呢肖小边集的个数就是图G的厚度。平面图的厚度是1，非平面图的厚度至少是2，如何计算一个图的厚度目前并没有有效的公式和算法。
平面图在工程技术上和拓扑图论中的具有很重要的应用，从图论的历史看，正式kuratowsky定理的建立和证明打破了图论发展的沉闷局面，该定理是图论振兴的转折点。一句话，这个定理具有很重要的理论意义。
4.灌木生长算法很重要
阅读(...) 评论()查看: 769|回复: 1
如果具有n个顶点的图是一个环，则它有几棵生成树？
主题帖子积分
王道论坛初级道友, 积分 22, 距离下一级还需 178 积分
王道论坛初级道友, 积分 22, 距离下一级还需 178 积分
考研年份2013
报考学校北京工业大学
本科学校南京信息工程大学
小弟请问，有没有谁做过这道题目，这道题目是哪本书上的内容?是1800吗?
主题帖子积分
王道论坛初级道友, 积分 22, 距离下一级还需 178 积分
王道论坛初级道友, 积分 22, 距离下一级还需 178 积分
考研年份2013
报考学校北京工业大学
本科学校南京信息工程大学
没人么？？？1800题上答案是n,但是我看了坛子里有人说是2n...> 问题详情
对于图和图，分别求：
(1)从顶点1开始进行深度优先搜索的遍历序列及其生成树或生成森林。
(2)从顶点1开
悬赏：0&答案豆
提问人：匿名网友
发布时间：
对于图和图，分别求：&&&&&&(1)从顶点1开始进行深度优先搜索的遍历序列及其生成树或生成森林。&&(2)从顶点1开始进行广度优先搜索的遍历序列及其生成树或生成森林。
我有更好的答案
论文写作技巧
相关考试课程
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……

我要回帖

更多关于 图的根顶点 的文章

 

随机推荐