Случайные блуждания: связь с резистивным расстоянием (часть 1) / forpes.ru

22.07.2024 09:16

HoboDaVS 0 217 Источник

Предисловие

Эта первая статья из цикла работ, посвящённых связи сопротивления и случайных блужданий.
Сперва мы пройдёмся по теоретическим аспектам изучаемых предметов, далее напишем скрипты для расчётов и проведём анализ полученных результатов.

Введение

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

С введением графовой интерпретации можно задать метрику для нахождения расстояния между двумя произвольными вершинами графа – резистивное расстояние[1]. Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя узлами электрической цепи, построенной путем замены сопротивления всех связей сети на сопротивление в 1 Ом. В таком случае вес каждого ребра будет равен единице. В то же время, для электрической цепи применим первый закон Кирхгофа :

"Алгебраическая сумма токов в узле электрической цепи равна нулю"

Связь между Законами Кирхгофа и резистивным расстоянием начали исследовать Douglas J. Klein и M. Randic [2] несколько десятилетий назад.

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

Главной целью является нахождение резистивного расстояния между двумя произвольными вершинами графа. Это расстояние эквивалентно сопротивлению между соответствующими узлами в электрической цепи. Модель позволяет использовать математические методы теории графов для анализа электрических цепей, что упрощает вычисления и интерпретацию результатов.

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

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

Теоретические аспекты электрических сетей

Стоит отметить, что существует два вида закона Ома: линейный и нелинейный.

Линейный закон Ома утверждает, что ток через проводник прямо пропорционален напряжению, приложенному к нему, при условии, что температура и другие физические условия остаются постоянными. Это выражается формулой:

$I=\frac{U}{R}$

где - ток (в амперах, А), - напряжение (в вольтах, В), - сопротивление (в омах, Ом).

Нелинейный закон Ома описывает материалы и устройства, у которых нет прямой зависимости тока от напряжения. В таких случаях ток может изменяться при изменении напряжения или сопротивления нелинейно. Формула нелинейного закона Ома часто значительно сложнее, чем линейный закон, и зависит от специфики материала или компонента. Для описания таких зависимостей обычно применяют эмпирические формулы. В статье рассматривается только линейный закон Ома.

Физические определения

Ток от вершины до графа определяется как функция на парах смежных вершин такая, что:

$i_{xy} = - i_{yx}$

Ток $i_{xy}$ определяется уравнением:

$\sum_y^{\sim x} i_{xy} = I\cdot \delta_{xa} - I\cdot \delta_{xb}, \ \forall x \in V(G)$

где сумма берется по всем $y\in V(G)$ , смежным с вершиной ; $\delta_{xy}$ - символ Кронекера..

Эта формула описывает сумму токов, входящих в вершину . Величина $I\delta_{xa}$ равна , если x=a (источник), и 0 - в противном случае. Аналогично, $I\delta_{xb}$ равно , если x=b (сток), и 0 - в противном случае. Таким образом, представляет собой величину чистого тока, входящего из источника и выходящего в сток . Это уравнение известно как закон Кирхгофа для тока (в случае одного источника и одного стока).

Ток называют физическим [2], если существует потенциал на вершинах графа такая, что:

$i_{xy}\cdot r_{xy} = v_x - v_y, \ \forall x,y \in E(G)$

где $r_{xy} \equiv r_{e}$ , при $e=\{x,y\}$ ; v_x - потенциал на узле , v_y - потенциал на узле $y$ .

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

$\sum_{x\sim y}^C i_{xy}r_{xy} = 0, \ \forall C$

где сумма берется по всем ребрам контура в графе , а ток из упорядоченной последовательности токов контура .

Нормированное пространство

В соответствии с графом можно определить нормированное пространство с ортонормированным базисом, элементы которого сопоставлены с вершинами графа .
Такой базисный вектор определяется как $|x\rangle, x \in V(G)$ . В этом пространстве представлены несколько матриц (линейных операторов).

Матрицей инцидентности называется матрица, элементы которой задаются следующим образом:

$A_{xy} = \langle x|A|y\rangle = \begin{cases} 1/r_{xy}, & x \sim y\\ 0, & otherwise \end{cases} \ x,y \in V(G)$

