수학정리(Applications, weighted graph)

 

-About Weighted Graph

-About Matrices

-About Lap(wG)

-Lap(wG):exactly psd

-(Matrix Tree Theorem for wG)

:the sum over all spanning trees of wG (prod of all weights of the spanning tree)

= |the cofactor of Lap(wG)|

-About a(wG)

-for wG, any r >= 0, f:Fiedler vector, M(r):={vi|fi + r >= 0}, induced subgraph on M(r) is connected(link)

-for wG, any r <= 0, f:Fiedler vector, M(r):={vi|fi + r <= 0}, induced subgraph on M(r) is connected

-for wG, f:Fiedler vector, any 0 <= c < max{fi}, M:={vi|fi < c}, induced subgraph on M is connected

-for wG, f:Fiedler vector s.t. for all i, fi:nonzero, then {vivj s.t. fi*fj < 0}:subset of E(G)를 제거하면 components가 2개가 나온다.

-if G:unweighted, te a subset E' of E(G) s.t. G - E' have two connected components, then te weight on G s.t. f:Fiedler vector, fi:nonzero for all i and {vivj s.t. fi*fj <0 }=E'(link)

-for G:connected wG, f:Fiedler vector, if fi > 0, then te j s.t. vi~vj, and fj < fi(link)