274
个编辑
更改
→Maximum Matching
==Maximum Matching==
==Maximum Matching==
'''<font color="#FF8000">最大匹配 Maximum Matching </font>'''
'''<font color="#FF8000">最大匹配 Maximum Matching </font>'''<br>
In graph theory, a [[matching (graph theory)|matching]] is a set of edges without common vertices. Liu et al.<ref name="Liu-Nature-11"/> extended this definition to directed graph, where a matching is a set of directed edges that do not share start or end vertices. It is easy to check that a matching of a directed graph composes of a set of vertex-disjoint simple paths and cycles. The maximum matching of a directed network can be efficiently calculated by working in the bipartite representation using the classical [[Hopcroft–Karp algorithm]], which runs in O(''E''{{radic|''N''}}) time in the worst case. For undirected graph, analytical solutions of the size and number of maximum matchings have been studied using the [[cavity method]] developed in statistical physics.<ref name="Zdeborova-06">[[Lenka Zdeborová|L. Zdeborová]] and M. Mezard, ''J. Stat. Mech.'' '''05''' (2006).</ref> Liu et al.<ref name="Liu-Nature-11"/> extended the calculations for directed graph.
In graph theory, a [[matching (graph theory)|matching]] is a set of edges without common vertices. Liu et al.<ref name="Liu-Nature-11"/> extended this definition to directed graph, where a matching is a set of directed edges that do not share start or end vertices. It is easy to check that a matching of a directed graph composes of a set of vertex-disjoint simple paths and cycles. The maximum matching of a directed network can be efficiently calculated by working in the bipartite representation using the classical [[Hopcroft–Karp algorithm]], which runs in O(''E''{{radic|''N''}}) time in the worst case. For undirected graph, analytical solutions of the size and number of maximum matchings have been studied using the [[cavity method]] developed in statistical physics.<ref name="Zdeborova-06">[[Lenka Zdeborová|L. Zdeborová]] and M. Mezard, ''J. Stat. Mech.'' '''05''' (2006).</ref> Liu et al.<ref name="Liu-Nature-11"/> extended the calculations for directed graph.
在图论中，匹配（图论）是一组没有共同顶点的边。Liu等人将此定义扩展到有向图，其中匹配是一组不共享起始或终止顶点的有向边。很容易检查有向图的匹配是否由一组顶点不相交的简单路径和周期组成。定向网络的最大匹配可以通过使用经典的'''<font color="#FF8000">Hopcroft-Karp算法 </font>'''在'''<font color="#FF8000">二分表示 Bipartite Representation </font>'''中工作来有效地计算，该算法在最坏情况下的时间复杂度是O(''E'{{radic |''N''}})。对于无向图，使用统计物理中开发的[[腔法]]研究了最大匹配的大小和数量的分析解。<ref name=“Zdeborova-06”>[[Lenkazdeborová| L Zdeborová]]和M.Mezard，''J.Stat.Mech''''05''（2006）。</ref>Liu等人<ref name=“Liu-Nature-11”/>扩展了有向图的计算范围。
In graph theory, a matching is a set of edges without common vertices. Liu et al. Liu et al. extended the calculations for directed graph.