CSCI3160 Special 4：树的路径、Prim 演算与割性质
原件：Sp04 题目（本地课件） p.1，图形已逐边视觉核对。 每题先题解后解析。题解为自行推导；Prim 初始边和平局规则在下文明确固定。
Problem 1：树中恰有一条简单路径
题解
连通性保证存在路径，删去其中重复顶点间的绕行可得到简单路径。若存在两条不同的简单路径，它们分叉后再汇合的两段构成环，与树无环矛盾，所以简单路径唯一。
具体解析
从u沿两条路径同时走，找到最后一个仍相同的前缀顶点a，再找分叉后第一次共同到达的顶点b。a到b的两条内部不相交路径拼成一个环。不能把两条全路径简单拼起来就声称是简单环，因为它们可能还共享其他部分；选择这一对分叉与汇合点解决这个问题。
自取树边ab、bc、bd，a到d只能走a,b,d。再添加cd后，出现另一条a,b,c,d，原图也随之出现b,c,d,b这个环，显示“唯一路径”与“无环”之间的联系。
Problem 2：Prim 的选边顺序
题解
采用课堂“先选全图最轻边”版本，并在同权时按端点字母序选边。得到顺序：bd(1)、de(1)、eg(1)、cg(1)、df(2)、ae(3)，总权重9。
具体解析
原图是无向图，共7点、11边：ac=6、ae=3、bc=2、bd=1、cd=5、ce=2、cf=6、cg=1、de=1、df=2、eg=1。曲线连接d与e，权重1；不是d到g。图中没有方向箭头。
全图最轻边有多条，因此题目若不规定初始和平局，选边顺序并不唯一。本文先选bd，树内S={b,d}；之后每次只在一端在S、一端在外的跨边中选最轻，不再全图找最轻边。依次加入e、g、c、f、a。每次加入一个新顶点，最终7点6边连通，是生成树；每步最轻跨割边的安全性由Q4保证。
采用从a开始的标准单根Prim可能先选ae，所得顺序不同但同样正确。答题应说明版本，不能把某一种合法执行当作唯一答案。
独立检查总权重 9，而非只重跑 Prim。 七点生成树需要六条边。任何树都要有边连到 a，a 的关联边中最轻为 ae，重量 3；取出这条接入 a 的边后，剩下五条边中至多四条能取重量 1（原图恰有 bd、de、eg、cg 四条），另一条至少重 2。因此任意生成树成本至少 。上面的六条边确实连通且总重 9，便同时给出可行解和相等下界。这是这个具体图的额外证书，不替代一般割性质证明。
自测：为什么不能仅说“六条最轻边之和”就是 MST？
六条最轻边可能围成环并漏掉 a。下界可以放宽可行性，但上界必须给出真正连通无环的树；这两步缺一不可。
Problem 3：每一步全部跨边如何变化
题解
按Q2执行，各轮选边前的跨边集合如下。边统一写成较小字母在前，括号为权重。
| 当前S | 全部跨边 | 本轮选边 |
|---|---|---|
| {b,d} | bc(2)、cd(5)、de(1)、df(2) | de(1) |
| {b,d,e} | bc(2)、cd(5)、ce(2)、ae(3)、eg(1)、df(2) | eg(1) |
| {b,d,e,g} | bc(2)、cd(5)、ce(2)、cg(1)、ae(3)、df(2) | cg(1) |
| {b,c,d,e,g} | ac(6)、ae(3)、cf(6)、df(2) | df(2) |
| {b,c,d,e,f,g} | ac(6)、ae(3) | ae(3) |
| 全部顶点 | 空 | 结束 |
具体解析
添加e时，原来的de两端都进S，故不再是跨边；新出现的ae、ce、eg只有e这一端在S，成为跨边。添加c时，bc、cd、ce、cg全部转为内部边而消失，ac、cf成为新跨边。这里列的是全部跨边，不是每个树外顶点只保留一条的best-cross队列。
例如S={b,c,d,e,g}时，f同时有cf(6)、df(2)两条跨边；优先队列实现只需保存f的最佳边df(2)，但题目要求跨边变化时不应把cf漏掉。每轮检查边的两端状态，恰一端在S才留下，是最可靠的手算方式。
Problem 4：割性质
题解
取任意MST T。若最轻S跨边e在T中，完成。否则加e成环，该环必还有另一条S跨边f。因为w(e)≤w(f)，换成T+e−f仍为生成树且权重不增加，因此也是MST并包含e。
具体解析
沿环穿过e离开S后，为回到起点必再进入S，所以另一条跨边确实存在；不能随便删环上一条内部边，因为其权重未必≥e。删环边保连通、加一减一保边数，因此仍是树。
若边权相等，交换可能仅保持总权重，故结论是e属于某棵MST，不是所有MST。若e是该割唯一最轻边，任何不含e的MST都能通过严格降权改进，这时才能加强为每棵MST都含e。本文图有重复权重，所以不能默认唯一性。
来源与证据
Sp04 p.1。原图已渲染核对，全部边、MST权重和跨边表已按端点集合独立检查。其余证明为自行推导。