第26卷(1996)第1期 ·75· 问题1确定每一批锁具的个数及装箱箱数。 问题2提出一种装箱和销售方案,使团体顾客不再或减少抱怨。 问题3采用所提出的方案,团体顾客的购买量不超过多少箱,就可以保证一定不 会出现互开的情形 问题4按原装箱办法,如何定量衡量团体顾客抱怨互开的程度(对购买一、二箱者 给出具体结果)。 上述问题有些已经得到较好的解决,而本文只是对问题3作些进一步的讨论 图论预备知识 个图G是指一个有序三元组(V(G),E(G),化),其中V(G)是非空的顶点集,E (G)是不与v(G)相交的边集,而9是关联函数,它使G的每条边对应于G的无序顶点 对(不必相异)。若e是一条边,而u和v是使得9(e)=uu的顶点,则称e连接u和v 顶点u和v称为e的端点 例如设V(G)={u,v,v,x},E(G)={e1,e2,e3,e}而9定义为 9(e1)=a,9(e2)=t,9(e3)=tu,G(e)=v。 这时G(V(G),E(G),9)就是一个图,且可用图形表示,如图 有时我们将图G=(v(G),E(G),9)简记 为:G=(V(G),E(G)),或G=(V,E)。一个 图,如果它既没有环也没有两条边连接同一对顶 点,称之为简单图。本文讨论的是简单图,下面 所说的图都指简单图。因为边总是和顶点联系在 起的,所以确定了顶点集和边集,也就确定了 个图 二部图(或称为偶图)是指一个图,它的顶 点集可以分解为两个(非空)子集X和Y,使得每条边都有一个端点在ⅹ中,另一个端 点在Y中。k部图是指这样的图,它的顶点集可分解为k个(非空)子集,使得任何一边 的两个端点均不在同一个子集中。 对任意集合A,记其元素个数为|A 设S是图H(V,E)的顶点集V的子集,若S中任意两个顶点在H中均不相邻(即 二点没有连边),则称S为H的独立集。H的一个独立集S称为H的最大独立集,如 果H不包含适合|S’|>{S|的独立集S'。H的最大独立集的顶点数称为H的独立 数,记为a(H)。 图H(V,E)的一个覆盖是指v的一个子集K,使得H的每条边都至少有一个端 点在K中。一个覆盖K称为H最小覆盖,如果H没有覆盖K使得|K”|<|K|。图 H的最小覆盖的顶点数称为H的覆盖数,记为R(H) 设图H(V,E),M是E的一个子集,M中的元素为H的边,并且M中任意两边 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved.© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved