若某无向图一共有16条边，并且有3个度为4的顶点，4个度为3

[问答题]

若某无向图一共有16条边，并且有3个度为4的顶点，4个度为3的顶点，其余顶点的度均小于3，则该无向图至少有多少个顶点？

雅尔达winniebaby92

无向图16条边，每条边有两个度，所以总度数为32

32-3*4-4*3=8

剩余节点度均小于3，则最大为2 8/2=4

3+4+4=11

发表于 2018-03-01 10:11:35 回复(0)

郭新鹏

11个

首先度数是什么概念呢,对于无向图度数就是这个点连了多少边.

所以一个无向边是对首尾两个节点各贡献一个度数,所以16条边的无向图,节点总度数是32。

减去3个4度节点和4个3度节点,还剩8个度数,

其余节点的度数均不超过2,所以还剩至少4个节点

3+4+4 = 11

发表于 2017-10-16 16:07:28 回复(0)

提交观点

问题信息

图

上传者：城市里的养猫者

难度：

2条回答 6收藏 6383浏览

扫一扫，把题目装进口袋