Матрица Кирхгофа — различия между версиями
| Строка 1: | Строка 1: | ||
| + | == Определение матрицы Кирхгофа == | ||
| + | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | '''Матрицей Кирхгофа''' простого графа <math>G = (V,E) </math> называется матрица <math> K (V \times E) = \parallel k_{i,j} \parallel </math>, элементы которой определяются равенством:<math> | + | '''Матрицей Кирхгофа''' простого графа <math>G = (V,E) </math> называется матрица <math> K (V \times E) = \parallel k_{i,j} \parallel </math>, элементы которой определяются равенством: <math> |
k_{i,j} = | k_{i,j} = | ||
\begin{cases} | \begin{cases} | ||
| Строка 11: | Строка 13: | ||
}} | }} | ||
Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении i-й строки и j-го столбца (<math>i \ne j</math>) стоит -1, если вершины с номерами i и j смежны, и 0 в противном случае. | Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении i-й строки и j-го столбца (<math>i \ne j</math>) стоит -1, если вершины с номерами i и j смежны, и 0 в противном случае. | ||
| + | |||
| + | == Некоторые свойства == | ||
| + | |||
| + | 1. Матрица Кирхгофа является симметрической (т.е. симметрична относительно главной диагонали). | ||
| + | |||
| + | 2. Связь с матрицей смежности: | ||
| + | <math> K = | ||
| + | \begin{pmatrix} | ||
| + | deg(v_1) & 0 & \cdots & 0 \\ | ||
| + | 0 & deg(v_2) & \cdots & 0 \\ | ||
| + | \vdots & \vdots & \ddots & \vdots \\ | ||
| + | 0 & 0 & \cdots & deg(v_n) | ||
| + | \end{pmatrix} - A, | ||
| + | </math> | ||
| + | |||
| + | где ''A'' - матрица смежности графа ''G''. | ||
| + | |||
| + | 3. [[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]: <math> K = I \cdot I^T, </math> где <math>I</math> - матрица инцидентности с некоторой ориентацией. | ||
Версия 07:21, 7 октября 2010
Определение матрицы Кирхгофа
| Определение: |
| Матрицей Кирхгофа простого графа называется матрица , элементы которой определяются равенством: |
Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении i-й строки и j-го столбца () стоит -1, если вершины с номерами i и j смежны, и 0 в противном случае.
Некоторые свойства
1. Матрица Кирхгофа является симметрической (т.е. симметрична относительно главной диагонали).
2. Связь с матрицей смежности:
где A - матрица смежности графа G.
3. Связь с матрицей инцидентности: где - матрица инцидентности с некоторой ориентацией.
