Rank (graph theory)

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. 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 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

References

  • Chen, Wai-Kai (1976), Applied Graph Theory, North Holland Publishing Company, ISBN 0720423716 .

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Nullity (graph theory) — The nullity of a graph is defined as the number:: m = b n + cwhere b is the number of edges, n is the number of nodes and c the number of components. Equivalently, the nullity of a graph is the dimension of the null space of the oriented… …   Wikipedia

  • Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… …   Wikipedia

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

  • Rank — is a very broad term with several meanings. As a noun it is usually related to a relative position or to some kind of ordering (see also ranking). As an adjective it is used to mean profuse, conspicuous, absolute, or unpleasant, especially in… …   Wikipedia

  • Rank (mathematics) — Rank means a wide variety of things in mathematics, including: * Rank (linear algebra) * Rank of a tensor * Rank of an abelian group * Rank of a Lie group * Percentile rank * Rank (differential topology) * Rank of a vector bundle * Rank (set… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Rank of a group — For the dimension of the Cartan subgroup, see Rank of a Lie group In the mathematical subject of group theory, the rank of a group G , denoted rank( G ), can refer to the smallest cardinality of a generating set for G , that is:… …   Wikipedia

  • Cycle rank — In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi (Eggan 1963). Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a …   Wikipedia

  • Distance-hereditary graph — A distance hereditary graph. In graph theoretic mathematics, a distance hereditary graph (also called a completely separable graph)[1] is a graph in which the distances in any connected induced subgraph are the same as they are in the original… …   Wikipedia

  • Signed graph — In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.Formally, a signed graph Sigma; is a pair ( G , sigma;) that consists of a graph G = ( V , E ) and a sign mapping or… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”