搜搜考试网一道离散数学的图论题目,求详解,亲,thax!
来源：学生作业帮 编辑：搜搜考试网作业帮 分类：数学作业 时间：2024/05/28 00:58:07
一道离散数学的图论题目,求详解,亲,thax!
设无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点的度数均小于3,请问G中至少有几个定点?（答案是11）
请把详解,比如用到那些定理,计算过程写出来,
设无向图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个节点.