Ранг (теорія графів)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Аналогічно, дефект[en] графа визначається як дефект ядра його матриці суміжності, що дорівнює nr.
Аналогічно, дефект[en] графа — це дефект ядра орієнтованої матриці інцидентності, що задається формулою mn + c, де n та c визначено вище, а m — число ребер графа. Дефект дорівнює першому числу Бетті графа. Сума рангу та дефекту дає число ребер.

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Weisstein, Eric W. Ранг графа(англ.) на сайті Wolfram MathWorld.
  2. Grossman, Kulkarni, Schochetman, 1995, с. 218.

Література

[ред. | ред. код]
  • 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. — ISBN 0-7204-2371-6.
  • 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.