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

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

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

Содержание

Определение

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

\ 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 = D - A,

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

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

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

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

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

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

Пример

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

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

Свойства

  • Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
\ \sum_{i=1}^{|V(G)|} k_{i,j} = 0
  • Определитель матрицы Кирхгофа равен нулю:
\ det (K)=0
\ k_{i,j} = k_{j,i}~~ i,j=1...|V(G)|
  • Все алгебраические дополнения \ K_{(ij)} симметричной матрицы Кирхгофа равны между собой — постоянная матрицы Кирхгофа. Для простого графа значение данной постоянной совпадает с числом всех возможных остовов графа (см. Матричная теорема о деревьях).
  • Если взвешенный граф представляет собой электрическую сеть, то миноры матрицы Кирхгофа позволяют вычислить резистивное расстояние (resistance distance) \ R_{ij} между точками \ i и \ j данной сети:

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

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

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


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

См. также


Формула

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Матрица Кирхгофа" в других словарях:

  • матрица контуров — 216 матрица контуров Прямоугольная матрица, строки которой соответствуют связям графа, а столбцы ветвям направленного графа электрической цепи, элементы которой равны нулю, единице или минус единице, если данная ветвь соответственно не… …   Словарь-справочник терминов нормативно-технической документации

  • Матрица контуров связей и сечений ребер — 16. Матрица контуров связей и сечений ребер Матрица коэффициентов в системе уравнений второго закона Кирхгофа, записанных для контуров связей графа радиоэлектронной схемы и выраженных явно относительно напряжений связей графа радиоэлектронной… …   Словарь-справочник терминов нормативно-технической документации

  • Метод непосредственного применения законов Кирхгофа — для расчета электрической цепи заключается в составлении системы из В уравнений с В неизвестными (B количество ветвей в рассматриваемой цепи) по двум законам Кирхгофа и последующем их решении. Содержание 1 Описание метода расчета …   Википедия

  • Топологические матрицы — В этой статье отсутствует вступление. Пожалуйста, допишите вводную секцию, кратко раскрывающую тему статьи. Топологические матрицы двумерные массивы, содержащие полное описание графа. Матрица инциденций таблица, котор …   Википедия

  • Метод узловых потенциалов — метод расчета электрических цепей путём записи системы линейных алгебраических уравнений, в которой неизвестными являются потенциалы в узлах цепи. В результате применения метода определяются потенциалы во всех узлах цепи, а также, при… …   Википедия

  • Метод контурных токов — Метод контурных токов  метод сокращения размерности системы уравнений, описывающей электрическую цепь. Содержание 1 Основные принципы 2 Построение системы контуров …   Википедия

  • ГОСТ 23070-78: Анализ и оптимизация на ЭВМ радиоэлектронных схем. Термины и определения — Терминология ГОСТ 23070 78: Анализ и оптимизация на ЭВМ радиоэлектронных схем. Термины и определения оригинал документа: Многовариантный анализ 32. Анализ переходных процессов радиоэлектронной схемы Одновариантный анализ, при котором получают… …   Словарь-справочник терминов нормативно-технической документации

  • ДИФФЕРЕНЦИАЛЬНОЕ УРАВНЕНИЕ С ЧАСТНЫМИ ПРОИЗВОДНЫМИ — уравнение вида где F заданная действительная функция точки х=(xt, ..., х п )области Dевклидова пространства Е п, и действительных переменных (и(х) неизвестная функция) с неотрицательными целочисленными индексами i1 ,..., in, k=0, ..., т, по… …   Математическая энциклопедия

  • ЗВУКОВИДЕНИЕ — получение оптически видимых изображений предметов с помощью акустич. волн. В зависимости от назначения и используемого диапазона частот применяют устройства 3., основанные на след. принципах …   Физическая энциклопедия

  • ПОЛЯРИЗАЦИОННАЯ ГОЛОГРАФИЯ — метод записи, воспроизведения и преобразования состояния и степени поляризации поля когерентных эл. магн. волн. Основан на отображении поляризации суммарного поля опорного и объектного источников излучения поляризационно чувствительными… …   Физическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»