矩阵论中的图论匹配法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

教育部科学技术研究重点项目(207047)


Matching method of graph theory in matrix theory
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    G.Birkhoff用代数的方法证明了如果一个矩阵是双随机矩阵,则它能表示成置换矩阵的凸线性组合.设G是具有两分类(X,Y)的二部图,则G中含有饱和X中的所有顶点的匹配M的充分必要条件为:对∀S⊆X,有dG(S)≥|S|.文章借助上述二部图的匹配思想,给出这一结论的图论证明.

    Abstract:

    Let a non-negative real matrix Q be doubly stochastic,and a permutation matrix be a(0,1)-matrix which has exactly one 1 in each row and each column,then every permutation matrix will be doubly stochastic matrix.G.Birkhoff proved a conclusion that every doubly stochastic matrix Q can be expressed as a convex linear combination of permutation matrixs using the method of algerbra.Let G be a bipartite graph with bipartition(X,Y),then G contains a matching M that saturates every vertex in X if and only if dG(S)≥|S| for all S⊆X.In this paper,we obtain the proof of graph theory on the conclusion using the above matching theorem of bipartite graph.

    参考文献
    相似文献
    引证文献
引用本文

陈丽娟.矩阵论中的图论匹配法[J].南京信息工程大学学报(自然科学版),2011,(6):571-573
CHEN Lijuan. Matching method of graph theory in matrix theory[J]. Journal of Nanjing University of Information Science & Technology, 2011,(6):571-573

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2010-11-28
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期:
  • 出版日期:

地址:江苏省南京市宁六路219号    邮编:210044

联系电话:025-58731025    E-mail:nxdxb@nuist.edu.cn

南京信息工程大学学报 ® 2024 版权所有  技术支持:北京勤云科技发展有限公司