Связь матрицы Кирхгофа и матрицы инцидентности

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Пусть G — произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный орграф на том же самом множестве вершин будем называть ориентацией графа G.


Лемма:
Пусть K матрица Кирхгофа графа G, I матрица инцидентности G с некоторой ориентацией. Тогда K = I \cdot I^T.
Доказательство:
\triangleright
При умножении i-й строки исходной матрицы I на j-й столбец транспонированной матрицы I^T перемножаются i-я и j-я строки исходной матрицы. При умножении i-й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов i-й строки, которая равна, очевидно, \deg(v_i). Пусть теперь i \ne j. Если (v_i, v_j) \in E, то существует ровно одно ребро, соединяющее v_i и v_j, следовательно результат перемножения i-й и j-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
\triangleleft
Граф Матрица Кирхгофа Матрица инцидентности
Link kirhgof matrix 1.png \left(\begin{array}{rrrrrr}  2 & -1 &  0 &  0 & -1 &  0\\ -1 &  3 & -1 &  0 & -1 &  0\\  0 & -1 &  2 & -1 &  0 &  0\\  0 &  0 & -1 &  3 & -1 & -1\\ -1 & -1 &  0 & -1 &  3 &  0\\  0 &  0 &  0 & -1 &  0 &  1\\ \end{array}\right) \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix}

[править] См. также

[править] Источники информации

  • Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты