问:证明了如果加权图中没有两条边具有相同的权重,则每个最小生成树(MST)中都包含与顶点v关联的权重最小的边。我的回答是:给定一个顶点( V )和一个加权图(G),我们注意到∃(存在)和与V相关的边(E)是最小权重的边。请注意,我们将有两个不同的顶点,它们将具有相同的最小权重边。这对我们来说不是问题,如果其中一个顶点包含在最小生成树中,另一个顶点将是。如果我们开始构建MST,在一个实例中必须将权重最小</em
如何在任意顶点之间的所有可能路径上找到一组最小边权重的最大值(u,v)i.e.Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9Path 2: s - x - y - z - w - t withweights 3 - 9 - 8 - 6 - 7因此,结果是max(1, 3) = 3
设G= (V,E)是赋权连通无向图,T是最小生成树。设e是不在E中的任何边(并且具有权重W(e))。证明或反驳:T U {e}是包含G‘= (V,E U {e})的最小生成树的边集。嗯,对我来说这听起来是真的,所以我决定证明这一点,但我每次都被卡住了……
例如,如果e是具有最小权重的新边,谁能向我们保证T中的边不是以错误的方式选择的,这会阻止我们在没有E-T中其他边的“帮助”的情况下获得新的最小权重