Bipartite Matching慕课视频播放-算法设计与分析-MOOC慕课视频教程-柠檬大学

匹配问题是一个经典问题

两分图匹配是其中的一个基本模型

我们先给出匹配问题的定义

输入是一个无向图G=(V, E)

我们称M是一个匹配

它是边集E的一个子集

使得每个节点至多出现在M的一条边中

最大匹配就是求包含边数最多的一个匹配

比如下图中标记蓝色的边

构成了一个匹配

对应的目标值为10

对于两分图匹配

它的输入是一个无向图G

同时也是一个两分图

节点被划分成两部分 L和R

使得每条边的两个端点分别属于L和R

同样地我们称M是一个匹配

它是边集E的一个子集

使得每个节点至多出现在M的一条边中

最大匹配就是求包含边数最多的一个匹配

比如在如下所给的两分图中

我们构建如下的匹配

1-2', 3-1', 4-5'

对应的目标值为3

实际上对于同一个图

我们可以得到如下的最大匹配

1-1', 2-2', 3-3', 4-4'

对应的目标值为4

我们用最大流的方法

来求解两分图的匹配问题

创建一个有向图G'

其节点集包含原问题中的点集L和R

并添加两个点s和t

G'的边集E'包含原图中的边

并令它们的方向从L一边指向R一边

并且赋予这些边无限的容量

实际上也可以是单位容量

从点s到L中所有的点存在一条有向边

其上有单位容量

从R中所有点都有指向t的有向边

其上也是单位容量

对于刚才的例子

我们可以构建出如下的图

我们有下面的定理

G上的最大匹配等于G'上的最大流的流值

我们分两部分来证明

首先证明最大匹配小于等于最大流值

给定G最大匹配M

对应的目标值为k

我们可以如图构建一个流f

每个匹配对应一条s-t可行路

可发送1个单位的流

我们得到G'上的一个可行流f

目标值为k

因此最大匹配小于等于最大流值

我们再来证明最大匹配大于等于最大流值

令f是G'上的一个可行流

目标值为k

由整流定理

k是整数

并且可以假设f在每条边上的流量都是0或1

令M是从L出发到R的边的集合

边上流量为1

由s到L的边上容量的设定

可知 L中的点在M中至多出现一次

同理 R中的点在M中出现至多一次

即M是一个匹配

并且包含k条边

因此最大匹配大于等于最大流值

最后简要讨论一下

利用不同最大流算法

求解两分图匹配的一些基本结论

如果采用一般增广路算法的话

算法运行时间为O(mval(f*))=O(mn)

采用变尺度技术的话

算法运行时间为O(m^2logC)=O(m^2)

如果采用最短增广路算法

那么算法的运行时间为O(mn^1/2)

非两分图匹配问题要复杂得多

但是相关的研究也很深入

Edmonds在1965年得到了O(n^4)的算法

目前最好的算法是

80年左右得到的O(mn^1/2)的结果

算法设计与分析课程列表：

1 Introduction of Algorithm

-1.1 Introduction

--Introduction

-1.2 A First Problem: Stable Matching

--A First Problem: Stable Matching

-1.3 Gale-Shapley Algorithm

--Gale-Shapley Algorithm

-1.4 Understanding Gale-Shapley Algorithm

--Understanding Gale-Shapley Algorithm

-Homework1

-Lecture note 1

--Lecture note 1 Introduction of Algorithm

2 Basics of Algorithm Analysis

-2.1 Computational Tractability

--Computational Tractability

-2.2 Asymptotic Order of Growth

--Asymptotic Order of Growth

-2.3 A Survey of Common Running Times

--A Survey of Common Running Times

-Homework2

-Lecture note 2

--Lecture note 2 Basics of Algorithm Analysis

3 Graph

-3.1 Basic Definitions and Applications

--Basic Definitions and Applications

-3.2 Graph Traversal

--Graph Traversal

-3.3 Testing Bipartiteness

--Testing Bipartiteness

-3.4 Connectivity in Directed Graphs

--Connectivity in Directed Graphs

-3.5 DAG and Topological Ordering

--DAG and Topological Ordering

-Homework3

-Lecture note 3

--Lecture note 3 Graph

