Lesson 6

Consider the following random complete graph with \(n\) vertices: each edge (independently) is assigned a random weight, chosen uniformly from the interval \([0,1]\). For any spanning tree of this graph, its expected total weight will be equal to \(\frac{n-1}{2}\). But what will be the expected weight of the minimum spanning tree in this graph? Try to guess the answer and look at the simulation of a random experiment given below. Then compare your guess with the answer.

from itertools import combinations
from networkx import Graph, minimum_spanning_edges
from random import random

n = 1000

graph = Graph()
for i, j in combinations(range(n), 2):
    graph.add_edge(i, j, weight=random())

print(sum([e[2]["weight"] for e in minimum_spanning_edges(graph)]))