Uniform Spanning Trees

The Uniform measure on Spanning Trees (UST) of a directed connected graph corresponds to a projection DPP with kernel the transfer current matrix of the graph. The later is actually the orthogonal projection matrix onto the row span of the vertex-edge incidence matrix. In fact, one can discard any row of the vertex-edge incidence matrix - note \(A\) the resulting matrix - to compute \(\mathbf{K}=A^{\top}[AA^{\top}]^{-1}A\).

See also

histogram showing uniformity of the spanning trees generated by the different procedures
from networkx import Graph
from dppy.exotic_dpps import UST


# Build graph
g = Graph()
edges = [(0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (2, 4), (3, 4)]
g.add_edges_from(edges)

# Initialize UST object
ust = UST(g)

(Source code)

# Display underlying kernel i.e. transfer current matrix
ust.plot_graph()

(Source code, png, hires.png, pdf)

../_images/ust-1.png

(Source code)

# Display underlying kernel i.e. transfer current matrix
ust.plot_kernel()

(Source code, png, hires.png, pdf)

../_images/ust-2.png

(Source code)

# Display some samples
for md in ('Wilson', 'Aldous-Broder', 'GS'):
    ust.sample(md)
    ust.plot()

(Source code)

../_images/ust-3_00.png

Fig. 44 (png, hires.png, pdf)

../_images/ust-3_01.png

Fig. 45 (png, hires.png, pdf)

../_images/ust-3_02.png

Fig. 46 (png, hires.png, pdf)