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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (Матрица, транспонированная данной…)
Строка 10: Строка 10:
  
 
|proof=
 
|proof=
При умножении i-й строки исходной матрицы <tex>I</tex> на j-й столбец трансонированной ей матрицы <tex>I^T </tex> перемножаются i-я и j-я строки исходной матрицы. При умножении i-й строки саму на себя на диагонали полученной матрицы будет сумма квадратов элементов i-й строки, которая равна, очевидно, <tex>deg(v_i)</tex>. Пусть теперь <tex>i \ne j</tex>. Если <tex> (v_i, v_j) \in E </tex>,  то существует ровно одно ребро, соединяющее <tex> v_i </tex> и <tex> v_j </tex>, следовательно результат перемножения i-й и j-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
+
При умножении <tex>i</tex>-й строки исходной матрицы <tex>I</tex> на <tex>j</tex>-й столбец транспонированной матрицы <tex>I^T </tex> перемножаются i-я и j-я строки исходной матрицы. При умножении <tex>i</tex>-й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов <tex>i</tex>-й строки, которая равна, очевидно, <tex>deg(v_i)</tex>. Пусть теперь <tex>i \ne j</tex>. Если <tex> (v_i, v_j) \in E </tex>,  то существует ровно одно ребро, соединяющее <tex> v_i </tex> и <tex> v_j </tex>, следовательно результат перемножения <tex>i</tex>-й и <tex>j</tex>-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
 
}}
 
}}
  

Версия 23:58, 22 января 2011

Определение:
Пусть [math]G[/math] - произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный орграф на том же самом множестве вершин будем называть ориентацией графа [math]G[/math].


Лемма:
Пусть [math]K[/math]- матрица Кирхгофа графа [math]G[/math], [math]I[/math]- матрица инцидентности [math]G[/math] с некоторой ориентацией. Тогда [math]K = I \cdot I^T.[/math]
Доказательство:
[math]\triangleright[/math]
При умножении [math]i[/math]-й строки исходной матрицы [math]I[/math] на [math]j[/math]-й столбец транспонированной матрицы [math]I^T [/math] перемножаются i-я и j-я строки исходной матрицы. При умножении [math]i[/math]-й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов [math]i[/math]-й строки, которая равна, очевидно, [math]deg(v_i)[/math]. Пусть теперь [math]i \ne j[/math]. Если [math] (v_i, v_j) \in E [/math], то существует ровно одно ребро, соединяющее [math] v_i [/math] и [math] v_j [/math], следовательно результат перемножения [math]i[/math]-й и [math]j[/math]-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
[math]\triangleleft[/math]

См. также

Матрица инцидентности графа

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

Подсчет числа остовных деревьев с помощью матрицы Кирхгофа

Источники

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