更改

A matching in a graph is a subset of its edges, no two of which share an endpoint. Polynomial time algorithms are known for many algorithmic problems on matchings, including maximum matching (finding a matching that uses as many edges as possible), maximum weight matching, and stable marriage.In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,[31] and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching[32] work correctly only on bipartite inputs.

A matching in a graph is a subset of its edges, no two of which share an endpoint. Polynomial time algorithms are known for many algorithmic problems on matchings, including maximum matching (finding a matching that uses as many edges as possible), maximum weight matching, and stable marriage.In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,[31] and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching[32] work correctly only on bipartite inputs.

一个图中的匹配是其边集的一个子集，其中任意两个边均不共享一个端点。'''<font color="#ff8000"> 多项式时间算法Polynomial time algorithms</font>'''素以解决很多关于匹配的算法问题而得名，包括'''<font color="#ff8000"> 最大匹配maximum matching</font>'''（查找使用尽可能多的边的匹配），'''<font color="#ff8000"> 最大权重匹配maximum weight matching</font>'''和'''<font color="#ff8000"> 稳定婚姻问题stable marriage</font>'''。在许多情况下，与非二分图相比，二分图上的匹配问题更容易解决，并且许多匹配算法（例如用于最大基数匹配的'''<font color="#ff8000"> Hopcroft-Karp算法</font>'''）仅在二分图输入的时候才能正确运行。

一个图中的匹配是其边集的一个子集，其中任意两个边均不共享一个端点。'''<font color="#ff8000"> 多项式时间算法Polynomial time algorithms</font>'''素以解决很多关于匹配的算法问题而得名，包括'''<font color="#ff8000"> 最大匹配Maximum matching</font>'''（查找使用尽可能多的边的匹配），'''<font color="#ff8000"> 最大权重匹配Maximum weight matching</font>'''和'''<font color="#ff8000"> 稳定婚姻问题Stable marriage</font>'''。在许多情况下，与非二分图相比，二分图上的匹配问题更容易解决，并且许多匹配算法（例如用于最大基数匹配的'''<font color="#ff8000"> Hopcroft-Karp算法</font>'''）仅在二分图输入的时候才能正确运行。