How to solve this problem ?

Revision en1, by liaojiqing, 2023-07-22 10:39:41

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.

Tags probability, math, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English liaojiqing 2023-07-22 10:39:41 680 Initial revision (published)