【教学课件】第八节最大对集问题.ppt

《【教学课件】第八节最大对集问题.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第八节最大对集问题.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八节第八节 最大对集问题最大对集问题二分图的对集二分图的对集 基本概念基本概念 主要定理主要定理二分图的最大基数对集二分图的最大基数对集 基本思想基本思想 算法步骤算法步骤 算法复杂性算法复杂性二分网络的最大权对集分派问题二分网络的最大权对集分派问题 规划形式规划形式 算法步骤算法步骤基本概念基本概念图图G=(N,E)的对集的对集M：M是是E的子集，且的子集，且M中任中任意两边均不相邻。意两边均不相邻。M-饱和点饱和点i：iN，且，且i同同M的一条边关联。的一条边关联。M-非饱和点非饱和点i：iN，且，且i不同不同M的任一条边关联。的任一条边关联。G的完美对集的完美对集M：G的每一个点都是的

2、每一个点都是M-饱和点。饱和点。G的最大基数对集的最大基数对集M：不存在另外一个对集：不存在另外一个对集M,使得使得|M|M|，其中，其中|M|表示表示M的基数。的基数。基本概念基本概念G的一条的一条M-交错路交错路：边在对集：边在对集M和和EM中交错中交错出现的路。出现的路。G的一条的一条M-增广路增广路：起点和终点都是：起点和终点都是M非饱和非饱和的一条的一条M-交错路。交错路。图图G=(N,E)的覆盖的覆盖K：K是是N的子集，且的子集，且G的每的每条边都至少有一个端点在条边都至少有一个端点在K中。中。图图G的最小覆盖的最小覆盖K：G不存在另外一个覆盖不存在另外一个覆盖K，使得，使得|K|

3、K|。续续主要定理主要定理定理定理 图图G中的一个对集中的一个对集M是最大基数对集当且仅当是最大基数对集当且仅当G不包含不包含M-增广路。增广路。引理引理 设设M是一个对集，是一个对集，K是一个覆盖，它们满足是一个覆盖，它们满足|M|=|K|，则，则M必定是最大基数对集，而必定是最大基数对集，而K是最小是最小覆盖。覆盖。定理定理 在二分图中，最大基数对集的边数等于最小覆在二分图中，最大基数对集的边数等于最小覆盖的点数。盖的点数。证明证明最大基数对集算法的基本思想最大基数对集算法的基本思想从从图图G的的任任意意一一个个对对集集M开开始始，若若M饱饱和和S的的所所有有点点，则则M是是G的的最最大大

4、基基数数对对集集；否否则则，由由S的的M-非非饱饱和和点点出发，用一个系统方法搜索一条出发，用一个系统方法搜索一条M-增广路增广路P。若若P存存在在，则则通通过过交交换换P在在M和和不不在在M中中的的边边，便便得得到到一一个个其其基基数数增增加加1的的对对集集，然然后后从从新新的的对对集集开开始始，继续迭代。继续迭代。若若P不存在，则现行的对集就是不存在，则现行的对集就是G的最大基数对集的最大基数对集。最大基数对集算法的步骤最大基数对集算法的步骤第第1步步(开始开始)给给定定二二分分图图G=(S,T,E)，令令M是是一一个个任任意意对对集集，可可能能是空对集，这时没有点被标号。是空对集，这时没

5、有点被标号。第第2步步(标号标号)(2.0)在在S中，每个非饱和点给以标号中，每个非饱和点给以标号“0”。(2.1)如如果果不不存存在在未未检检查查的的标标号号点点，转转向向第第4步步；否否则则，找找一一个个具具有有未未检检查查的的标标号号点点i，如如果果iS，转转向向(2.2)；如果；如果iT，转向，转向(2.3)(2.2)检检查查点点i的的标标号号如如下下：对对每每个个同同点点i关关联联的的边边i,j，除除非非j已已经经被被标标号号；否否则则，给给点点j标标号号“i”，转转向向(2.1)。(2.3)检检查查点点i的的标标号号如如下下：如如果果点点i是是非非饱饱和和点点，转转向向第第3步步；

6、否否则则，辨辨认认同同点点i关关联联的的属属于于M的的唯唯一一边边i,j，给点，给点j标号标号“i”，转向，转向(2.1)。最大基数对集算法的步骤最大基数对集算法的步骤第第3步步(增广增广)终终止止在在i的的一一条条增增广广路路被被找找到到，通通过过反反方方向向追追踪踪辨辨认认在在路路上上点点i的的前前点点，通通过过把把路路上上不不在在M中中的的边边加加入入M，而而把把路路中中在在M中中的的边边从从M中中除除去去来来增增广广M，抹抹掉掉所所有标号，转回有标号，转回(2.0)。续续例例最大基数对集算法的复杂性最大基数对集算法的复杂性若令若令|S|=m，|T|=n，且，且m0，则则转转向第向第4步

7、。步。(2.2)找找一一个个未未检检查查的的标标号号点点i，其其中中或或者者iS，或或者者 iT且且i=0，如如果果iS，则则转转向向(2.3)；如如果果iT，则转向则转向(2.4)。最大权对集算法的步骤最大权对集算法的步骤(2.3)检检查查点点i的的标标号号如如下下：对对每每条条边边i,j不不属属于于M，如如 果果 ui+vj-wij0,jT，=min1,2。令令L表表示示所所有有标标号号点点的的集集合合。对对每每个个iLS，从从ui减减去去；对对每每个个j=0的的点点jT，则则vj加加上上；对对每每个个j0的的点点jLT，则则j减减去去。如如果果1，转转向向(2.1)；否否则则，M是是最最大大权权对集，变量对集，变量ui和和vj是最优对偶解。是最优对偶解。续二续二