标签：#组合最优化

匹配 (图论)

在图论中，一个图是一个匹配（或称独立边集）是指这个图之中，任意两条边都没有公共的顶点。这时每个顶点都至多连出一条边，而每一条边都将一对顶点相匹配。 严格定义 对于一个给定的图G=(V,E)，这幅图的一个匹配M是图G的一个子图（由原来的图的一部分顶点和一部分边构成的图），其中每两条边都不相邻（没有公共顶点）。在匹配图中，一个顶点连出的边数至多是一条。如果这个顶点连出一条边，就称这个顶点是已匹配的。 图G的一个极大匹配是指这样一个匹配，它不…