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

Определение:

Матрицей Кирхгофа простого графа [math]G = (V,E) [/math] называется матрица [math] K (V \times E) = \parallel k_{i,j} \parallel [/math], элементы которой определяются равенством:[math] k_{i,j} = \begin{cases} \deg(v_i), \ i = j \\ -1, \ (v_i,v_j) \in E \\ 0, \mbox{ else}. \end{cases} [/math]

Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении i-й строки и j-го столбца ([math]i \ne j[/math]) стоит -1, если вершины с номерами i и j смежны, и 0 в противном случае.