大门|大门-CS-2005 |问题84

设s和t是无向图G+（V，E）中具有不同正边权的两个顶点。设[X，Y]是V的一个划分，使得s&in；X和t&in；考虑在所有具有一个顶点x的边和Y.中的一个顶点之间具有最小权重的边E。 让边e的权重表示该边上的拥塞。路径上的拥塞被定义为路径边缘上的最大拥塞。我们希望找到从s到t的路径具有最小的拥塞。以下哪条路径总是这样一条拥塞最小的路径？ （A） 最小加权生成树中从s到t的路径 （B） 从s到t的加权最短路径 （C） 从s到t的欧拉步行 （D） 从s到t的哈密顿路径 答复: （A） 说明： 假设从A->B开始的最短路径是6，但在MST中，我们有A->C->B（A->C=4，C->B=3），然后沿着MST中的路径，我们有最小的拥塞，即4 这个问题的小测验