已知无向图G含有16条边,其中度为4的顶点个数为3,度为3的顶点个数为4,其他顶点的度均小于3。图G所含的顶点个数至少是()
A.10 B.11
C.13 D.15
无向图有16条边,每条边会给两个顶点带来1度,顶点度数之和:16*2=32 度数为4的顶点度数之和:3*4=12 度数为3的顶点度数之和:4*3=12 剩下的度数:32-12-12=8 要让顶点最少,则设剩下都为2度的顶点:8/2=4
所以总顶点数为:3+4+4=11
无向图边数的两倍等于各顶点度数的总...
用户登录可进行刷题及查看答案
无向图边数的两倍等于各顶点度数的总和。由于其他顶点的度均小于3,所以它们的度至多为2,可列出方程:
解得:
本题选B。
登录后提交答案