78 数学的实践与认识 了一些困难。首先,矩阵A在计算机内存中放不下,所以我们在程序中不构造矩阵A, 而是每次都去判断二锁具是否互开,为了提高程序的效率,求出每个锁具所连边的边数 (在图论中此数称为顶点的度数)分别放在数组 ouedn(2940]和jedn2940]中。其次 数组ou2940〕,j[2940中一个元素表示成一个整数:10001+1000h2+100h3+ih +h5,此数可能超出微机整数所允许的范围,所以我们在程序中将一个锁具分开故在两 个整数型变量中,即将ou[2940分开装到ou2940和ou2(2940两个数组中,同样将 2940]分成j1[2940和j2(2940两数组 程序框图见附录 程序运行速度较快,在386微机上只需要8分钟,且得出满意的结果,找出了一个 边数为2940的对集。 定理4的证明因锁具图G(V,E)中V|=5880,由定理3,显然锁具图G(v, E)的最大对集的边数为2940。再由定理1、2易得:a(G)=2940 六、推广 6.1槽数增加为6的情形 将引言中的问题稍作改变:即将锁具槽的个数由5改变为6,其他条件不变,再来研 究独立数的问题 我们用上述的方法,将程序稍作变动得出下面的结果 批锁具的总数为:35080 总槽高为奇数的锁具数为:17720 总槽高为偶数的锁具数为:17360 找出了边数为17360的对集,在386微机上运行时间为140分钟 类似地可以推得:此时的锁具图的独立数为:17720 6.2槽高的范围改为{1,2,3,4,5,6,7}时的情形 将引言中的问题改变为:锁具的每个槽高在{1,2,3,4,5,6,7}中取一数值,其 它条件不变时,同样可考虑此时锁具图的独立数。我们得出下述结果: 批锁具的总数为:993 总槽高为奇数的锁具数为:4942 总槽高为偶数的锁具数为:4994 将程序再作修改,也找出了边数为4942的对集。在386微机上运行时间为11分 钟。 类似地可以推得此时的锁具图的独立数为:49 6.3定理4的另一种证明 定理4的又一种证明:对锁具图G(V,E),因P即是一独立集,所以a(G)≥2940。 又因定理3,锁具图G(V,E)的边数为2940的对集M包含了锁具图G的所有顶点(顶 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved.© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved