欢迎来到天天文库
浏览记录
ID:24180964
大小:71.84 KB
页数:4页
时间:2018-11-12
《一个图论问题的简单证明》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、一个图论问题的简单证明摘要:通过引入拓扑中的一个不变量__欧拉示性数来证明图论中的一个重要定理。关键词:库拉图斯基定理;可平面图;定理中国分类号:029文献标识码:A从库拉图斯基定理的证明以来,很多书本都引入这个定理,它也是证明一个图是否是可平面图的基本定理,同时也是一个平面图着色的基础。本文就是通过一种容易理解和简短的证明这个有用的定理.一、知识简介库拉图斯基定理图G是可平面图当且仅当G中既不含与K5同胚的子图,也不含与K3,3同胚的子IsI.定义1(点连通)设X是一个拓扑空间,X,yex,如果X中有一个连通子集同时包含x和y
2、,我们称点x和y是连通的.定义2(连通分支)设X是一个拓扑空间,对X中的点的连通关系而言的每一个等价类成为拓扑空间X的一个连通分支.二、定理的证明定理:完全图K5和二部图K3,3不能嵌入S2.1图2证明:先证完全图K5不能嵌入到S2.假设存在嵌入f:K5-S2,由于K5中三条边才能构成一个闭合回路(见上图1ABC就是一个回路),从而S2/f(K5)的每个连通分支至少要与K5的三条边相邻,同时K5的每条边只与至多2个连通分支相邻.考虑到K5—共有C25=10条边,这就意味着S2/f(K5)至多有[2X4+3]=6个连通分支,这里[
3、x]表示取整函数.同时S2/f(K5)的每个连通分支应该是一个盘,于是我们就得到了一种用圆盘沿着边粘出S2的方法,粘出来有5个顶点,10条边,至多6个面.因此我们有欧拉数2=x(S2)彡5+6-10=1,这是一个矛盾,也就是完全图K5不可能嵌入到S2.下面再证二部图K3,3也不可能嵌入到S2.假设存在这样的嵌入f:K3,3-S2,由于K3,3中四条边才能构成闭合回路(见图2中的A1B1A2B2A1就是一个回路),这是因为K3,3在同一层的3个顶点没有相互连接,从而S2/f(K3,3)的每个连通分支至少要与K3,3中的4条边相邻,
4、同时K3,3的每条边至多只与2个连通分支相邻.考虑到K3,3—共有3C13=9条边,这就意味着S2/f(K3,3)至多有[9X2+4]=4个连通分支.类似于K5的情形,此时我们粘出来有6个顶点,9条边,至多4个面.因此欧拉数2=x(S2)6+4-9=1,这是一个矛盾,也就是二部图K3,3也不可能嵌入到S2.参考文献:[1]Kuratowski,Kazimierz.Surleproblemedescourbesgauchesentopologie.Fund.MathinFrench,1930:271-283.[2]徐俊明.图论及其
5、应用[M].中国科技大学出版社,2010(03).[3]张先迪,李正良.图论及其应用[M].高等教育出版社,2005-02-01.[4]迪斯特尔.图论[M].4版.于青林,等译.北京:高等教育出版社,2013-01-01.[5]阿姆斯特朗.基础拓扑学[M].孙以丰,译.人民邮电出版社,2010-04-01.作者简介:邢振宇,硕士研究生,研究方向:计算机代数与代数几何。
此文档下载收益归作者所有