где в нотации Дирака: $|x\rangle$ - вектор, в котором элемент с номером равен 1, а остальные 0; $|y\rangle$ - вектор, в котором элемент с номером y равен 1, а остальные 0; - матрица инцидентности графа .

При установлении единичных сопротивлений в цепи, матрица сводится к матрице смежности графа .

Матрица $\Delta$ , элементы которой задаются следующим образом:

$\Delta_{xy} = \langle x|\Delta|y\rangle=\delta_{xy}\sum_z^{\sim x}1/r_{xz},$

где суммирование происходит по вершинам $z\in V(G)$ , которые смежны с , называется матрицей степеней вершин.

Далее большую роль сыграет матрица под названием Лапласиан, которая задаётся через разность $\Delta - A$ .
Она крайне удобна для следующей леммы:

Лемма о собственных значениях

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

$|\phi\rangle \equiv \sum_x |x\rangle,$

Для уменьшения размера статьи доказательство опускается. Оно представлено в [2] см. 86 стр.

Следствие леммы

По условиям леммы, Лапласиан имеет как минимум одно собственное значение равное нулю. Следовательно, он не является обратимым в привычном смысле. Однако в подпространстве, ортогональном к $|\phi\rangle$ , он действительно имеет обратную матрицу, которая задаётся следующим образом :

$(\Delta - A)^+ = ((\Delta - A)^T(\Delta - A))^{-1}(\Delta - A)^T$

Резистивное расстояние

Лемма о токе

Физический ток в графе из вершины в вершину в связном графе существует, является единственным и определяется следующим образом:

$i_{xy} = \frac{I}{r_{xy}}\langle x -y| (\Delta - A)^+| a-b\rangle,$

где $|a-b\rangle \equiv |a\rangle - |b\rangle$ .

Доказательство

Для доказательства, подставим определение тока в определение потенциала и получим:

$\sum_y^{\sim x}\frac{1}{r_{xy}} \{v_x - v_y\} = I\delta_{xa} - I\delta_{xb}$

Используя определения матрицы смежности и матрицы степеней вершин, получим:

где $\langle x | a -b \rangle$ в нотации Дирака является скалярным произведением векторов.

Теперь $\forall x \in V(G)$ , это можно переписать как:

$(\Delta - A)\sum_x v_x|x\rangle = I\langle x | a - b\rangle.$

Тогда, согласно лемме о собственных значениях, формулу можно переписать как:

$\sum_x v_x|x\rangle = I(\Delta - A)^+ |a-b\rangle$

Это непосредственно приводит к формуле нашей теоремы, тем самым устанавливая уникальность этих различий. Для нахождения разности потенциалов между парой вершин ?, ? нужно из элемента вектора $\sum _x v_x |x\rangle$ с номером вычесть элемент с номером , что дает нам:

$v_x - v_y = I\langle x -y|(\Delta - A)^+ |a-b\rangle$

Тогда, закон Ома дает формулу леммы, единственность и его существование. Что и требовалось доказать.

Разность потенциалов между двумя точками, как видно из Закона Ома, прямо пропорциональна . При выборе x=a и y=b , этот коэффициент пропорциональности называется эффективным сопротивлением $\Omega_{ab}$ между и . Таким образом, мы получаем основной результат этого раздела:

Теорема о резистивном расстоянии

Для физического тока из в в графе резистивное расстояние $\Omega_{ab}$ равно:

$\Omega_{ab} = \langle a-b|(\Delta - A)^+| a -b\rangle$

Теорема об эквивалентности сопротивления и расстояния

Формально определим эффективное сопротивления как расстояние.
Под расстоянием на графе мы понимаем отображение $\rho$ из декартова произведения $V(G)\times V(G)$ в вещественные числа, удовлетворяющее следующим аксиомам:

$\rho(a,b) \ge 0,\\ \rho(a,b) =0 \Leftrightarrow a =b,\\ \rho(a,b) = \rho(b,a),\\ \rho(a,x) = \rho(x,b) \ge \rho(a,b)$

Доказательство приведено в [2] см. 89 стр.

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