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

题目

假设我们用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的，即为答案。