= Solution
Use the maximum-weight version of <Kruskal's algorithm>: sort the <edges> by decreasing weight, start with no <edges>, and add an <edge> exactly when it joins different current <connected components of a graph>. For the maximum over all <forests>, skip negative-weight <edges>; removing a negative <edge> always preserves a <forest> and increases its weight. Zero-weight <edges> are optional. The <matroid greedy algorithm> for the <graphic matroid> proves this procedure optimal; it maximizes over independent sets rather than requiring a full basis.
The positive <edges> are considered in the order
$$
12:9,\quad15:8,\quad25:7,\quad23:4,\quad35:3.
$$
Admit $12$ and $15$. Reject $25$, since it closes the triangle on $1,2,5$. Admit $23$. Reject $35$, since $3$ and $5$ are already joined by the path $3,2,1,5$. Skip both negative <edges> incident with vertex four. Therefore
$$
\boxed{F^*=\{12,15,23\},\qquad w(F^*)=9+8+4=21.}
$$
Vertex four is isolated. Requiring a <spanning tree> would force a negative <edge> and solve a different optimization problem. With a <disjoint-set data structure>, sorting dominates the running time, giving $O(|E|\log|E|)$.
Back to article page
