Матрица инциденций

Другой матрицей, связанной с графом G, в котором помечены и вершины и ребра, является матрица инциденцийB=||bij||. В этой (pq)-матрице bij=1, если vi иxj инцидентны, и bij=0 в противном случае. Как и матрица смежностей, матрица инциденций определяет граф G с точностью до изоморфизма. На самом деле уже любые р-1 строки матрицы В определяют G, поскольку каждая строка равна сумме по модулю 2 всех остальных строк.

Следующая теорема связывает матрицу смежностей реберного графа графа G и матрицу инциденций графа G. Обозначим через ВТ матрицу, транспонированную к матрице В.

Теорема.Для любого (р, q)-графа G с матрицей инциденций В

A(L(G))=BTB-2Iq,

где Iq— единичная матрица порядка q.

Пусть М — матрица, полученная из матрицы -А заменой i-ro элемента главной диагонали на deg ui . В классической работе Кирхгофа приведена

Теорема(матричная теорема о деревьях). Пусть G - связный помеченный граф с матрицей смежностей А. Тогда все алгебраические дополнения матрицы М равны между собой и их общее значение есть число остовов графа G.

Лемма(а).Если Р и Q — соответственно (mn)-матрица и (nm)-матрица (m<n), то определитель матрицы PQ равен сумме произведений соответствующих главных определителей матриц Р и Q.