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

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

Содержание

1 Определение
2 Пример
3 Свойства
4 См. также

Определение

Дан простой граф с вершинами. Тогда матрица Кирхгофа данного графа будет определяться следующим образом:

$k_{i,j}:= \begin{cases} \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ (v_i,v_j) \in E(G) \\ 0 & \mbox{otherwise}. \end{cases}$

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

$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}$

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

где — это матрица смежности данного графа, а — матрица, на главной диагонали которой степени вершин графа, а остальные элементы — нули:

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

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

$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}$

Пример

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

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

Свойства

Матрица Кирхгофа симметрическая:

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

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

См. также

Матричная теорема о деревьях

Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её.

Lt304888.ru

Туристические услуги

Рекомендуем