liaojiqing's blog

By liaojiqing, history, 16 months ago, In English

Given a complete graph with n (n<=40) points, each edge has a certain probability of existing or not. For the existing edges, the weight is an integer between 1 to k (k<=4), where k is the maximum possible edge weight.

The task is to calculate the probability that the graph is connected and the size of the minimum spanning tree is exactly s for all s satisfying n-1 ≤ s ≤ k(n-1).

Specifically, we use p0 to denote the probability of an edge not existing, p1 to denote the probability of an edge having a weight of 1, p2 the probability of an edge having a weight of 2, and so on, with pk denoting the probability of an edge having a weight of k.

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it