4 Greedy Algorithms

-4.1 Coin Changing

--Coin Changing

-4.2 Interval Scheduling

--Interval Scheduling

-4.3 Interval Partitioning

--Interval Partitioning

-4.4 Scheduling to Minimize Lateness

--Scheduling to Minimize Lateness

-4.5 Optimal Caching

--Optimal Caching

-4.6 Shortest Paths in a Graph

--Shortest Paths in a Graph

-4.7 Minimum Spanning Tree

--Minimum Spanning Tree

-4.8 Correctness of Algorithms

--Correctness of Algorithms

-4.9 Clustering

--Clustering

-Homework4

-Lecture note 4

--Lecture note 4 Greedy Algorithms

5 Divide and Conquer

-5.1 Mergesort

--Mergesort

-5.2 Counting Inversions

--Counting Inversions

-5.3 Closest Pair of Points

--Closest Pair of Points

-5.4 Integer Multiplication

--Integer Multiplication

-5.5 Matrix Multiplication

--Video

-5.6 Convolution and FFT

--Convolution and FFT

-5.7 FFT

--FFT

-5.8 Inverse DFT

--Inverse DFT

-Homework5

-Lecture note 5

--Lecture note 5 Divide and Conquer

6 Dynamic Programming

-6.1 Weighted Interval Scheduling

--Weighted Interval Scheduling

-6.2 Segmented Least Squares

--Segmented Least Squares

-6.3 Knapsack Problem

--Knapsack Problem

-6.4 RNA Secondary Structure

--RNA Secondary Structure

-6.5 Sequence Alignment

--Sequence Alignment

-6.6 Shortest Paths

--Shortest Paths

-Homework6

-Lecture note 6

--Lecture note 6 Dynamic Programming

7 Network Flow

-7.1 Flows and Cuts

--Flows and Cuts

-7.2 Minimum Cut and Maximum Flow

--Minimum Cut and Maximum Flow

-7.3 Ford-Fulkerson Algorithm

--Ford-Fulkerson Algorithm

-7.4 Choosing Good Augmenting Paths

--Choosing Good Augmenting Paths

-7.5 Bipartite Matching

--Bipartite Matching

-Homework7

-Lecture note 7

--Lecture note 7 Network Flow

8 NP and Computational Intractability

-8.1 Polynomial-Time Reductions

--Polynomial-Time Reductions

-8.2 Basic Reduction Strategies I

--Basic Reduction Strategies I

-8.3 Basic Reduction Strategies II

--Basic Reduction Strategies II

-8.4 Definition of NP

--Definition of NP

-8.5 Problems in NP

--Problems in NP

-8.6 NP-Completeness

--NP-Completeness

-8.7 Sequencing Problems

--Sequencing Problems

-8.8 Numerical Problems

--Numerical Problems

-8.9 co-NP and the Asymmetry of NP

--co-NP and the Asymmetry of NP

-Homework8

-Lecture note 8

--Lecture note 8 NP and Computational Intractability

9 Approximation Algorithms

-9.1 Load Balancing

--Load Balancing

-9.2 Center Selection

--Center Selection

-9.3 The Pricing Method: Vertex Cover

--The Pricing Method: Vertex Cover

-9.4 LP Rounding: Vertex Cover

--LP Rounding: Vertex Cover

-9.5 Knapsack Problem

--Knapsack Problem

-Homework9

-Lecture note 9

--Lecture note 9 Approximation Algorithms

10 Local Search

-10.1 Landscape of an Optimization Problem

--Landscape of an Optimization Problem

-10.2 Maximum Cut

--Maximum Cut

-10.3 Nash Equilibria

--Nash Equilibria

-10.4 Price of Stability

--Price of Stability

-Homework10

-Lecture note 10

--Lecture note 10 Local Search

11 Randomized Algorithms

-11.1 Contention Resolution

--Contention Resolution

-11.2 Linearity of Expectation

--Linearity of Expectation

-11.3 MAX 3-SAT

--MAX 3-SAT

-11.4 Chernoff Bounds

--Chernoff Bounds

-Homework11

-Lecture note 11

--Lecture note 11 Randomized Algorithms

Exam

-Exam

Bipartite Matching在线视频