教材全解_算法导论

题目	题型
设（u,v）是连通图G中一条权重最小的边，证明：边（u,v）为图G的某棵最...	问答
Sabatier教授猜想除了一个逆定理：设G=(V,E)是一个连通无向图，...	问答
证明：如果图G的一条边（u,v）包含在图G的某棵最小生成树中，则该条边是横...	问答
给出一个连通图的例子，使得边集合{(u, v): 存在一个切割(S, V-...	问答
设e为连通图G=(V, E)的某条环路上权重最大的边。证明:...	问答
证明:如果对于图的每个切割，都存在一条横跨该切割的唯一的轻量级边，则该图存...	问答
证明:如果一个图的所有边的权重都是正值，则任意一个连接所有结点且总权重最小...	问答
设T为图G的一棵最小生成树，设L为树T中一个边权重的有序列表。...	问答
设T为G=(V, E)的一棵最小生成树，设V为V的一个子集。...	问答
给定图G和G的一棵最小生成树T,假设减小了T中一条边的权重。证明:T仍然是...	问答
给定图G和一棵最小生成树T,假设减小了位于T之外的某条边的权重。请给出一个...	问答
对于同一个输入图， Kruskal算法返回的最小生成树可以不同...	问答
假定我们用邻接矩阵来表示图G=(V, E)。请给出Prim算法的一-种简...	问答
对于稀疏图G=(V, E)，这里{E\| =(V)，使用斐波那契堆实现的Pr...	问答
假定图中的边权重全部为整数，且在范围1~\|V\|内。在此种情况下，Krusk...	问答
假定图中边的权重取值全部为整数，且在范围1~\|V\|内。Prim 算法最快能...	问答
假定一个图中所有的边权重均匀分布在半开区间[0, 1)内。Prim算法和K...	问答
假定图G的一棵最小生成树已经被计算出来。如果在图中加入一个新结点及其相关的...	问答
Borden教授提出了一个新的分治算法来计算最小生成树。该算法的原理如下:...	问答
(次优最小生成树)设G=(V, E)为一连通无向图，...	问答

题目

题型

设（u,v）是连通图G中一条权重最小的边，证明：边（u,v）为图G的某棵最...

问答

Sabatier教授猜想除了一个逆定理：设G=(V,E)是一个连通无向图，...

问答

证明：如果图G的一条边（u,v）包含在图G的某棵最小生成树中，则该条边是横...

问答

给出一个连通图的例子，使得边集合{(u, v): 存在一个切割(S, V-...

问答

设e为连通图G=(V, E)的某条环路上权重最大的边。证明:...

问答