274
个编辑
更改
跳到导航
跳到搜索
第95行：
第95行： − ===Maximum Matching===+
→Maximum Matching
(1976年)。 / ref '''<font color="#32CD32">主要的问题是，对于可变系统参数来说，缺乏可控性或可观测性是否是一般性的。在结构控制的框架下，系统参数可以是独立自由变量，也可以是固定零点。这对于物理系统的模型是一致的，因为参数值永远不会准确地知道，零值除外，零值表示交互或连接的缺失。</font>
(1976年)。 / ref '''<font color="#32CD32">主要的问题是，对于可变系统参数来说，缺乏可控性或可观测性是否是一般性的。在结构控制的框架下，系统参数可以是独立自由变量，也可以是固定零点。这对于物理系统的模型是一致的，因为参数值永远不会准确地知道，零值除外，零值表示交互或连接的缺失。</font>
==Maximum Matching==
'''<font color="#FF8000">最大匹配 Maximum Matching </font>'''
'''<font color="#FF8000">最大匹配 Maximum Matching </font>'''
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.