关于离散数学平面图的两个问题。答得好的话会有加分哦！
1、设G是一个没有三角形的平面图。应用欧拉公式证明G中有一个顶点v,使得degv≤3。2、设G是一个没有三角形的平面图。应用数学归纲法证明G是4－可着色的。...
1、设G是一个没有三角形的平面图。应用欧拉公式证明G中有一个顶点v,使得degv ≤3。
2、设G是一个没有三角形的平面图。应用数学归纲法证明G是4－可着色的。 展开
2、设G是一个没有三角形的平面图。应用数学归纲法证明G是4－可着色的。 展开
1个回答
展开全部
1.证明：采用反证法，设G中所有顶点的度数 >= 4.
设G中的顶点数为V，边数为E，面数为F则
则 根据欧拉公式 V-E+F=2.
又因为G是一个没有三角形的平面图，所以G中的每一个面至少由4条边组成（G中只有少于4条边的情况不用考虑，因为这种图形必然满足结论），因此 4F <= 2E (因为每一条边与2个面相关)。
将4F <= 2E 带入 V-E+F=2 可得E+4<=2V。
因为G中所有顶点的度数 >= 4,所以可得 4V <= 2E 即 2V <= E, 这与E+4<=2V矛盾，因此，G中至少有一个顶点v,使得degv ≤3。
2.不知道你说的G是4－可着色的 意思是指 G的顶点是4－可着色的 还是 G的面是4－可着色的？
设G中的顶点数为V，边数为E，面数为F则
则 根据欧拉公式 V-E+F=2.
又因为G是一个没有三角形的平面图，所以G中的每一个面至少由4条边组成（G中只有少于4条边的情况不用考虑，因为这种图形必然满足结论），因此 4F <= 2E (因为每一条边与2个面相关)。
将4F <= 2E 带入 V-E+F=2 可得E+4<=2V。
因为G中所有顶点的度数 >= 4,所以可得 4V <= 2E 即 2V <= E, 这与E+4<=2V矛盾，因此，G中至少有一个顶点v,使得degv ≤3。
2.不知道你说的G是4－可着色的 意思是指 G的顶点是4－可着色的 还是 G的面是4－可着色的？
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
