数学的实践与认识 在图H中没有公共的端点,则称M为H的对集(或匹配)。若H没有另外的对集M, 使M'|>|M|,则称M为H的最大对集。 三、建立模型 定义锁具图:G=(V,E),其中,V为顶点集,V中一顶点表示一个锁具,即V是 批锁具的全体。E为边集,对V中任意两点,当且仅当它们所代表的锁具能够互开 时,则用一条边将此二点连接。 为了方便,用五元数组来记一个锁具 其中h;(=1,2,3,4,5)为锁具的第i个槽的高度,并记 Total 称之为此锁具 的总槽高。根据每个锁具的总槽高 Total值,可将锁具图G(V,E)的顶点集V分为20 个子集,分别记为 每个子集的元素个数如下表 集合中元素个数2050120162251322405508539563 集合中元素个数563 则A(i=8,9,10,…,27)具有下面两条性质: A,是图G(V,E)的独立集G=8,9,10,…,27)。 2.A中的元素只可能与A-1或A+1中的元素有连边。所以锁具图G为20部图 为了解决问题,我们将V分成两个集合 A,, Q 显然,P,Q都为图G的独立集,即G(V,E)为二部图 我们应注意到下面两点: 1.一批锁具的个数即是锁具图G(V,F)的顶点数|Vv=5880 2.从一批锁具中取出一些锁具构成集合K,要求K中任意二锁具不能互开,则K 是锁具图G(V,E)的独立集。所以求解问题2和问题3就要深入研究独立集。因而锁具 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved.© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved