矩阵论中的图论匹配法
作者:
基金项目:

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


Matching method of graph theory in matrix theory
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献
  • | | | |
  • 文章评论
    摘要:

    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.

    参考文献
    [1]Birkhoff D.Tres observaciones sobre el algebra lineal[J].Univsidad Naccional de Tucuman Revista,Serie A,1946,5:147-151
    [2]李乔.矩阵论八讲[M].上海:上海科学技术出版社,1988LI Qiao.Eight lectures of matrix theory[M].Shanghai:Shanghai Science and Technology Press,1988
    [3]戴华.矩阵论[M].北京:科学出版社,2001DAI Hua.Theory of matrix[M].Beijing:Science Press,2001
    [4]Stuart J L,Weaver J R.Diagonally scaled permutations and circulant matrices[J].Linear Algebra and Its Applications,1994,212-213:397-411
    [5]谭尚旺.矩阵特征多项式的图论计算公式[J].纯粹数学与应用数学,2009,25(2):209-216TAN Shangwang.On formulas calculating the characteristic polynomial of matrices in graph theory[J].Pure and Applied Mathematics,2009,25(2):209-216
    [6]Liu G Z,Zhu B H.Some problems on factorizations with constraints in bipartite graphs[J].Discrete Applied Mathematics,2003,128(2):421-434
    [7]李世群.简单图的最大匹配的矩阵求法[J].数学的实践与认识,2007,37(7):120-124LI Shiqun.Severy algorith of maximum matching for simple graghs by means matrix[J].Mathematics in Practice and Theory,2007,37 (7):120-124
    [8]Bondy J A,Murty U S R.Graph theory with application[M].New York:Elsevier Science Press,1976
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

陈丽娟.矩阵论中的图论匹配法[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

复制
分享
文章指标
  • 点击次数:916
  • 下载次数: 2268
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2010-11-28

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

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

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