WikiSort.ru - Не сортированное

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

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

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

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

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

См. также

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.