# Graph Analysis - Minimum spanning forest

Minimum spanning forest

## Application

Application: Design hot-water delivery network for the university campus:

• Network must achieve same connectivity as input graph.
• An edge represents a possible pipe.
• Weight of edge is cost of installing the pipe.
• Goal: minimize total cost.

### Grow

``````def Grow(G)
S := 0;
consider the edges in increasing order # Increasing order: 2, 3, 4, 5, 6, 7, 8, 9.
for each edge e:
if e’s endpoints are not yet connected
add e to S.```
```

### Shrink

``````def Shrink(G)
S = {all edges} consider the edges in order, from highest-weight to lowest-weight # Decreasing order: 9, 8, 7, 6, 5, 4, 3, 2.
for each edge e:
if every pair of nodes are connected via S -{e}:
remove e from S.```
```

Discover More
Graph - Analysis

Analysis of graphs involves the application of algorithms determining certain details the graph structure, Most of this algorithm are implemented in linear algebra. Determining all routes ...
Linear Algebra - Graph

graph in linear algebra Formulating GF(2) vector: subset {Pembroke, Main, Gregorian} is represented by: Pembroke Athletic Bio-Med Main Keeney Wriston Gregorian 1 1 1 Edge Representation...