Graph Analysis - Minimum spanning forest

Graph

About

Minimum spanning forest

Definition

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
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 ...
Graph
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...



Share this page:
Follow us:
Task Runner