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

Ранг неориентированного графа имеет два не связанных друг с другом определения. Пусть n равно числу вершин графа.

• В терминах теории матриц ранг r неориентированного графа определяется как ранг его матрицы смежности.

Аналогично, дефект^[англ.] графа определяется как дефект ядра его матрицы смежности, что равно n − r.

• В терминах теории матроидов графов ранг неориентированного графа определяется как число n − c, где c — число связных компонент графа^[1]. Эквивалентно, ранг графа — это ранг ориентированной матрицы инцидентности, ассоциированной с графом^[2].

Аналогично, дефект^[англ.] графа — это дефект ядра^[англ.]* ориентированной матрицы инцидентности, который задаётся формулой m − n + c, где n и c определены выше, а m — число рёбер графа. Дефект равен первому числу Бетти графа. Сумма ранга и дефекта даёт число рёбер.

См. также

• Контурный ранг
• Циклический ранг
• Дефект^[англ.]

Примечания

1. Weisstein, Eric W. "Graph Rank." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphRank.html Архивная копия от 23 сентября 2017 на Wayback Machine
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.