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

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

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

В терминах теории матроидов графов ранг неориентированного графа определяется как число , где — число связных компонент графаWeisstein, Eric W. "Graph Rank." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphRank.html . Эквивалентно, ранг графа — это ранг ориентированной матрицы инцидентности, ассоциированной с графом. Аналогично, графа — это ориентированной матрицы инцидентности, который задаётся формулой , где n и c определены выше, а m — число рёбер графа. Дефект равен первому числу Бетти графа. Сумма ранга и дефекта даёт число рёбер.

См. также Контурный ранг Циклический ранг

Примечания

Литература

Категория:Алгебраическая теория графов Категория:Связность графа Категория:Инварианты графов