关于离散数学平面图的两个问题.答得好的话会有加分哦!
1、设G是一个没有三角形的平面图.应用欧拉公式证明G中有一个顶点v,使得degv ≤3.
2、设G是一个没有三角形的平面图.应用数学归纲法证明G是4-可着色的.
人气:384 ℃ 时间:2020-05-28 19:57:25
解答
1.证明:采用反证法,设G中所有顶点的度数 >= 4.
设G中的顶点数为V,边数为E,面数为F则
则 根据欧拉公式 V-E+F=2.
又因为G是一个没有三角形的平面图,所以G中的每一个面至少由4条边组成(G中只有少于4条边的情况不用考虑,因为这种图形必然满足结论),因此 4F
推荐
- 平面图问题,初步组合分析问题
- 有关平面图的问题
- 平面图 欧拉公式 r = e - v + 2 这个公式中的 r 代表区域,但是怎么去找呢?如何判断?不知道该怎么找..
- 离散数学题:设G是(6,12) 的简单连通平面图,则G的面由多少条边围成,为什么?
- 在一幅比例尺是1比5000的平面图上,量的学校和超市的距离是8厘米.当把这两个地点画在另外一副平面图上时,它们的距离是5厘米,另外这幅平面图的比例尺是多少?
- 一个正方形分成六等份
- 英语翻译
- 两个数的积是第一个因数的15倍,是另一个因数的19倍,这两个因数的积是多少?
猜你喜欢