For oriented edges , the probability that their unoriented versions all belong to a uniform spanning tree is the determinant of the matrix of transfer currents between them. In particular, every finite forest that can be extended to a spanning tree has positive inclusion probability.
In a finite unweighted connected graph, take distinct graph vertices and orient the unique graph path from to in a uniform spanning tree and assign signed unit current to its edges. Its mean over trees is the electrical unit flow from to . The Kirchhoff node law follows by averaging graph path divergences. For the graph cycle law, let be the two-component spanning forests separating the terminals and the component containing . Deleting a tree-path edge and conversely adjoining an edge across a forest cut are inverse operations. Hence the mean signed current on an edge isThis is the gradient of , proving the graph cycle law. In particular . For an oriented existing edge , that edge is used by the tree graph path exactly when it belongs to the tree, and then has positive orientation. Thus its mean current is , giving the edge-inclusion formula for a uniform spanning tree by Ohm's law.
For an edge of conductance in a finite electrical network, its inclusion probability in the conductance-weighted uniform spanning tree is . The same formula holds for the wired limit using the limiting wired effective resistance.
Articles by others on the same topic
There are currently no matching articles.