Ранг (теорія графів)
Ранг неорієнтованого графа має два не пов'язані між собою визначення. Нехай n дорівнює числу вершин графа.
- У термінах теорії матриць ранг r неорієнтованого графа визначається як ранг його матриці суміжності.
- Аналогічно, дефект[en] графа визначається як дефект ядра його матриці суміжності, що дорівнює n − r.
- У термінах теорії матроїдів графів ранг неорієнтованого графа визначається як число n − c, де c — число компонент зв'язності графа[1]. Еквівалентно, ранг графа — це ранг асоційованої з ним орієнтованої матриці інцидентності[2].
- Аналогічно, дефект[en] графа — це дефект ядра орієнтованої матриці інцидентності, що задається формулою m − n + c, де n та c визначено вище, а m — число ребер графа. Дефект дорівнює першому числу Бетті графа. Сума рангу та дефекту дає число ребер.
Див. також
ред.Примітки
ред.- ↑ Weisstein, Eric W. Ранг графа(англ.) на сайті Wolfram MathWorld.
- ↑ 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:.
- 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.