= Minimum-weight acyclic subgraph
Among all <acyclic graphs> contained in a finite weighted <undirected graph>, with no requirement to connect <vertices>, one optimum is obtained by keeping only strictly negative <edges> and computing their <minimum spanning forest>. Removing a nonnegative <edge> never worsens weight or creates a cycle. Within a connected component of the negative-edge subgraph, any disconnected candidate <forest> can be extended by a negative crossing <edge>, strictly improving its weight. Hence an optimum must span each such component and minimise its tree weight. <Kruskal's algorithm> on the negative <edges> therefore solves the problem. Zero-weight <edges> are optional when they preserve acyclicity.
Back to article page
