更多“3.若图G= <v, e> 中具有一条汉密尔顿回路, 则对于…”相关的问题
第1题
3.若图G= <v, e> 中具有一条汉密尔顿回路, 则对于结点集V的每个非空子集S,在G中删除S 中的所有结点得到的连通分支数为W,则S中结点 数|S|与W满足的关系式为
点击查看答案
第2题
设G=<v,e,w> 是一个通信网络,其中结点集V是站点集合,边集E是站点之间的链路集合,
,权值w(e)表示带宽,并且假设每条边的权都不相等. 对于任意站点
,一条u-v路径P的最大带宽是
,即这条路径上的所有边的带宽的最小值. 而u与v之间的最佳带宽w(u,v)=max{w(P)|P是一条u-v路径},即所有u-v路径带宽的最大值. 这也是u与v之间通信的最佳带宽. (1)证明存在一棵生成树,使得在这棵树中,连接每对结点u,v唯一路径的最大带宽等于u与v之间的最佳带宽. (2)设计一个找这样一棵生成树的算法,并分析算法的时间复杂度.
点击查看答案
第3题
设G = <v, e> 中无孤立点,M是G的最大匹配,N为G的最小边覆盖,则M∩N=0
点击查看答案
第4题
若图G= <v,e> 的关联矩阵表示为
,则图G中的边数为( )
点击查看答案
第5题
设G=<V,E>为无向图,命题均有,则G中存在哈密顿通路”的真值为( )。
设G=<V,E>为无向图,命题
均有
,则G中存在哈密顿通路”的真值为( )。
点击查看答案
第6题
给定无向图G= <v,e> ,如下图所示,下面哪个边集是其边割集( )。
点击查看答案
第7题
设图G=<V,E>,G'=<V’,E'>,若______ , 则G'是G的真子图;若______,则G'是G的生成子图。
点击查看答案
第8题
设G = <v1, v2, e> 为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配,也是最大匹配。
点击查看答案
第9题
若无向图G= <v,e> 的邻接矩阵表示为
,则图G中的边数为( )
点击查看答案