Question

设无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点的度数均大于3,请问G中至多有几个顶点?

设无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点的度数均大于3,请问G中至多有几个顶点?搜索
为什么是 3×4＋4×3＋(n-7)×4 ≤ 2×16 ？
题目只说了大于3，为什么 n-7 乘以 4 ？为什么不是 5 或 6

Answer 1

对于无向图度数就是这个点连了多少边，所以一个无向边是对首尾两个节点各贡献一个度数，所以16条边的无向图，节点总度数是32，减去3个4度节点和4个3度节点，还剩8个度数，其余节点的度数均不超过2。

所以还剩至少4个节点，加起来是3个4度节点和4个3度节点和4个2度节点，至少11个节点，另外，通过画图确实得到了这样的图，所以证明出至少有11个节点。

扩展资料：

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

【例】无序对(vi，vj)和(vj，vi)表示同一条边。

如果a是集合A的元素，就说元素a属于集合A，记作a∈A。符号“∈”表示属于，读作“a属于A”，或读作“A含有a”；如果a不是集合A的元素，就说a不属于A。

给定有向图G=(VE)，并且给定该图G中的任意两个结点u和v，如果结点u与结点v相互可达，即至少存在一条路径可以由结点u开始，到结点v终止，同时存在至少有一条路径可以由结点v开始，到结点u终止。

对于一个无向图来说，如果它是连通的，那么它的任意两个顶点之问必存在一条路径，因此，通过这一路径可从一个顶点“到达”另一个顶点，若从顶点“可以到达u，则从u也可以到达“，也即v和u之间是互相可以到达的。

对于有向图，情形就不同了，因为存在从u到v的路径，并不蕴涵也存在从v到u的路径。

参考资料来源：百度百科--无向图

Answer 2

这个很好理解,首先度数是什么概念呢,对于无向图度数就是这个点连了多少边,所以一个无向边是对首尾两个节点各贡献一个度数,所以16条边的无向图,节点总度数是32,减去3个4度节点和4个3度节点,还剩8个度数,其余节点的度数均不超过2,所以还剩至少4个节点哈哈,加起来是3个4度节点和4个3度节点和4个2度节点,至少11个节点,另外,通过画图确实得到了这样的图,所以证明出至少有11个节点.

追问

其余节点的度数均不超过2 ？
可是题目说了其余结点的度数大于3

Answer 3

我们知道无向图的度数之和为边数的两倍，因此16条边共有32个度。减去3*4+4*3 还剩8个度 你看其余顶点度数均大于3 此时当为剩余每个顶点为4度时边最少，因此还剩有2个点
3+4+2 9个顶点

Answer 4

要使得节点数目尽可能多，则剩余的每一个的度数均要最小（这个易得到），由于每个点的度数要大于3，所以度数最小只能取到4，所以就是*4.

Answer 5

因为是至多有几个顶点呀，所以其他顶点度数越小，G的顶点越多