Rank (graph theory)
{{Short description|Characteristic of undirected graphs}}
{{Graph connectivity sidebar}}
In graph theory, a branch of mathematics, the rank of an undirected graph has two unrelated definitions. Let {{math|n}} equal the number of vertices of the graph.
- In the matrix theory of graphs the rank {{math|r}} of an undirected graph is defined as the rank of its adjacency matrix.
:Analogously, the nullity of the graph is the nullity of its adjacency matrix, which equals {{math|n − r}}.
- In the matroid theory of graphs the rank of an undirected graph is defined as the number {{math|n − c}}, where {{math|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.{{citation
| last1 = Grossman | first1 = Jerrold W.
| last2 = Kulkarni | first2 = Devadatta M.
| last3 = Schochetman | first3 = Irwin E.
| doi = 10.1016/0024-3795(93)00173-W
| journal = Linear Algebra and Its Applications
| mr = 1324059
| pages = 213–224
| title = On the minors of an incidence matrix and its Smith normal form
| volume = 218
| year = 1995| doi-access = free
}}. See in particular the discussion on p. 218.
:Analogously, the nullity of the graph is the nullity of its oriented incidence matrix, given by the formula {{math|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.
Examples
A sample graph and matrix:
Image:Labeled undirected graph.svg
(corresponding to the four edges, e1–e4):
| {| align=left class=wikitable | ||||
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1
|0||1||1||1 | ||||
| 2
|1||0||0||0 | ||||
| 3
|1||0||0||1 | ||||
| 4
|1||0||1||0 |
| =
|
\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
References
- {{citation|last=Chen|first=Wai-Kai|title=Applied Graph Theory|publisher=North Holland Publishing Company|year=1976|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), [https://www.sciencedirect.com/science/article/pii/S0024379596005137/pdf?md5=d4fb4bfce95f03fecb3e51f0c4d3af0d&isDTMRedir=Y&pid=1-s2.0-S0024379596005137-main.pdf&_valck=1 The rank of a graph after vertex addition]. Linear Algebra and its Applications, vol. 265, pp. 55–69.