Linear Algebra - Graph

1 - About

3 - Minimum Spanning Forest

3.1 - Formulation

Formulating ] in linear algebra

Let D = set of nodes {Pembroke, Athletic, Main, Keeney, Wriston}

Pembroke Athletic Bio-Med Main Keeney Wriston Gregorian
1 1 1
  • Edge Representation in term of vectors:
Edge Vector
Pembroke Athletic Bio-Med Main Keeney Wriston Gregorian
{Pembroke, Athletic} 1 1
{Pembroke, Bio-Med} 1 1
{Athletic, Bio-Med} 1 1
{Main, Keeney} 1 1
{Main, Wriston} 1 1
{Keeney, Wriston} 1 1
{Keeney, Gregorian} 1 1
{Wriston, Gregorian} 1 1
  • The vector representing {Keeney, Gregorian} is the sum, for example, of the vectors representing {Keeney, Main }, {Main, Wriston}, and {Wriston, Gregorian}.
  • A vector with 1’s in entries x and y is the sum of vectors corresponding to edges that form an x-to-y path in the graph. For instance, the span of the vectors representing {Pembroke, Bio-Med}, {Main, Wriston}, {Keeney, Wriston}, {Wriston, Gregorian }

<WRAP indent>

  • contains the vectors corresponding to

{Main, Keeney}, {Keeney, Gregorian}, and {Main, Gregorian}

  • but not the vectors corresponding to

{Athletic, Bio-Med } or {Bio-Med, Main}

</note>

3.2 - Algorithm


def Grow(G)
    S := 0; 
    consider the edges in increasing order
    for each edge e:
        if e’s endpoints are not yet connected
             add e to S.


def Grow(V)
    S = 0; 
    repeat while possible:
        find a vector v in V not in Span S,
        and put it in S.

  • Considering edges e of G corresponds to considering vectors v in V
  • Testing if e’s endpoints are not connected corresponds to testing if v is not in Span S.

The Grow algorithm for MSF is a specialization of the Grow algorithm for vectors. Same for the Shrink algorithms.

4 - Basis

One kind of basis in a graph G: a set S of edges forming a spanning forest.

  • Spanning: for each edge xy in G, there is an x-to-y path consisting of edges of S.
  • Independent: no cycle consisting of edges of S

A basis for a graph is a spanning forest. Unique Representation shows that, for each edge xy in the graph,

  • there is an x-to-y path in the spanning forest, and
  • there is only one such path.

Data Science
Data Analysis
Statistics
Data Science
Linear Algebra Mathematics
Trigonometry

Powered by ComboStrap