校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > UI专业知识 > 色彩
题目

假设我们用d=(a1,a2,….a5)表示无向无自环图G的5个顶点的度数,下面给出的哪组值是可能的

A.{3,4,4,3,1}

B.{4,2,2,1,1}

C.{3,3,3,2,2}

D.{3,4,3,2,1}

解答

正确答案是 B

首先要理解无自环是指一个顶点不能自己到自己,而不是图没有环,所以这题目的图是可以有环的。然后无向图边数最多和总度数最多的情况下,就是完全无向图,边数为E=n(n-1)/2条,总度数为边数的两倍即D=n(n-1)。所以只要边数小于等于E,度小于等于D,且总度数D是一个偶数,那么就都可以构成图。题目5个顶点,其完全无向图的边数为10,总度数为20,备选答案所有数字之和是偶数且不大于20的,即为答案。

C 3条回复 评论
京巴

所有度之和只能为偶数,不可能为奇数

发表于 2018-10-12 12:10:35
0 0
石头

有向图所有的入度之和等于出度之和。而无向图不分入度出度,所以总的度数和一定是相当于有向图的入度+出度=2*入度,这一定是个偶数。只有B选项中的和是偶数,所以选B

发表于 2018-10-12 12:09:50
0 0
Lee

因为是无向图,度数和为偶数;

发表于 2018-10-12 12:09:37
0 0