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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть <tex>G</tex> - произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный [[ориентированный граф|орграф]] на том же самом множестве вершин будем называть '''ориентацией''' графа <tex>G</tex>.  
+
Пусть <tex>G</tex> произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный [[Основные определения теории графов#Ориентированные графы|орграф]] на том же самом множестве вершин будем называть '''ориентацией''' графа <tex>G</tex>.  
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Пусть <tex>K</tex>- матрица Кирхгофа графа <tex>G</tex>, <tex>I</tex>- матрица инцидентности <tex>G</tex> с некоторой ориентацией. Тогда  
+
Пусть <tex>K</tex> — [[Матрица Кирхгофа| матрица Кирхгофа]] графа <tex>G</tex>, <tex>I</tex> — [[Матрица инцидентности графа| матрица инцидентности]] <tex>G</tex> с некоторой ориентацией. Тогда  
 
  <tex>K = I \cdot I^T.</tex>
 
  <tex>K = I \cdot I^T.</tex>
  
 
|proof=
 
|proof=
При умножении <tex>i</tex>-й строки исходной матрицы <tex>I</tex> на <tex>j</tex>-й столбец транспонированной матрицы <tex>I^T </tex> перемножаются <tex>i</tex>-я и <tex>j</tex>-я строки исходной матрицы. При умножении <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 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
+
При умножении <tex>i</tex>-й строки исходной матрицы <tex>I</tex> на <tex>j</tex>-й столбец транспонированной матрицы <tex>I^T </tex> перемножаются <tex>i</tex>-я и <tex>j</tex>-я строки исходной матрицы. При умножении <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>-й строк равен <tex>-1</tex>, в противном случае он равен <tex>0</tex> в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
 
}}
 
}}
 +
{|class="wikitable"
 +
!Граф
 +
!Матрица Кирхгофа
 +
!Матрица инцидентности
 +
|-
 +
|[[Файл:Link_kirhgof_matrix_1.png|200px]]
 +
|<tex>\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)</tex>
 +
|<tex>\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}</tex>
 +
|}
  
== См. также ==
+
==См. также==
[[Матрица инцидентности графа]]
+
*[[Матрица Кирхгофа]]
 +
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
 +
*[[Количество помеченных деревьев]]
 +
*[[Коды Прюфера]]
  
[[Матрица Кирхгофа]]
+
==Источники информации==
  
[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
+
*Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
 
 
==Источники==
 
 
 
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Остовные деревья ]]
 +
[[Категория: Свойства остовных деревьев ]]

Текущая версия на 19:25, 4 сентября 2022

Определение:
Пусть [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] перемножаются [math]i[/math]-я и [math]j[/math]-я строки исходной матрицы. При умножении [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]-й строк равен [math]-1[/math], в противном случае он равен [math]0[/math] в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
[math]\triangleleft[/math]
Граф Матрица Кирхгофа Матрица инцидентности
Link kirhgof matrix 1.png [math]\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)[/math] [math]\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}[/math]

См. также

Источники информации

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