第5章独立集与匹配

第五章独立集与匹配5.1独立集5.2支配集5.3匹配5.4最大匹配算法5.5最优匹配5.6Ramsey数

5.1独立集

点覆盖

图中，点覆盖数依次为3，4，6。23145678910

边覆盖独立集的应用举例例：(收款台的设置问题)某大型商场为加强经营管理，对商品的零售收入实行统一收款制度。为了使顾客在任何一个货架前都能看到收款台，问收款台应设置在什么地方且至少要设置多少个收款台?

矩阵变换求独立集

v1v2v4v3v6v5

团的定义：

clique例：求下图的极大独立集45236187

5.2支配集

在国际象棋的比赛中，首先出现了支配集的概念。1862年，De考虑了控制整个棋盘所需要的最少的皇后个数问题。他指出在一个的棋盘具有处在配置下的64个格子，在所给某个位置的皇后控制着同行、同列以及包含这个格子的两条斜线上的所有格子，这种皇后的最少个数为5，左图显示了一种放置方法。QQQQQ

若要求任两个皇后都不互相攻击，即任两个皇后都不在同一行、同一列或一斜线上，那么这种皇后的最少个数为7，下图显示了一种放置方法。QQQQQQQ支配集的几个性质定理

注意：不是每个支配集都是独立集；也不是每个最小支配集都是独立集。

求极小支配集的一种布尔运算方法例：求在下图的全部极小支配集。5.3匹配

匹配问题是运筹学的重要问题之一,也是图论研究的终点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想。

说明:(1)完美匹配是最大匹配，反之未必然;(2)匹配的定义与边的方向无关，故匹配是针对无向图。

例：下图中虚线所示为匹配，则(2,3,5,6,9,10)是一条交错路，而(1，2，3，5，6，8)是一条可增广路。练习

例：某工厂生产由六种不同颜色的纱织成的双色布，由这个工厂所生产的双色布中，每一种颜色至少和其他三种颜色搭配。证明可以挑选出三种不同的双色布，它们含有所有的六种颜色。

5.4最大匹配算法匈牙利算法

图（a）图（b）

MxSTN(S)yN(S)-T{y,u}MP{y1,y2,y3,y4,y5}y1非饱和{x1y2,x2y1,x3y3x5y5}y2饱和y3饱和N(S)=T,停止

图(c)

例：求下图最大匹配

匈亚利算法：

00**00

**11*23*00*11*23*

22200*1123*222

0*

44044

**23044**23

5.5最优匹配及算法

基于上述定理，Kuhn(1955)和Munkres(1957)提出一个在加权完全二部图中求最优匹配的算法，简称为K-M算法。其主要思想如下：

Kuhn-Munkres算法

Kuhn-Munkres算法也可以用来求加权完全二部图中总权最小的完美匹配。它需要将原来的权重矩阵做相应的变化，即将权重最大问题，转化为权重最小问题。

x1x2x3x4x5y1y2y3y4y5

5.6Ramsey数1928年,年仅24岁的英国杰出数学家Ramsey发表了著名论文《论形式逻辑中的一个问题》,他在这篇论文中,提出并证明了关于集合论的一个重大研究成果,现称为Ramsey定理。尽管两年后他不幸去世，但是他开拓的这一新领域至今仍十分活跃，而且近年来在科技领域获得了成功的应用。在