作业帮一道离散数学的图论题目,求详解,亲,thax!设无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点的度数均小于3,请问G中至少有几个定点?（答案是11）请把详解,比如用到那些定理,计算过程写出来,
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/11 19:19:51
一道离散数学的图论题目,求详解,亲,thax!设无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点的度数均小于3,请问G中至少有几个定点?（答案是11）请把详解,比如用到那些定理,计算过程写出来,
一道离散数学的图论题目,求详解,亲,thax!
设无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点的度数均小于3,请问G中至少有几个定点?（答案是11）
请把详解,比如用到那些定理,计算过程写出来,
一道离散数学的图论题目,求详解,亲,thax!设无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点的度数均小于3,请问G中至少有几个定点?（答案是11）请把详解,比如用到那些定理,计算过程写出来,
这个很好理解,首先度数是什么概念呢,对于无向图度数就是这个点连了多少边,所以一个无向边是对首尾两个节点各贡献一个度数,所以16条边的无向图,节点总度数是32,减去3个4度节点和4个3度节点,还剩8个度数,其余节点的度数均不超过2,所以还剩至少4个节点哈哈,加起来是3个4度节点和4个3度节点和4个2度节点,至少11个节点,另外,通过画图确实得到了这样的图,所以证明出至少有11个节点.
由握手定理可知：
共有2x16=32个度数。由于有3个4度，4个3度顶点。即有3x4+4x3=24个度数。
即余下顶点共有32-24=8个度数，那么接下来就考虑余下的有几个顶点：
因为其余顶点度数小于3，即是0、1或者2，即余下的最多是无穷个顶点，最少是4个顶点。
考虑到奇度数的顶点为偶数（4），所以上面可以是4个顶点，
即至少有4+4+3=11个顶点
全部展开
由握手定理可知：
共有2x16=32个度数。由于有3个4度，4个3度顶点。即有3x4+4x3=24个度数。
即余下顶点共有32-24=8个度数，那么接下来就考虑余下的有几个顶点：
因为其余顶点度数小于3，即是0、1或者2，即余下的最多是无穷个顶点，最少是4个顶点。
考虑到奇度数的顶点为偶数（4），所以上面可以是4个顶点，
即至少有4+4+3=11个顶点
希望能帮助你。。。。
收起
题目为： 含有5个结点，3条边的不同构的简单图有___个。 A 2 B 3 简单图：无环、无多重边的图。同构图：两个同阶图（点数为图的阶），若