组合数学-第十三节：相异代表系.doc

第7章 相异代表系7.1 引论我们先来看一个例子。现有6名职员和6项工作，每个职员适合做某些工作而不适合做另外一些工作。为了方便，在图7.1.1中以阴影表示某人不适合做某项工作。现在要问：是否有一种安排使得每个职员都做他适合的工作？如果这种安排存在，如何把它找到？如果这种安排不存在，那么对多少人能做合适的安排？在第5章中，我们把它看成是有限制位置的排列问题，使用容斥原理及棋子多项式可以求出合适安排的方法数。但是，它仅仅是计数，对于如何找到合适的安排不能提供任何信息。在本章中，我们将按照一种完全不同的方法来研究并解决这个问题。在前面的问题中，所谓合适的安排，就是在无阴影的部分里不同行、不同列选6个方块的一种方法。如果把每行无阴影方块的横坐标写成集合，那么如果能从每个集合中选出一个元素，而且6个元素两两互不相同，就得到了一种合适的安排。遗憾的是，对于这里的而言，这样的选择不存在。这是因为，无论选出的是，还是都没有合适的元素可选。7.2 相异代表系令是集合E的n个子集。E的n个元素，其中，称为是集族的一个代表系。如果集族的代表系中的元素两两互不相同，则称该代表系为集族的相异代表系。例如，4，1，4，3是的代表系，而1，2，3，4和4，2，3，5是的相异代表系。非空集合构成的集族一定有代表系，但不一定有相异代表系。例如，就没有相异代表系。直观上看，是因为中的元素太少。如何把感性认识上升到理论高度，找出集族有相异代表系的充要条件是本节的任务。假设是集族的相异代表系，对于有个非空子集，故这种必要条件有个。1935年，P.Hall提出将这放在一起就是集族有相异代表系的充分条件。定理7.2.1 集族有相异代表系，当且仅当对每个和每种选择，集族满足证明 由前面的分析，必要性是显然的。下面通过对n进行归纳来证明充分性。当时，由定理的条件知，即是非空集合。任取的元素，就是的相异代表系。设对任何满足定理的条件，则该集族有相异代表系。现假设集族满足定理的条件，我们将分两种情况讨论：（1）对于任何，选择均满足，由于满足定理的条件，于是。任取，构造集族则对于任意和，有即该集族满足定理的条件，由归纳假设知它有相异代表系，且。从而就是的相异代表系。（2）对某个及某种选择，不失一般性，我们假设这p个集合是，则。由于取自原来的集族，故满足定理的条件，并且，由归纳假设知集族有相异代表系，然而，故现考虑个集合构成的集族对于任意和，有即满足定理的条件，且集族中的集合数。由归纳假设知它有相异代表系，且从而就是集族的相异代表系。例1 已知。因为由定理7.2.1知集族没有相异代表系。但集族有相异代表系1，4，5，2。定理7.2.2 集族中存在着r元子集有相异代表系，当且仅当对每个和每种选择，集族满足证明 对于，定理中的不等式自动满足。令，且，考虑集族。下面先证明：的r元子集有相异代表系，当且仅当有相异代表系。假设的r元子集有相异代表系，不失一般性，设有相异代表系，就是的相异代表系。假设有相异代表系，因F中只有个元素，所以中至少有r个元素不在F中。不妨假设，且两两互不相同，从而是的r元子集的一个相异代表系。下面再证明：有相异代表系，当且仅当对每个和每种选择，有根据定理7.2.1，有相异代表系，当且仅当对每个和每种选择，有由于从而由定理7.2.2知，集族的r元子集有相异代表系，当且仅当对每个和每种选择，有使该不等式成立的r的最大值就是的最小值。故有如下推论：推论7.2.1 集族有相异代表系的最大子集数等于的最小值，其中，以及所有选择例2 已知，则有且6，5，2，1，4是子集族的相异代表系。于是，有相异代表系的子集数最大为5。7.3 棋盘覆盖问题棋盘覆盖问题是指将棋盘中的一些方块涂上阴影，余下部分用的多米诺骨牌覆盖。所谓棋盘的完全覆盖，是指多米诺骨牌的一种放置方法，它满足如下3个性质：（1）每个多米诺骨牌覆盖棋盘上两个相邻的方法（无阴影的）；（2）棋盘上的每个方块均被某个多米诺骨牌覆盖；（3）所有多米诺骨牌不重叠放置。现在的问题是：任意给定一个部分涂上阴影的棋盘，是否有一个完全覆盖？如果没有，那么满足性质（1）和（3）的覆盖需要用多少多米诺骨牌？例 对图7.3.1所示的棋盘用多米诺骨牌覆盖。解 首先，对整个棋盘依次标记，使得有公共边的方块标记不同。然后，对无阴影部分（要覆盖的区域）的标记从左到右、从上到下进行编号。因为每个多米诺骨牌必定覆盖一个和一个b，所以无阴影部分中标记w的块数与标记b的块数相同才有可能有完全覆盖。对每个定义一个集合，它由用多米诺骨牌覆盖时可能覆盖的组成，即标记和的方块有公共边显然，图7.3.1中，令相应的为如果有相异代表系，则该棋盘有一个完全覆盖。不难看出就是它的一个相异代表系，相应的完全覆盖如图7.3.2所示。对于B的子集，定义例如，上例中由定理7.2.1即得如下定理：定理7.3.1 棋盘存在完全覆盖，当且仅当，且对任意，成立。7.4 二分图的匹配问题如果图的结点集合，且图中的每条边均为，其中，则该图称为二分图，记作，其中，表示边集合。令，在二分图中定义则可将二分图与集族联系起来。例如，设则图7.4.1所示的二分图关联的集族为该集族的相异代表系关联的4条边没有公共结点。在二分图的某个边集合中，如果及都是两两互不相同的，则称它是该二分图的一个匹配。令，二分图关联的集族为，则有如下事实：（1）若是二分图的一个匹配，则是集族的一个相异代表系；（2）有相异代表系，当且仅当二分图有一个n边的匹配（称为完全匹配）；（3）有相异代表系的最大子集数等于二分图的最大匹配边数。在二分图中，如果结点集合，使得中的每条边至少有一个结点在其中，则称S是的一个覆盖。例如，图7.4.1中，都是的覆盖。定理7.4.1 设是一个二分图，它的匹配的最大边数等于覆盖的最小结点数。证明 令M是二分图具有最大边数的匹配，其边数为。令S是具有最小结点数的覆盖，其结点数为。因为M中没有两边有公共结点，并且M中的条边每边至少有一个结点在S中，所以