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

Пусть G -- помеченный граф, V(G) = {1, 2, 3, …, N}. Матрицей Кирхгофа графа G называется N´N-матрица K(G) = (Kij), такая, что:

Kij =

Матрица Кирхгофа K(G) симметрична, на главной диагонали расположена степенная последовательность графа G. Кроме того, сумма элементов каждой строки (столбца) равна 0. (Матрица с последним условием обладает тем свойством, что алгебраические дополнения всех элементов такой матрицы равны между собой.) Как и для матрицы смежности, справедлива

Теорема. Графы изоморфны тогда и только тогда, когда их матрицы Кирхгофа получаются друг из друга путём парных перестановок одинаковых строк и столбцов.

< Предыдущая		Следующая >