Ранг матрицы графа

[julia88]

Связный граф (n вершин, m ребер) задан матрицей A, строки которой соответствуют вершинам графа, столбцы - ребрам. Если в графе присутствует ребро (i,j), то в соответствующем столбце i-ый элемент равен 1, j-ый элемент равен -1,остальные элементы равны нулю. Требуется найти ранг матрицы A.
Я не могу понять, как это считать.
Ясно, что в каждом столбце будет один единичный элемент, один, равный -1, а остальные нули. Переходить как-то к матрицам меньшего размера, используя разложение по строке? Помогите, пожалуйста.

[Brukvalub]

julia88 писал(а):

Переходить как-то к матрицам меньшего размера, используя разложение по строке? Помогите, пожалуйста.

Ранг матрицы равен количеству ее линейно независимых строк (столбцов).