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

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

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

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

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

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

См. также

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