第26卷(1996)第1期 ·79 点总数为V|=5880),若将M的每边分别放入一个抽屉中(共有2940个抽屉),则相 应地,锁具图G的顶点放入这2940个抽屉,而每个抽屉里的二顶点都有连边。由抽屉 原则,从V中任取子集V,若|V≥2941,必然有两个元素在同一抽屉中,即有两个 元素之间有连边,所以V不是独立集。所以得a(G)≤2940 由上述两方面得a(G)=2940 注1此证明方法不需要定理1,定理2。 注2此证明方法有局限性,不适合上面1、2两种情形的锁具图。 参考文献 1.J.A.邦迪、U.S.R默蒂著,图论及其应用,科学出版社,北京,1984年。 附录 求锁具图对集程序的框图 按Toal值从小到大生成每个锁具,并分别顺序将总槽高 Total为偶数的锁具放入oa2940 中,将总槽高 Total为奇数的锁具放入n(2940)数组中 计算每个锁具的度数并分别放入数组 ouedn2940],iedn(2940 For K= 2939 To 0 step-1 从 ouedn(1到 ouedn [K中找最小的数,用变量 minou记其序号若最小数<=0,则程序打印 出错信息后结束 找j(1〕到n(K〕中与 ou minor连边的锁,若连边,则iedn[i-1,并求这些与ou nnow)连边的锁中 lied nli)最小的锁,记其序号为minj i〔minj与jK)交换,iedn(minn与 jiedu(K)交换, ou minot)与aK〕交换, outdo(m ou]与oedn(K〕交换 屏幕显示找到的一对锁具oK〕,jK〕,及已找到的锁具对数2940-K 将数组a2940和n[2940按总槽高 Total顺序输出到磁盘文件中 注1此框图略去了某些细节。如ou[2940)在程序中是分为二数组o1(2940和ou2(2940)的等 2 O1995-2004 Tsinghua Tongfang Optical Disc Co, LId. All rights reserved.© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved