Матрица Кирхгофа

Еще одной формой матричного представления неориентированных графов является матрица Кирхгофа.

Пусть - граф порядка и . Матрицу для графа определим следующим образом:

2.12

Матрица называется матрицей Кирхофа графа . Сумма элементов каждой строки и каждого столбца этой матрицы равна нулю. На рис 2.7 приведен граф и соответствующая ему матрица Кирхгофа.

.

Рис. 2.7