Graph Analysis - Minimum spanning forest

1 - About

Minimum spanning forest

3 - Definition

  • input: a graph G, and an assignment of real-number weights to the edges of G.
  • output: a minimum-weight set S of edges that is spanning and a Tree - Forest (Set of Tree).

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

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

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


Data Science
Data Analysis
Statistics
Data Science
Linear Algebra Mathematics
Trigonometry

Powered by ComboStrap