Ранг неорієнтованого графа має два не пов язані між собою визначення Нехай n дорівнює числу вершин графа У термінах теор

Ранг неорієнтованого графа має два не пов'язані між собою визначення. Нехай $n$ дорівнює числу вершин графа.

У термінах теорії матриць ранг $r$ неорієнтованого графа визначається як ранг його матриці суміжності.

Аналогічно, ^[en] графа визначається як дефект ядра його матриці суміжності, що дорівнює

n - r

.

У термінах теорії матроїдів графів ранг неорієнтованого графа визначається як число $n - c$ , де $c$ — число компонент зв'язності графа. Еквівалентно, ранг графа — це ранг асоційованої з ним орієнтованої матриці інцидентності.

Аналогічно, ^[en] графа — це дефект ядра орієнтованої матриці інцидентності, що задається формулою

m - n + c

, де n та c визначено вище, а m — число ребер графа. Дефект дорівнює першому числу Бетті графа. Сума рангу та дефекту дає число ребер.

Див. також

Jerrold W. Grossman, Devadatta M. Kulkarni, Irwin E. Schochetman. On the minors of an incidence matrix and its Smith normal form // Linear Algebra and its Applications. — 1995. — Т. 218. — С. 213–224. — DOI:10.1016/0024-3795(93)00173-W.
Wai-Kai Chen. Applied Graph Theory. — North Holland Publishing Company, 1976. — .
Hedetniemi S. T., Jacobs D. P., Laskar R. Inequalities involving the rank of a graph. // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1989. — Т. 6. — С. 173–176.
The rank of a graph after vertex addition // Linear Algebra and its Applications. — 1997. — Т. 265. — С. 55–69.