In graph theory, a branch of mathematics, the rank of an undirected graph has two unrelated definitions. Let n equal the number of vertices of the graph.
- In the matrix theory of graphs the rank r of an undirected graph is defined as the rank of its adjacency matrix.
- In the matroid theory of graphs the rank of an undirected graph is defined as the number n − c, where c is the number of connected components of the graph. Equivalently, the rank of a graph is the rank of the oriented incidence matrix associated with the graph.
Examples
A sample graph and matrix:
(corresponding to the four edges, e1–e4):
| = | ( 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 ) . {\displaystyle {\begin{pmatrix}0&1&1&1\\1&0&0&0\\1&0&0&1\\1&0&1&0\\\end{pmatrix}}.} |
In this example, the matrix theory rank of the matrix is 4, because its column vectors are linearly independent.
See also
Notes
- Chen, Wai-Kai (1976), Applied Graph Theory, North Holland Publishing Company, ISBN 0-7204-2371-6.
- Hedetniemi, S. T., Jacobs, D. P., Laskar, R. (1989), Inequalities involving the rank of a graph. Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 6, pp. 173–176.
- Bevis, Jean H., Blount, Kevin K., Davis, George J., Domke, Gayla S., Miller, Valerie A. (1997), The rank of a graph after vertex addition. Linear Algebra and its Applications, vol. 265, pp. 55–69.
References
Grossman, Jerrold W.; Kulkarni, Devadatta M.; Schochetman, Irwin E. (1995), "On the minors of an incidence matrix and its Smith normal form", Linear Algebra and Its Applications, 218: 213–224, doi:10.1016/0024-3795(93)00173-W, MR 1324059. See in particular the discussion on p. 218. /wiki/Doi_(identifier) ↩