关于pku一道期中考试题,老赵发起的问题(更新) |
您所在的位置:网站首页 › 如何求点连通度和边连通度的关系 › 关于pku一道期中考试题,老赵发起的问题(更新) |
证明3-正则图的点连通度等于其边连通度。 这道题的证明应该是: 设G是3-正则图,分3种情况讨论: 1.G是非连通图(即每个连通分支为3-正则图),此时边连通度为0,点连通度也为0,即命题成立。 2.G是含桥的简单连通图,则此时边连通度为1,点连通度也为1,即命题成立。 3.G是不含桥的简单连通图, a.不含长度大于3的圈时,边连通度为3,点连通度为3; b.含长度大于等于4的圈时,边连通度为2,点连通度为2; a.证明如下: 这里前两种情况显然,易知,G为不含桥的3-正则连通图时边连通度为3,下面只证明第3种情况的点连通度为3:
点连通度显然不大于3,假设G的点连通度大于3,则G中任意去掉3个顶点后,G仍然是连通的。v是G的任一顶点,与v相邻的顶点只有3个,去点这3个后G不连通,与假设矛盾!
点连通度显然不小于3,假设G的点连通度小于3,则G中任意去掉点与v相邻的2个顶点后,G的连通性必然遭到破坏,但是与v相邻的顶点有3个,G的连通性没有遭到破坏,矛盾。 b.证明如图: 去掉边{}即得到破坏原图连通性,则边连通度=2. 此处关于b情况,感谢iamjw指正。 ---------------------------------------------------------
PS.2007年真题第三.4: 是否存在4-连通的3-正则图?为什么? 答案:不存在。证明仿照上面的证明。 --------------------------
或者上面G为不含桥的a情况的3-正则连通图时点连通度为3的证明可以用构图法来证明:
或者上面G为不含桥的a情况中3-正则连通图时点连通度为3可以利用定理这么证明:(比较麻烦)
证明:令G为n阶不含桥的3-正则连通图,则n>3.
当n=4时,G为K4,其点连通度为3显然。 下面证明n>4时,命题成立。 当n>4时,n阶3-正则连通图的边连通度必为3,根据定理 知:k=入=3(因为k>=2*3-n+2=8-n,且n>4,则k>=3) 故:k=入=3 即3-正则连通图的点连通度等于其边连通度。 --------------------------------------------- 相关定理的补充:
由定理7.12也可以得到边连通度为3。 感谢老赵及时纠正。
构图法,用归纳去证,发现在证明当n+1阶3-正则图的点连通度为3,在n阶3-正则图点连通度为3的基础上去证明时,我需要在n阶3-正则图基础上增加一个顶点,但是这样的话,是不行的,因为n阶已经是3-正则图了,再加一点v,必然存在度数大于3的顶点,所以需要加工假设中是命题成立的n阶3-正则图,把n个顶点都去掉一边后,然后这n个顶点都与这个v点相连,这样也可以证明,因为度数没有增加没有减少,故用构图法可以实现这个证明。 --------------------------------- 当G为不含桥的3-正则连通图时(受2007年真题的启发) |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |