题目
n 个结点的完全有向图含有边的数目()。A. n*nB. n(n+1)C. n/2D. n*(n-1)
n 个结点的完全有向图含有边的数目()。
A. n*n
B. n(n+1)
C. n/2
D. n*(n-1)
题目解答
答案
D. n*(n-1)
解析
步骤 1:理解完全有向图的定义
完全有向图是指在有向图中,任意两个顶点之间都存在一条有向边。这意味着每个顶点都与其他所有顶点之间有一条有向边相连。
步骤 2:计算无向图的边数
在无向图中,如果顶点个数为 n,则最多有 Cn2=n(n-1)/2 条边。这是因为每个顶点可以与其他 n-1 个顶点相连,但每条边被计算了两次(一次从顶点 A 到顶点 B,一次从顶点 B 到顶点 A),所以需要除以 2。
步骤 3:计算有向图的边数
在有向图中,由于每条边都是有方向的,所以每条边只被计算一次。因此,有向图的边数是无向图边数的两倍,即 n(n-1)。
完全有向图是指在有向图中,任意两个顶点之间都存在一条有向边。这意味着每个顶点都与其他所有顶点之间有一条有向边相连。
步骤 2:计算无向图的边数
在无向图中,如果顶点个数为 n,则最多有 Cn2=n(n-1)/2 条边。这是因为每个顶点可以与其他 n-1 个顶点相连,但每条边被计算了两次(一次从顶点 A 到顶点 B,一次从顶点 B 到顶点 A),所以需要除以 2。
步骤 3:计算有向图的边数
在有向图中,由于每条边都是有方向的,所以每条边只被计算一次。因此,有向图的边数是无向图边数的两倍,即 n(n-1)。