Rank (graph theory)
In graph theory, a branch of mathematics, the rank of an undirected graph is defined as the number n − c, where n is the number of vertices and c is the number of connected components of the graph.[1] Equivalently, the rank of a graph is the rank of the oriented incidence matrix associated with the graph.[2]
Analogously, the nullity of an undirected graph is the nullity of its incidence matrix, given by the formula m − n + c, where n and c are as above and m is the number of edges in the graph. The nullity is equal to the first Betti number of the graph. The sum of the rank and the nullity is the number of edges.
See also
Notes
- ↑ Weisstein, Eric W. "Graph Rank." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphRank.html
- ↑ 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.
References
- Chen, Wai-Kai (1976), Applied Graph Theory, North Holland Publishing Company, ISBN 0-7204-2371-6.
This article is issued from Wikipedia - version of the Tuesday, October 08, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.