15.03.2021

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


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

Определение

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

  k i , j := { deg ⁡ ( v i ) при   i = j , − 1 при   ( v i , v j ) ∈ E ( G ) , 0 в противном случае . {displaystyle k_{i,j}:={egin{cases}deg(v_{i})&{ ext{при}} i=j,-1&{ ext{при}} (v_{i},v_{j})in E(G),&{ ext{в противном случае}}.end{cases}}}

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

  K = D − A , {displaystyle K=D-A,}

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

  d i , j := { deg ⁡ ( v i ) при   i = j , 0 в противном случае . {displaystyle d_{i,j}:={egin{cases}deg(v_{i})&{ ext{при}} i=j,&{ ext{в противном случае}}.end{cases}}}

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

  k i , j := { ∑ u ∈ V ( G ) ( v i , u ) ∈ E ( G ) c ( v i , u ) при   i = j , − c ( v i , v j ) при   ( v i , v j ) ∈ E ( G ) , 0 в противном случае . {displaystyle k_{i,j}:={egin{cases}sum _{egin{smallmatrix}uin V(G)(v_{i},u)in E(G)end{smallmatrix}}^{}c(v_{i},u)&{ ext{при}} i=j,-c(v_{i},v_{j})&{ ext{при}} (v_{i},v_{j})in E(G),&{ ext{в противном случае}}.end{cases}}}

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

  d i , j := { ∑ u ∈ V ( G ) ( v i , u ) ∈ E ( G ) c ( v i , u ) if   i = j , 0 otherwise . {displaystyle d_{i,j}:={egin{cases}sum _{egin{smallmatrix}uin V(G)(v_{i},u)in E(G)end{smallmatrix}}^{}c(v_{i},u)&{mbox{if}} i=j,&{mbox{otherwise}}.end{cases}}}

Пример

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

Свойства

  • Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:   ∑ i = 1 | V ( G ) | k i , j = 0 {displaystyle sum _{i=1}^{|V(G)|}k_{i,j}=0} .
  • Определитель матрицы Кирхгофа равен нулю: det K = 0 {displaystyle det K=0}
  • Матрица Кирхгофа простого графа симметрична:   k i , j = k j , i i , j = 1 , … , | V ( G ) | {displaystyle k_{i,j}=k_{j,i}quad i,j=1,ldots ,|V(G)|} .
  • Все алгебраические дополнения   K ( i j ) {displaystyle K_{(ij)}} симметричной матрицы Кирхгофа равны между собой — постоянная матрицы Кирхгофа. Для простого графа значение данной постоянной совпадает с числом всех возможных остовов графа (см. Матричная теорема о деревьях).
  • Если взвешенный граф представляет собой электрическую сеть, где вес каждого ребра соответствует его проводимости, то миноры матрицы Кирхгофа позволяют вычислить резистивное расстояние (resistance distance)   R i j {displaystyle R_{ij}} между точками   i {displaystyle i} и   j {displaystyle j} данной сети:   R i j = K ( i , j ) K ( i j ) {displaystyle R_{ij}={frac {K^{(i,j)}}{K_{(ij)}}}} ,
здесь   K ( i j ) {displaystyle K_{(ij)}} — постоянная (алгебраическое дополнение) матрицы Кирхгофа, а   K ( i , j ) {displaystyle K^{(i,j)}} — алгебраическое дополнение 2-го порядка, то есть определитель матрицы, получающейся из матрицы Кирхгофа вычеркиванием двух строк и двух столбцов   i , j {displaystyle i,j} .
  • Существует алгоритм восстановления матрицы Кирхгофа по матрице сопротивлений R i j {displaystyle R_{ij}} .
    • 0 является собственным значением матрицы (соответствующий собственный вектор — все единицы), кратность его равна числу связных компонент графа.
    • Остальные собственные значения положительны. Второе по малости значение Фидлер назвал индексом связности графа, соответствующий собственный вектор — вектор Фиддлера.

Похожие новости:

Эпсилон-окрестность

Эпсилон-окрестность
ε {displaystyle varepsilon } -окрестность множества в функциональном анализе и смежных дисциплинах — это такое множество, каждая точка которого удалена от данного множества

Марковский момент времени

Марковский момент времени
Марковский момент времени (в теории случайных процессов) — это случайная величина, не зависящая от будущего рассматриваемого случайного процесса. Дискретный случай Пусть дана последовательность

Спектральная теория графов

Спектральная теория графов
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как

Функция Гёделя

Функция Гёделя
Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел. Определение Функцией Геделя Γ ( x
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Эффективность продвижения в социальных сетях: проверено Святославом Гусевым
Эффективность продвижения в социальных сетях: проверено Святославом Гусевым
Продвижение товаров и услуг через социальные сети стремительно набирает свою популярность. Такой...
Критерии выбора надежной криптобиржи
Критерии выбора надежной криптобиржи
Современный рынок криптовалютных бирж включает в себя множество платформ, которые отличаются по...
Как вернуть мебели внешний вид и функциональность
Как вернуть мебели внешний вид и функциональность
Если мебель при длительной эксплуатации потеряла свой внешний вид, вернуть ей презентабельность...
Все новости