Блог пользователя liaojiqing

Автор liaojiqing, история, 10 месяцев назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится