Spanning Tree Edge Probability

Problem

Compute the probability that a given edge belongs to a uniformly random spanning tree of a connected undirected graph.

This probability equals the effective resistance between the edge endpoints when every edge is a unit resistor. Solve the grounded Laplacian system with one unit of current injected at u and extracted at v. edges is a list of [u, v] pairs and edge is the pair to test. Return a float.

Hint

Uniform spanning trees connect probability of inclusion to electrical resistance.

Test cases

case 1

in: [3,[[0,1],[1,2],[2,0]],[0,1]]

expected: 0.6666666666666666

case 2

in: [3,[[0,1],[1,2]],[0,1]]

expected: 1

case 3

in: [4,[[0,1],[1,2],[2,3],[3,0]],[0,1]]

expected: 0.75

case 4

in: [4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]],[0,1]]

expected: 0.5

Starter codePython

def spanning_tree_edge_probability(n, edges, edge):
    # Your code here
    pass

4 test cases · run your code against them in the editor