In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a branch of mathematics, the rank of an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
has two unrelated definitions. Let equal the number of
vertices of the graph.
* In the
matrix theory
In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object.
For example,
\begi ...
of graphs the rank of an undirected graph is defined as the rank of its
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
.
:Analogously, the
nullity of the graph is the nullity of its adjacency matrix, which equals .
* In the
matroid theory
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in ...
of graphs the rank of an undirected graph is defined as the number , where is the number of
connected components of the graph. Equivalently, the rank of a graph is the
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
of the oriented
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
associated with the graph.
[. 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 , 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
In algebraic topology, the Betti numbers are used to distinguish topological spaces based on the connectivity of ''n''-dimensional simplicial complexes. For the most reasonable finite-dimensional spaces (such as compact manifolds, finite simplicia ...
of the graph. The sum of the rank and the nullity is the number of edges.
Examples
A sample graph and matrix:
(corresponding to the four edges, e1–e4):
In this example, the matrix theory rank of the matrix is 4, because its column vectors are linearly independent.
See also
*
Circuit rank
In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...
*
Cycle rank
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close a
digraph is to a directed acyclic graph (DAG), in the sense that a DAG has
...
*
Nullity (graph theory)
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)
The rank of a graph after vertex addition ''Linear Algebra and its Applications'', vol. 265, pp. 55–69.
Algebraic graph theory
Graph connectivity
Graph invariants