设图G内有20个节点和50条边。G图中有两个点vi和vj，它们的度分别为4和5。假设完全随机生成图G，vi 到 vj的边预期有多少条？

Consider a graph G, with 20nodes and 50edges. If there are two nodes vi and vj in the graph, degree of vi is 4, and degree for vj is 5. What is the expected number of edges from vi to vj?

Question

设图G内有20个节点和50条边。G图中有两个点vi和vj，它们的度分别为4和5。 假设完全随机生成图G，vi 到 vj的边预期有多少条？

Consider a graph G, with 20nodes and 50edges. If there are two nodes vi and vj in the graph, degree of vi is 4, and degree for vj is 5. What is the expected number of edges from vi to vj?

BlackTom AI · Accepted Answer

In the configuration model for a uniformly random graph with fixed degrees, the expected number of edges between two vertices equals (degree(vi) × degree(vj)) divided by the total number of stubs (2m). This gives the key formula used below.

1) Relevant knowledge points and concepts
- Each edge contributes two stubs, so total stubs = 2m. Here m = 50, so total stubs = 100.
- Under a random matching of stubs (configuration model), each stub of vi has probability proportional to degree(vj) of being paired to a stub of vj.
- The expected number of vi–vj edges is the sum over vi’s stubs of the probability each connects to vj’s stubs, giving E = d_i · d_j / (2m) (common approximation).

2) Step-by-step reasoning
- deg(vi) = d_i = 4, deg(vj) = d_j = 5, number of edges m = 50.
- Total stubs = 2m = 100.
- Expected number of edges between vi and vj ≈ (d_i × d_j) / (2m) = (4 × 5) / 100.

3) Intermediate calculations
- 4 × 5 = 20
- 20 / 100 = 0.20
- 0.20 expressed as a fraction = 1/5

(Note: a slightly more exact calculation using conditional probabilities without the 2m approximation gives 4 × 5 / (2m − 1) = 20/99 ≈ 0.20202, but the multiple-choice options use the simpler 1/5 = 0.20.)

4) Why the correct answer is correct
The formula captures that each of vi’s four stubs has about a 5/100 chance of attaching to one of vj’s five stubs; summing those four independent expectations yields 4×(5/100)=20/100=1/5.

5) Why the other options are incorrect
- 4/5 (0.8) is far too large; it would imply nearly one edge per stub, inconsistent with the sparse stub pool.
- 2/20 = 1/10 (0.1) and 1/20 (0.05) are too small given the product 4×5 = 20 and 100 total stubs; they do not reflect the correct ratio 20/100.

6) Conclusion
Using the standard random-stub argument gives expected edges = (4×5)/100 = 1/5. This matches the provided correct answer: 1/5.

类似问题

在一个图中，给定一个节点 v 的邻居中的连通对(pair)的数量与 v 的邻居中的所有对(pair)的数量之比率是 The ratio between the number of connected pairs of v's neighbors and the total number pairs of v's neighbors is called

在无向图 G(V, E) 中，|G| = n 和 |E| = m，度的总和是 In an undirected graph G(V, E), where |G| = n and |E| = m, the summation of degrees is

How many vertices does the Shiba model have?

Select the set that corresponds to the relation given in the arrow diagram below:

Given the adjacency matrix \( M \) of a directed graph, the number of paths of length 3 from vertex i to vertex j is found in matrix Answer Question 5[input]. Use proper notation (e.g., M^3).

A tree with 10 vertices has how many edges?

在社交媒体网络中，连通任意两个人的最短路径介于： In a social media network, the shortest path that connect any two people in the network is between

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单