• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical Problems in Engineering >Maximum Matchings of a Digraph Based on the Largest Geometric Multiplicity
【24h】

Maximum Matchings of a Digraph Based on the Largest Geometric Multiplicity

机译：基于最大几何多重性的有向图的最大匹配

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Matching theory is one of the most forefront issues of graph theory. Based on the largest geometric multiplicity, we develop an efficient approach to identify maximum matchings in a digraph. For a given digraph, it has been proved that the number of maximum matched nodes has close relationship with the largest geometric multiplicity of the transpose of the adjacency matrix. Moreover, through fundamental column transformations, we can obtain the matched nodes and related matching edges. In particular, when a digraph contains a cycle factor, the largest geometric multiplicity is equal to one. In this case, the maximum matching is a perfect matching and each node in the digraph is a matched node. The method is validated by an example.
机译：匹配理论是图论最重要的问题之一。基于最大的几何多样性，我们开发了一种有效的方法来识别有向图的最大匹配。对于给定的有向图，已经证明最大匹配节点的数量与邻接矩阵的转置的最大几何多重性密切相关。此外，通过基本的列变换，我们可以获得匹配的节点和相关的匹配边。特别是，当有向图包含循环因子时，最大几何多重性等于1。在这种情况下，最大匹配是完全匹配，并且有向图中的每个节点都是匹配的节点。通过示例验证了该方法。

著录项

  • 来源
    《Mathematical Problems in Engineering》 |2016年第4期|4702387.1-4702387.7|共7页
  • 作者

    Yang Yunyun; Xie Gang;

  • 作者单位

    Taiyuan Univ Technol, Coll Informat Engn, Taiyuan 030024, Shanxi, Peoples R China;

    Taiyuan Univ Technol, Coll Informat Engn, Taiyuan 030024, Shanxi, Peoples R China;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号