Top Qs
Timeline
Chat
Perspective

Rank (graph theory)

Characteristic of undirected graphs From Wikipedia, the free encyclopedia

Remove ads
Remove ads

In graph theory, a branch of mathematics, the rank of an undirected graph has two unrelated definitions. Let n equal the number of vertices of the graph.

Analogously, the nullity of the graph is the nullity of its adjacency matrix, which equals n r.
Analogously, the nullity of the graph is the nullity of its oriented 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.
Remove ads

Examples

Summarize
Perspective

A sample graph and matrix:

Thumb
An undirected graph.

(corresponding to the four edges, e1–e4):

1234
1 0111
2 1000
3 1001
4 1010
=

In this example, the matrix theory rank of the matrix is 4, because its column vectors are linearly independent.

Remove ads

See also

Notes

References

Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads