Ранг неорієнтованого графа має два не пов'язані між собою визначення. Нехай дорівнює числу вершин графа.
У термінах теорії матриць ранг неорієнтованого графа визначається як ранг його матриці суміжності.
Аналогічно, графа визначається як дефект ядра його матриці суміжності, що дорівнює .
У термінах теорії матроїдів графів ранг неорієнтованого графа визначається як число , де — число компонент зв'язності графа. Еквівалентно, ранг графа — це ранг асоційованої з ним орієнтованої матриці інцидентності.
Аналогічно, графа — це дефект ядра орієнтованої матриці інцидентності, що задається формулою , де n та c визначено вище, а m — число ребер графа. Дефект дорівнює першому числу Бетті графа. Сума рангу та дефекту дає число ребер.
Див. також Контурний ранг Циклічний ранг
Примітки
Література