早教吧 育儿知识 作业答案 考试题库 百科 知识分享

问一道图论题:设简单连通图G的结点数是15,其中8个点的度是4,6个点的度是6,一个点的度是8,证明G是非平面图.

题目详情
问一道图论题:
设简单连通图G的结点数是15,其中8个点的度是4,6个点的度是6,一个点的度是8,证明G是非平面图.
▼优质解答
答案和解析
我对图论也不是很熟悉,我试一下吧.提供给你参考.
证明:
首先,根据条件得到:
边数为:(4*8+6*6+8)/2=38
假设G是平面图
根据欧拉定理知道,面数等于:
38+2-15=25
根据假设,面的总长度是:38*2=76
所以,G的面有24个长度为3,1个长度为4
不可能有别的可能.
设度为8的结点为P
分两种情况:
1.P不在长度为4的面上.
设和P相连的八个点为:A1,A2,...,A8
根据假设.由A1,A2...,A8,P组成的子图为
如下:
A1,A2...,A8组成一个八边形.
P在八边型内部,P和A1,...,A8都有一条连
线.
和A1相连的有A2,A8,P
和A2相连的有A3,A1,P
...
和A8相连的有A1,A7,P.
剩下的六个点记为:B1,B2..,B6
首先,A1...A8里面必然有度为6的点.
否则,由B1,..,B6组成的子图是非平面图.
(这个通过欧拉公式可推出,此处从略)
不妨设A1为度为6的点.
设A1与B1,B2,B3相连.
必有点与A3连,且该点不可能是B1,B2,B3
否则,(比如是B1),P-A1-B1-A3为长度为四的面.矛盾
所以设与A3连的是B4
同理,设与A5连的是B5
设A7连的是B6
现在看B4这点.
根据上面分析,B4不可能与P,A1,A5,A6,A7,A8,中任意点连.
同时,B4不能和B1,B2,B3,B5,B6中任意点连,否则.(比如B6)
则,P-A3-B4-B6-A7-P
组成长度为5的面.矛盾.
所以B4的度为3,根据题意,矛盾.
所以排除这种情况.
2.P在长度为4的面上.
分析方法类似于1,己于人这里不再重复写.如果问题你补充.