Geodesic
A Note on the Stochastic Rank of a Bipartite Graph
Canadian mathematical bulletin, Tome 2 (1959) no. 3, pp. 159-162

Voir la notice de l'article provenant de la source Cambridge University Press

A bipartite graph is a system consisting of two sets of vertices S and T and a set of edges K, each edge joining a vertex of S to a vertex of T. A set U of edges of K is said to be independent if no two edges of U have a vertex in common. The largest possible number of independent edges has been variously called the exterior dimension [3], term rank [4, 5, 7], etc. This number is the same as the smallest number of vertices in a set W such that each edge of K has at least one of its vertices in W. The edges of a finite bipartite graph can be represented as a set of cells in a matrix as follows. If S = a1, a2, ..., an T = b1, b2, ... bm, the edges of K are represented by some of the cells of an n by m matrix as follows: if K contains the edge joining ai to bj then the (i, j)th cell of the matrix represents this edge. It is convenient sometimes to represent the set K by a matrix A with real entries aij where aij = 0 if ai is not joined to bj in K and aij > 0 if ai is joined to bj in K. Any non-null graph K will have infinitely many matrix representations. 
Dulmage, A.L.; Mendelsohn, N.S. A Note on the Stochastic Rank of a Bipartite Graph. Canadian mathematical bulletin, Tome 2 (1959) no. 3, pp. 159-162. doi: 10.4153/CMB-1959-020-4
@article{10_4153_CMB_1959_020_4,
     author = {Dulmage, A.L. and Mendelsohn, N.S.},
     title = {A {Note} on the {Stochastic} {Rank} of a {Bipartite} {Graph}},
     journal = {Canadian mathematical bulletin},
     pages = {159--162},
     year = {1959},
     volume = {2},
     number = {3},
     doi = {10.4153/CMB-1959-020-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1959-020-4/}
}
TY  - JOUR
AU  - Dulmage, A.L.
AU  - Mendelsohn, N.S.
TI  - A Note on the Stochastic Rank of a Bipartite Graph
JO  - Canadian mathematical bulletin
PY  - 1959
SP  - 159
EP  - 162
VL  - 2
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1959-020-4/
DO  - 10.4153/CMB-1959-020-4
ID  - 10_4153_CMB_1959_020_4
ER  - 
%0 Journal Article
%A Dulmage, A.L.
%A Mendelsohn, N.S.
%T A Note on the Stochastic Rank of a Bipartite Graph
%J Canadian mathematical bulletin
%D 1959
%P 159-162
%V 2
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1959-020-4/
%R 10.4153/CMB-1959-020-4
%F 10_4153_CMB_1959_020_4

[1] 1. Konig, D., Theorie der endlichen und unendlichen Graphen, (New York, 1950). Google Scholar

[2] 2. Dulmage, A.L. and Halperin, I., On a theorem of Frobenius-- Konig and J. von Neumann's game of hide and seek, Trans. Roy. Soc. Can. Ser. III, 49 (1955), 23-29. Google Scholar

[3] 3. Dulmage, A.L. and Mendelsohn, N.S., Coverings of bipartite graphs, Can. J. Math. 10 (1958), 517-534. Google Scholar

[4] 4. Dulmage, A.L. and Mendelsohn, N.S., The term and stochastic ranks of a matrix, Can. J. Math. 11 (1959), 269-279. Google Scholar

[5] 5. Ore, O., Graphs and matching theorems, Duke Math. J. 22 (1955), 625-639. Google Scholar

[6] 6. Ryser, H.J., Combinatorial properties of matrices of zeros and ones, Can. J. Math. 9 (1957), 371-377. Google Scholar

[7] 7. Ryser, H.J., The term rank of a matrix, Can. J. Math. 10 (1957), 57-65. Google Scholar

Cité par Sources :