无向图G有23条边,度为4的顶点有5个,度为3的顶点有4个,其余都是度为2的顶点,则图G最多有( )个顶点。

admin2014-04-17  33

问题 无向图G有23条边,度为4的顶点有5个,度为3的顶点有4个,其余都是度为2的顶点,则图G最多有(    )个顶点。

选项 A、11
B、12
C、15
D、16

答案D

解析 顶点的度是指与此顶点相关联的边数,而每条边与两个顶点相关联。23条边最多有46个顶点(不排除多条边共享一个顶点),设图G中有n个顶点,则有4×5+3x4+(n一5—4)×2≤23x2,解得n≤16。
转载请注明原文地址:https://kaotiyun.com/show/sixi777K
0

最新回复(0)