MathCastle
Graph TheoryMediumGraph Algorithms

Graph Algorithms · Medium problem

A network connects stations a,b,c,d,ea,b,c,d,e with possible cables and costs ab:3,ac:6,bc:2,bd:5,cd:4,ce:7,de:1ab{:}3, ac{:}6, bc{:}2, bd{:}5, cd{:}4, ce{:}7, de{:}1. A technician instead builds the spanning tree using cables ab,ac,bd,deab, ac, bd, de (which does connect every station). By how much does the technician's total cost exceed the true minimum spanning tree's cost?