Rank (graph theory)
Encyclopedia
In graph theory
, a branch of mathematics, the rank of an undirected graph is defined as the number , where is the number of vertices
and 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.
Analogously, the nullity of an undirected graph is the nullity of its 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
of the graph. The sum of the rank and the nullity is the number of edges.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a branch of mathematics, the rank of an undirected graph is defined as the number , where is the number of vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
and is the number of connected components
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
of the graph. Equivalently, the rank of a graph is the rank
Rank (linear algebra)
The column rank of a matrix A is the maximum number of linearly independent column vectors of A. The row rank of a matrix A is the maximum number of linearly independent row vectors of A...
of the oriented incidence matrix
Incidence matrix
In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related ...
associated with the graph.
Analogously, the nullity of an undirected graph is the nullity of its 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
Betti number
In algebraic topology, a mathematical discipline, the Betti numbers can be used to distinguish topological spaces. Intuitively, the first Betti number of a space counts the maximum number of cuts that can be made without dividing the space into two pieces....
of the graph. The sum of the rank and the nullity is the number of edges.