算法►算法设计技巧与分析

匹配

文章目录
  1. 1. 问题定义
  • 二分图
  • 一般图

    • maximum v.s maximal matching

    maximal matching: 极大匹配？

    maximum match: (also known as maximum-cardinality matching)最大匹配是要找出一个E的子集M，它具有最大数量的不交叠边，即在M中任何两条边没有一个共同顶点。

    交替路径：一条由匹配边和未匹配边交替组成的简单路径。

    交替路径被称为增广路径，当p中所有的匹配边都在M中并且端点是自由的。

    问题定义

    寻找二分图的最小顶点覆盖算法：Kőnig’s theorem)

    Let’s say you have G = (V, E) a bipartite graph, separated between X and Y.

    As you said, first you have to find a maximum matching (which can be achieved with Dinic’s algorithmfor instance). Let’s call M this maximum matching.

    Then to construct your minimum vertex cover顶点覆盖:

    • Find U the set (possibly empty) of unmatched vertices in X, ie. not connected to any edge in M
    • Build Z the set or vertices either in U, or connected to U by alternating paths (paths that alternate between edges of M and edges not in M) 通过交替路径与U中顶点相连。
    • Then K = (X \ Z) U (Y ∩ Z) is your minimum vertex cover

    二分图和一般图的匹配算法研究

    • 交替路径树：每一条从根节点到叶子节点的路径均为交替路径

    • 匈牙利树：从自由顶点r开始生长交替路径树，如果树被阻塞，则该被阻塞的树为匈牙利树。

      从自由顶点r开始，加上每一条连接r和y顶点y的未匹配边(r, y)。对于y，如果有匹配边(y, z)存在，则将其加入T。重复此过程直到遇到自由的y顶点或被阻塞。

    二分图

    二分图：不含奇数长度的回路。

    1. 网络流方法

    2. 匈牙利树方法

      1. 无向图G的一个匹配M是最大的，当且仅当G不包含关于M的增广路径。
      2. M为一个匹配，p是关于M的一条增广路径，则M+p可以构造一个更大的匹配。

      (匈牙利树的方法利用了匹配的特定性质，这个性质可以帮助我们解决扩大匹配这个问题)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    BiMatch2
    Input: 二分图 G = (X ∪ Y, E)
    Output: G中最大匹配M
    初始化M为任意匹配（可能为空）
    while存在自由顶点x和自由y顶点
    	设r为一个自由x顶点，采用广度优先搜索，生成一棵以r为根的交替路径树T
    	if T为匈牙利树： 
    		let G <- G - T
    	else:
    		在T中找到一条增广路径p，并设M = M + p
    • 算法的时间复杂度？构造交替树$O(m)$，最多构造$O(n)$棵树 => $O(nm) = O(n^3)$
    • 为什么匈牙利树可被移除而不影响搜索匹配过程？
      • 匈牙利树中无顶点能在增广路径中出现
        • 如果($x, y)$为一条边，使得$x$在$T$中而$y$不在$T$中，那么$x$肯定被标记为内部
      • 交替路径不经过$T$
        • 如果经过$T$，则必然以内部顶点进入、内部顶点穿出，矛盾。

    一般图

    1. 匈牙利树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    GMATCH
    Input: undirected graph G(V, E)
    Output: maximum match M of G

    M = {}
    maximum = false
    while not maximum
    	确定与M相关的自由顶点集Ｆ
    	augment = false
    	while F ≠ {} and not augment
    		清空栈、未标记边，从顶点删除标记
    		设x为下一个顶点； F = F - {x}; T = x
    		标记x为外部的 {初始化交替路径树}
    		
    		hungarian = false
    		while not augment:
    			选择一个外部顶点x和一条未标记的边(x, y)
    			if (x, y)存在： 标记(x, y)
    			else:
    				hungarian = true
    				break
    			if y是内部的: doNothing {找到偶数长的回路}
    			elif y是外部的: {找到花}
    				将花放到栈顶，收缩花
    				用顶点w替换花，标记w是外部的
    				如果花包含根，则标记w是自由的
    			elif y是自由的：
    				augment = true
    				F = F - {y}
    			else:
    				设(y, z)在M中，将(x, y) 和(y, z)加入T中
    				标记y是内部的，z为外部的
    			
    			if hungarian: 从G中移除T
    			elif augment:
    				构造增广路径:从栈中弹出花，展开它们，增加偶数长部分
    				用p增广G
    	if not augment:
    		maximum = true

    外层while循环寻找最大匹配，每一次迭代，增广路径被发现并由这条路径匹配扩展集

    中层while循环对所有的自由顶点循环，直到发现增广路径为止。

    每次迭代中选取一个自由顶点左右交替路径树的根，从这个根出发在内层循环中对图探查，内循环的功能是每次加两条边增长交替路径树。每次迭代中，它取任意一个外部顶点x和相应的边(x,y)，如果这样的边存在，有以下几种情况：

    1. y是内部的
    2. y是外部的
    3. y被标记为自由的
    4. 其他情况下