早教吧作业答案频道 -->数学-->
问一道图论题:设简单连通图G的结点数是15,其中8个点的度是4,6个点的度是6,一个点的度是8,证明G是非平面图.
题目详情
问一道图论题:
设简单连通图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,己于人这里不再重复写.如果问题你补充.
证明:
首先,根据条件得到:
边数为:(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,己于人这里不再重复写.如果问题你补充.
看了 问一道图论题:设简单连通图G...的网友还看了以下:
一列火车通过一座560米长的大桥用45秒然后又以同样的速度通过另一座380米长的大桥用了36秒求火 2020-04-07 …
1.一列火车通过一座长530米的桥需40秒钟,以同样的速度穿过380米的山洞需30秒钟,求这列火车 2020-04-07 …
苯甲酸(C3H5COOH)是常见的食品防腐剂.某同学准备惊醒试验验证苯甲酸具有酸的某一通性,下列物 2020-05-13 …
英语翻译1.这做古庙几乎成为一堆废墟了.(fallintoruin)2.进入这做建筑物的唯一通道是 2020-05-16 …
黑海通往地中海的唯一通道是()A.马六甲海峡B.土耳其海峡C.苏伊士运河D.霍尔木兹海峡 2020-05-16 …
地理好的进来1.十六条战略要道的???位于瑞典与丹麦之间,是通往北海和???的门户,也是俄罗斯波罗 2020-05-16 …
'台湾海峡是沟通东海和南海的唯一通道’是什么意思?它并不大,没有大面积覆盖东海和南海的接口,为什么 2020-05-17 …
用access翻译:大雪切断了通向这个村子的唯一通道 2020-05-17 …
这一类的数学题一列火车通过一座长456米的大桥需要80秒,用同样的速度通过一条长399米的隧道要7 2020-05-17 …
光线通过一块玻璃板,其强度将失掉10%,现将6块玻璃板叠加制成玻璃墙,求光线通过该玻璃墙后的强度为 2020-06-19 …