问答题
无向图G有16条边,有3个4度顶点,4个3度顶点,其余顶点的度均小于3,则图G至少有__________个顶点。【湖南大学2006】
【正确答案】
正确答案:11。无向图16条边,其度数为16*2=32。设无向图顶点数是n,根据已知条件,度为4和3的顶点度数是3*4+4*3=24,其余顶点度最大为2,个数是n一3—4,度数为(n一3—4)*2,故顶点度数之和等于24+(n一3—4)*2=2n+10,因为2,z+10>=32,所以,图至少有11个顶点。
【答案解析】
提交答案
关闭