极大匹配怎么判断请详细举例说明

极大匹配是指在二分图中，匹配边数最大，且不存在增广路径的匹配。其中增广路径是指从一个未匹配点开始，沿着交替路径一直走到另一个未匹配点的路径。

举个例子，我们有一个二分图如下：

1 -- 2
|    |
3 -- 4

其中，数字代表节点，这个图中有4个节点，分别是1、2、3、4。我们可以将这个二分图表示成一个邻接矩阵：

  1 2 3 4
1 0 1 1 0
2 1 0 0 1
3 1 0 0 1
4 0 1 1 0

其中，1表示两个节点之间有边相连，0表示没有边相连。我们可以使用匈牙利算法来求出这个二分图的极大匹配。

首先，我们选取一个未匹配点，比如节点1。我们从这个节点开始，尝试将它与它的邻居节点进行匹配。由于节点1与节点2、3都相连，我们可以尝试将节点1与节点2或者节点3进行匹配。

假设我们先尝试将节点1与节点2进行匹配。这时，我们发现节点2还没有被匹配，因此我们可以将节点1和节点2匹配起来。现在，匹配状态如下：

1 -- 2
|    |
3 -- 4

我们继续寻找未匹配点，发现节点3还没有被匹配。我们尝试将节点3与节点4进行匹配，但是失败了，因为节点4已经被节点2匹配了。

现在，我们尝试寻找增广路径。从未匹配点节点3开始，我们可以沿着交替路径走到已匹配点节点2，再走到未匹配点节点4。因此，我们可以将节点3和节点4匹配起来。匹配状态如下：

1 -- 2
     |
3 -- 4

现在，所有节点都已经被匹配。这个二分图的极大匹配是{(1,2), (3,4)}。