K(7,3)的若干性质.doc

对Kneser图的性质的研究与探索对K(7,3)的若干性质研究浙江师范大学学生课外科技活动第十一期课题（论文）目录摘要11引言12的若干性质22.1阶数22.2正则度32.3边数32.4围长32.5周长52.6拟泛圈性62.7直径82.8是-图102.9是-图102.10Hamilton圈分解102.11边染色132.12边独立数、边覆盖数、独立数、覆盖数132.13点染色152.14是Euler图152.15不是可平面图163的若干性质173.1阶数173.2正则度173.3边数173.4围长173.5直径193.6是-图，-图193.7可遍历性194结束语19对Kneser图的性质的研究与探索对的若干性质研究杨巧珍初阳学院 数学与应用数学综合理科071 07990111 指导老师：王应前（教授）【摘要】 Kneser图是图论中一类十分重要的图,这是因为许多关于集合的计数以及计算问题可以转换为此类图中的问题加以探讨. 令人着迷的Petersen图就是Kneser图. 虽然,已有若干文献对Kneser图的一系列性质: 如连通性、Hamilton问题、染色问题进行了研究,但远远不够完整.为了提示更多更深刻的性质,对阶数较小的Kneser图进行系统的研究也很有意义.本文对Kneser图家族中的第三个平凡的图即展开系统研究,确定了的一系列重要参数,进而又对一般的图的一些简单性质进行整理研究,这一工作将有助于揭示较大的更一般的Kneser图的深刻性质.【关键词】；图；直径；围长；周长；连通性；色数；染色；泛圈性；Hamilton圈1 引言图论起源很早，远在十八世纪就出现了图论问题，如著名的哥尼斯堡七桥问题就是当时很有名的图论问题。而随着理论与科技的发展，目前图论在物理、化学、运筹学、计算机科学、控制论、网络理论等许多学科领域都有应用。研究并掌握各种图类的性质与规律，是图论学科的基础。Kneser图是图论中一类重要的图类, 这是因为许多关于集合的计数以及计算问题可以转换为此类图中的问题加以探讨。一般地，令为的所有元子集所形成的集合, ,则称为Kneser图. 对其各种性质和规律的研究，具有一定的重要意义.在本文中,把作为研究对象, 进一步研究的一类Kneser图的若干性质. 显然, 当时, 为一个3-圈.当时,人们研究发现, 即为Petersen图,它是一个特别有趣的图. Petersen图是以丹麦著名数学家Peter Christian Julius Petersen的名字命名的.它的首次出现是在1886年Alfred Bray Kempe的一篇论文中,Petersen图被Petersen作为反例引出,从而奠定了该图在图论中的地位和基础. 当时，的顶点数、边数会越来越多, 不容易研究. 因此，本文主要先对的情况进行研究，即对进行研究. 在对进行较充分的研究后，会对的一些简单性质进行整理研究.由Kneser图的定义可知，令为的所有元子集所形成的集合, , 则称此Kneser图为. 据的定义, 同时参考即Petersen图的画法, 可画出如下图. 图1-12 的若干性质2.1 阶数由的定义可知, 的顶点数为的所有-元子集的个数.而的所有-元子集的个数为,故的顶点数为35个, 即的阶数为35.2.2 正则度 易见Kneser图是正则图, 特别也是正则图. 由的定义, 与中任一顶点相邻的顶点所对应的集合与对应的集合相交为空集. 因此, 任一顶点的度数为.2.3 边数由前面结论, 的阶数为35, 且是4正则的, 因此的边数为.2.4 围长图中最短圈的长度叫做的围长, 记作.在图1-1中可以找到一个6-圈, 即有一个:.性质1：的围长为6.证:由于简单图中最小的圈就是，如果能证明中无,-圈，即证明了的围长为6.令 先证图中不含-圈(如图2-1).则有.图2-1设,根据的定义，则有图中含有-圈，即有图中结构，即有,以及 显然这与相矛盾！故图中不含-圈. 下证图中不含-圈. 假设图中含有-圈(如图2-2).则有,并且而(若不然就产生了-圈).图2-2根据的定义, 有.由上述的分析，可得且，且 以及和.或，或.若, 且, 矛盾！若, 且又且，, 矛盾！故假设不成立，即图中不含-圈. 下证图中不含-圈.假设图中含有-圈(如图2-3).则有,.并且此-圈中除上述条边外无其它边(若不然就会产生了图2-3或-圈).根据的定义, 有显然有，否则之间无公共的相邻的顶点. 同理有.又有这显然与矛盾！故假设不成立，即图中不含-圈.综合，可以得到中不含,-圈, 因此，中最小的圈为, 即的围长就是6，也即.2.5 周长图中最长圈的长度叫做的周长, 记作.显然在中能找到一个, 如图2-4所示. 又因为一共有35个顶点, 故的最长圈是, 即，也即是Hamilton图.图2-4中的一个2.6 拟泛圈性若对于每个介于，之间的整数, 图中都至少有一个, 则称图是泛圈的. 若对于每个介于，之间的整数, 图中都至少有一个, 则称图是拟泛圈的. 性质2：是拟泛圈图.证：由于在中, 没有3,4,5-圈, 所以它不是泛圈图. 但注意到在中从到, 对于每个介于6到35之间的整数, 图2都至少有一个, 具体如下:其中，表示顶点对应为的点.因此, 是拟泛圈图.2.7 直径若图中任意两个顶点之间都有一条路，则称图是连通的。设图是连通的, 任给, 把连接的最短路的长度, 叫做间的距,记作. 把的最长的距离叫做的直径, 记作或, 即.性质3： .证：令 ，要证.设,.若, 则依的定义，有故有.若 不妨设,其中互不相同则可令之间无公共的相邻的顶点, 所以之间的最短路长大于2.令,显然有，.即, , .故有.若不妨设,. 令.则，.故有.，有. 另一方面要证，s.t. .令，则有不存在, 使得，即.综合可得，.一般地，对于图， M. Valencia-Pabon,和J.-C.Vera已经得到了关于图的直径的计算公式，即 其中记成，而图记为，则有顶点集，边集.当然可根据此直径计算公式得到的直径，对于，公式中的，代入计算公式得，此结果与上述证明的结果相同。2.8 是-图设, 若不连通, 则称为的一个点割. 具有个点的点割, 叫做-点割. 当为非完全图时, 把叫做的(点)连通度. 若,则称是极大(点)连通的, 简称为-图,其中为的最小度.定理1：若是连通的点可迁图, 且不含有, 则性质4：是-图.证：Kneser图是点可迁图, 当然也是点可迁图, 而且由前面证明得中不含, 当然就不含有, 这样由定理1可得, , 即是-图.2.9 是-图设, 若不连通, 则称为的一个边割. 令则为的边连通度. 即为中最小的边割中所含有的边数.若, 则称是极大边连通的, 或-图.定理2：对任意图，有.性质5：是-图.证：由性质4及定理2容易得到, , 即, 即是-图.2.10 Hamilton圈分解如果图中的一个回路C含有的所有顶点, 那么这个回路C称为的一个Hamilton回路. Hamilton回路简称为回路. 包含的所有顶点的路称为Hamilton路. 而称含有Hamilton回路的图为Hamilton图, 简称为图.性质6：是Hamilton图.如图2-7可知, 可分解为2个Hamilton3圈. 有很多种Hamilton圈分解的方式，现分出了40种（见附录,在附录中又给出了3种分法，其它同理）.圈1: (如图2-5)圈2: (如图2-6)圈1(图2-5)圈2(图2-6)图2-72.11 边染色设图, 是一个映射, 若在图中相邻且有, 则称为的一个-边染色, 又称是-边可染的. 的边染色所需的最少的颜色数称为的边色数,记为,简记为.定理3(Vizing定理) : 若图是简单图, 则 .若, 则称图是第一类的; 若, 则称是第二类的.定理4：若, 则图是第二类的, 即. 证：由上述定理知，或, 要证此定理成立，即证. 假设, 即的边集可剖分成个匹配. 由于每个匹配中至多含有条边, 从而有, 矛盾！所以，.推论1：任意奇数阶正则图是第二类的.证：设为奇数阶正则图, 为-正则. 据握手引理, 有为偶数. 并且据上述定理，有图是第二类的，即任意奇数阶正则图是第二类的.性质7：是第二类的，即有的边色数.证：由定义知的阶为35，并且是4-正则图, 根据上述推论知是第二类的, 即有的边色数.2.12 边独立数、边覆盖数、独立数、覆盖数设是一个图, . 若中的点两两不相邻, 则称为的一个独立集. 若中不存在独立集, 使得, 则称为的一个最大独立集. 把最大独立集中所含有的顶点的个数叫做图的独立数, 记作.设. 若的每条边至少有一个端点属于, 则称为的一个(点)覆盖. 若中没有覆盖, 使得, 则称为的一个最小点覆盖. 最小点覆盖中所含有的顶点的个数, 叫做的覆盖数, 记作.设是一个无环图, 把的一个匹配叫做边独立集. 最大边独立集中所含有的边的条数叫做的边独立数, 记作.设, 若的每一个顶点必是中的某条边的端点, 则称为的一个边覆盖. 把的最小边覆盖所含有的边的条数叫做的边覆盖数, 记作.定理5：对任何图, 有.定理6：(Gallai, 1959)若, 则.定理7：设图是没有孤立顶点的阶图, 那么.性质8：对于有： 独立数： 覆盖数： 边独立数： 边覆盖数：证: 设为的一个独立集, 则中的点两两不相邻, 即中的点对应的集合两两之间都含有一个或两个相同的元素. 易知当中的点所对应的集合均含有同一个相同的元素时,则为的一个最大独立集.故不妨设这个相同的元素为1, 则最多为. 即.因为, 由定理5可得.因为的阶为35, 所以由定理7得, 又因为 是一个包含17条边的独立集, 所以.2.13 点染色性质8：的点色数.证：1）由的拟泛圈性知道图中存在奇圈，而因为所以有的点色数.2）而是可以用三种颜色进行正常染色的，具体的染色方案如图2-8所示.图2-82.14 是Euler图若一个连通图中存在一条经过每条边的闭迹,(称为Euler闭迹),则称为一个Euler图,简称为E图.定理8：设为一个非平凡的连通图, 则下面的命题是等价的. 为一个Euler图; 的每个点均为偶数度; 的边集可划分为若干个圈.证: .设为图的一条Euler闭迹, 对于中的任意一点,若点在中出现了t次,则点在中的度为偶数.由于为连通且非平凡图，并且每个点均为偶数读，故, 即中至少有一个圈,令,可见的每个点均为偶数度。若为空图,则命题成立. 若为非空图, 再去掉中的一个圈, 如此下去, 直至得到空图为止. 因此的边集可划分为若干个圈之并.设为的边集划分中的一个圈,若中只有此圈,则命题成立,否则, 中存在圈,使得与至少有一个公共点,从而存在一条闭迹恰好包含和.如此下去,得到一条包含的按边集划分的所有圈的闭迹,从而包含了的所有边,即为一个Euler图.性质9：是Euler图.证：可分解为2个Hamilton圈, 故由上述定理可知是Euler图.2.15 不是可平面图如果能与这样的一个图同构, 其中的顶点在同一平面上, 而的边只能在端点处相交(即能够画在一个平面上而使得任何两条边都不会交叉), 就称为平面图, 而称为的一个平面嵌入, 或称为在平面上的实现.如果在图的一条或多条边中插入一个或多个度为2的顶点得到一个新图, 我们称这个新图为图的一个细分. 显然, 一个平面图的每个细分都是平面图，一个非平面图的每个细分都是非平面图.定理9(Kuratowski定理) ：一个图是平面的当且仅当不含, 或者,的一个细分作为子图.性质10：不是可平面图.图2-9证：据图1-1, 显然图2-9是的一个子图, 而图2-9是完全图的一个细分, 所以根据定理9可得图不是可平面图.3 的若干性质3.1 阶数由图的定义可知, 的顶点数为的所有-元子集的个数. 而的所有-元子集的个数为, 故的顶点数为, 即的阶数为.3.2 正则度因为Kenser图是正则图, 因此也是正则图. 又由的定义, 与中任一顶点相邻的顶点所对应的集合与对应的集合相交为空集. 因此, 图的任一顶点的度数为.3.3 边数由前面结论，图的阶数为, 且是-正则的. 因此, 据握手引理有图的边数为, 即的边数为.3.4 围长由的定义, 的所有顶点对应的元素集合为.1) 当时, 是一个圈, ;2) 当时, 就是Peterson图, ;3) 当时, 由前面的研究得，;4) 当时, 可证得，;证明：只证第4条. 令, 显然图中无环也无重边. 图无3圈. 假设图中有3圈. 显然有, , , , 故有, 矛盾！ 图无4圈. 假设图中有4圈. 显然有, , , , , , 所以, 有,矛盾！ 图无5圈. 假设图中有5圈. 显然有, 及, 否则, 也即, 则, 这样就不存在与,都相邻的顶点, , 同理也有. 所以, 有 又有, , 矛盾!综合有, 图无3,4,5-圈.下证图含有6-圈. 取, , , , 显然, 以上六个点互不相同, 且都是得顶点，并且这六个点刚好构成一个6-圈.综上所述, 当时, 的围长为6, 即.3.5 直径 性质1：.证：利用公式(1-1), 可容易得到上述结论3.6 是-图，-图性质2：是-图，-图.证：因为是点对称图, 每个顶点在图中由同等地位, 所以是点可迁图, 这样据定理1可得-图. 又据定理2可得, 是-图.3.7 可遍历性性质3：当为奇数时, 是Eurler图；当为偶数时, 不是Eurler图.证：因为当为奇数时, 的度数为是偶数, 所以由定理8可知是Eurler图; 同理, 当为偶数时, 不是Eurler图. 由定理8进一步有, 当为奇数, 可能有Hamilton圈分解, 而当为奇数, 肯定不能进行Hamilton圈分解.4 结束语通过本课题的研究，虽然只是对Kneser图家族中具体的一个非平凡图的性质进行研究整理，并没有抽象到一般的Kneser图中，但在此次研究过程中也有一定收获，首先最大的收获是给出图的画法，进一步了解到Kneser图是一种极漂亮的图类，引发更多的人对Kneser图的研究兴趣；其次找到了图40种Hamilton圈分法，也即找到了80个不同的Hamilton圈(只是部分)，可以通过这40 种分法找出某种规律进而确定的Hamilton圈分解种数（这将在后续研究中进一步进行）。此外，本课题的研究对本人以及组员具有深刻意义，本课题的研究与探索不