dmagin (dmagin) wrote,
dmagin
dmagin

Category:

Эффективные сопротивления графа - что, как и почему

Это итоговый пост о свойствах потоков и потенциалов в симметричных графах. Даже более конкретно - о матрице эффективных сопротивлений (резистивных расстояний, резистенсов) R.
Сведем кратко и воедино все, что смогли уяснить, и закроем тему.

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

Поскольку в основе методики - обычная математика (а не физика), то результаты можно применять к любой области, в которой можно выделить множество объектов (вершины графа), связанных между собой симметричным образом (матрица смежности C, для электрической сети - матрица проводимости).

Тезисно.
1) Для симметричного графа можно определить матрицу эффективных сопротивлений R. Она же - матрица резистивных расстояний.
* Электрический смысл элемента Rij - общее (эффективное) сопротивление между точками i и j.
* Броуновский смысл - среднее время достижимости узла j при старте из узла i и случайном (вероятностном) блуждании.
То есть, чем дольше электроны идут из узла i в узел j - тем больше эфф. сопротивление между этими узлами.

2) Матрица R имеет свойства метрики (выполняется неравенство треугольника - сумма двух сторон всегда больше третьей).
Вполне возможно, что реально наше пространство определяется как раз матрицей R. Поскольку, как известно из квантовой механики, при наличии многих возможных путей из точки i в точку j частицы (фотоны, электроны и т.п.) идут сразу по всем путям одновременно. А длина такого "общего пути" как раз описывается элементом матрицы Rij.

3) Важно, что во многих ситуациях матрица эффективных сопротивлений может быть измерена. То есть нам дана в ощущениях именно матрица R (а не C). Поскольку, как правило, мы не можем вычленить непосредственно влияние только одного ребра графа Cij, не разрушая систему (хм, вот и неразрушающий контроль всплыл - моя институтская специальность). Влияют все связи - то есть измеряем эффективные (средние) связи.

4) Не менее важно, что на основании полной матрицы R можно восстановить матрицу локальных проводимостей C. Понятно, что такая возможность должна быть, поскольку по информационной емкости матрицы R и C совпадают. Но все равно удивительно, что существуют относительно простые алгоритмы прямого и обратного преобразования.

Все вышесказанное в той или иной степени ясности уже приводилось в данном журнале. Теперь новое.

5) Узлов в практически интересных графах может быть много. Например, если проводить электроизмерения сеткой 30 x 30, то получаем 900 узлов. Для графа из 900 узлов количество возможных связей (полный граф) составляет N(N-1)/2 = 404550 значений. Это внушительная цифра. Слишком много неинтересных данных.
В то же время для восстановления матрицы проводимостей нужны как будто бы все данные.

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

6) Оказывается, что существует способ обработки данных матрицы R при ее неполном заполнении.
Преобразование (R -> C) выполняется через промежуточную матрицу Грина G. Матрица Грина является псевдообратной по отношению к матрице Кирхгофа - то есть по ее значениям можно построить матрицу Кирхгофа и далее - матрицу проводимостей.
Кроме того, так же как матрица Кирхгофа является лапласианом от матрицы проводимостей, так и матрица Грина является лапласианом от некой матрицы. Обозначим эту матрицу как S и назовем ее матрицей контрастности сопротивлений (почему - будет ясно из нижеследующего).

7) Элементы матрицы контрастности S могут быть получены на основе элементов и агрегатов матрицы R:

Sij = (Rij + R_ave - Ri_ave - Rj_ave)/2

Суть - в использовании агрегатов (усредненных значений) матрицы Rij.

Ri_ave = Сумма_i(Rij)/N, R_ave = Сумма(Rij)/N^2

Элемент матрицы контрастности отражает отклонение эфф. сопротивления (резистенса) между узлами i и j от среднего сопротивления узлов i и j.

8) Таким образом, для получения (оценки) матрицы контрастности мы можем использовать только часть элементов матрицы R - получить примерную оценку. Нет необходимости измерения всех возможных значений матрицы R - можно выбрать только часть (заданной конфигурации) и на их основе вычислять средние значения резистенсов узлов.

9) Для электрометрии нет особой необходимости в построении матрицы проводимости C - матрица S ей обратно подобна.
Построив матрицу контрастности, можно получать срезы контрастности на различные глубины (суммировать Sij заданного радиуса - расстояния от узла).
Удобство состоит еще и в том, что мы можем перейти непосредственно к удельным сопротивлениям - это облегчит сравнение срезов по глубине.

На этом завершаем цикл заметок, посвященных электрометрии.
Мы замкнули процесс многоэлектродной электрометрии - от способа измерений (измерять надо эфф. сопротивления (резистенсы), показали - как это можно сделать, какие данные нужны) - до способа обработки (вывели алгоритмы - как правильно обрабатывать данные матрицы эффективных сопротивлений для последующей визуализации).
Tags: Графы, Электрометрия
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments