Matching method of graph theory in matrix theory
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference
  • |
  • Related [1]
  • |
  • Cited by
  • | |
  • Comments
    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.

    Reference
    Cited by
Get Citation

CHEN Lijuan. Matching method of graph theory in matrix theory[J]. Journal of Nanjing University of Information Science & Technology,2011,(6):571-573

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 28,2010
Article QR Code

Address:No. 219, Ningliu Road, Nanjing, Jiangsu Province

Postcode:210044

Phone:025-58731025