WikiSort.ru - Не сортированное

Матрица Кирхгофа — одно из представлений конечного графа с помощью матрицы. Матрица Кирхгофа представляет дискретный оператор Лапласа для графа. Она используется для подсчета остовных деревьев данного графа (матричная теорема о деревьях), а также в спектральной теории графов.

Определение

Дан простой граф ${\displaystyle \ G}$ с ${\displaystyle \ |V(G)|=n}$ вершинами. Тогда матрица Кирхгофа ${\displaystyle \ K=(k_{i,j})_{n\times n}}$ данного графа будет определяться следующим образом:

${\displaystyle \ k_{i,j}:={\begin{cases}\deg(v_{i})&{\text{при}}\ i=j,\\-1&{\text{при}}\ (v_{i},v_{j})\in E(G),\\0&{\text{в противном случае}}.\end{cases}}}$

Также матрицу Кирхгофа можно определить как разность матриц

${\displaystyle \ K=D-A,}$

где ${\displaystyle \ A}$ — это матрица смежности данного графа, а ${\displaystyle \ D=(d_{i,j})_{n\times n}}$ — матрица, на главной диагонали которой степени вершин графа, а остальные элементы — нули:

${\displaystyle \ d_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j,\\0&{\mbox{otherwise}}.\end{cases}}}$

Если граф является взвешенным, то определение матрицы Кирхгофа обобщается. В этом случае элементами главной диагонали матрицы Кирхгофа будут суммы весов рёбер, инцидентных соответствующей вершине. Для смежных (связанных) вершин ${\displaystyle \ k_{i,j}=-c(v_{i},v_{j})}$ , где ${\displaystyle \ c(v_{i},v_{j})}$ — это вес (проводимость) ребра. Для различных не смежных (не связанных) вершин полагается ${\displaystyle \ k_{i,j}=0}$ .

${\displaystyle \ k_{i,j}:={\begin{cases}\sum _{\begin{smallmatrix}u\in V(G)\\(v_{i},u)\in E(G)\end{smallmatrix}}^{}c(v_{i},u)&{\mbox{if}}\ i=j,\\-c(v_{i},v_{j})&{\mbox{if}}\ (v_{i},v_{j})\in E(G),\\0&{\mbox{otherwise}}.\end{cases}}}$

Для взвешенного графа матрица смежности ${\displaystyle \ A}$ записывается с учетом проводимостей ребер, а на главной диагонали матрицы ${\displaystyle \ D}$ будут суммы проводимостей ребер инцидентных соответствующим вершинам.

${\displaystyle \ d_{i,j}:={\begin{cases}\sum _{\begin{smallmatrix}u\in V(G)\\(v_{i},u)\in E(G)\end{smallmatrix}}^{}c(v_{i},u)&{\mbox{if}}\ i=j,\\0&{\mbox{otherwise}}.\end{cases}}}$

Пример

Пример матрицы Кирхгофа простого графа.

Помеченный граф	Матрица Кирхгофа
	${\displaystyle \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)}$

Свойства

• Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:

  ${\displaystyle \ \sum _{i=1}^{|V(G)|}k_{i,j}=0}$ .

• Определитель матрицы Кирхгофа равен нулю:

  ${\displaystyle \det K=0}$

• Матрица Кирхгофа простого графа симметрична:

  ${\displaystyle \ k_{i,j}=k_{j,i}\quad i,j=1,\ldots ,|V(G)|}$ .

• Все алгебраические дополнения ${\displaystyle \ K_{(ij)}}$ симметричной матрицы Кирхгофа равны между собой — постоянная матрицы Кирхгофа. Для простого графа значение данной постоянной совпадает с числом всех возможных остовов графа (см. Матричная теорема о деревьях).

• Если взвешенный граф представляет собой электрическую сеть, где вес каждого ребра соответствует его проводимости, то миноры матрицы Кирхгофа позволяют вычислить резистивное расстояние (resistance distance) ${\displaystyle \ R_{ij}}$ между точками ${\displaystyle \ i}$ и ${\displaystyle \ j}$ данной сети:

  ${\displaystyle \ R_{ij}={\frac {K^{(i,j)}}{K_{(ij)}}}}$ ,

здесь ${\displaystyle \ K_{(ij)}}$  — постоянная (алгебраическое дополнение) матрицы Кирхгофа, а ${\displaystyle \ K^{(i,j)}}$  — алгебраическое дополнение 2-го порядка, то есть определитель матрицы, получающейся из матрицы Кирхгофа вычеркиванием двух строк и двух столбцов ${\displaystyle \ i,j}$ .

• Существует алгоритм восстановления матрицы Кирхгофа по матрице сопротивлений ${\displaystyle R_{ij}}$ .
  • 0 является собственным значением матрицы (соответствующий собственный вектор — все единицы), кратность его равна числу связных компонент графа.
  • Остальные собственные значения положительны. Второе по малости значение Фидлер назвал индексом связности графа, соответствующий собственный вектор — вектор Фиддлера.

См. также

• Матричная теорема о деревьях
• Оператор Лапласа