Геометрия данных 4. Пространство графа

    Особенность координатных систем на точечном базисе (ди- и би-координат) состоит в том, что их можно использовать как в обычном геометрическом пространстве, так и в пространстве графа.



    Что такое пространство графа


    Мерность пространства и мерность базиса


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

    Точки и векторы в пространстве графа


    Необходимо разобраться, что представляют собой точки и векторы на графе. Вначале попробуем ответить на вопрос, являются ли вершины графа точками его пространства? На первый взгляд — да, потому что именно на вершинах графа определяется его базис. А точки базиса безусловно входят в пространство, ими задаваемое. Тем не менее правильный ответ — нет, не являются.

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

    Что такое точка в пространстве графа можно понять на примере электрической цепи. Лапласианом электрической цепи является матрица, состоящая из проводимостей ребер. Умножение данной матрицы на электрические потенциалы узлов дает ток в узлах. Соответственно, потенциалы в узлах $U_j$ являются дистанционными координатами, а суммарный ток узла $I^i$ — барицентрическими. Преобразование координат — это просто закон Ома:

    $L^{ij}U_j=I^i$

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

    Особые точки пространства графа


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

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

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

    Построение системы координат на графе


    Постановка задачи


    Задачу построения системы координат (СК) на графе можно сформулировать следующим образом.
    1. Задан граф как множество связанных между собой вершин.
    2. Из множества всех вершин графа выделен базис — набор вершин, для которого можно построить метрический тензор — дистанционный или лапласовский.
    3. Остальные вершины графа — внутренние. Для внутренних вершин известны:
      • Общая связность вершины (сумма весов ее связей).
      • Связи между вершинами.
      • Связи внутренних вершин с вершинами базиса.

    Требуется определить координаты внутренних вершин относительно базиса. Система координат должна позволять определять дистанции между всеми (любыми) вершинами графа.

    Уточним, что приведена лишь одна из возможных формулировок задачи построения СК. Комбинации известных параметров и тех, что требуется определить, могут варьироваться.

    Базисный подграф


    Обозначим множество базовых вершин графа индексом $a$ (anchor-якорь), а множество остальных (внутренних) вершин индексом $t$. Объединение данных множеств дает все вершины графа. Считаем узлы графа связанными с остальными хотя бы одной связью.

    Общий дистанционный метрический тензор (ДМТ) графа $Dm$ можно разбить на 4 матрицы:

    $ Dm = \begin{pmatrix} Dm_{aa} & Di_{at} \\ Di_{ta} & D2_{tt} \end{pmatrix} \quad(4.1.1) $

    $Dm_{aa}$ — дистанционный метрический тензор базиса, включает в себя окаймление вектором из единиц;

    $Di_{at}$ — матрица ди-координат вершин $t$ в базисе $a$. В данной матрице координаты вершины — это столбец матрицы, в транспонированной $Di_{ta}$ — строка. Каждая координата включает в себя скалярную компоненту — 1;

    $D2_{tt}$ — матрица (отрицательных) полудистанций между вершинами графа, не входящих в базис.

    Из перечисленных матриц известным предполагается только ДМТ базиса $Dm_{aa}$. Матрицы $Di_{at}$ и $D2_{tt}$ — это то, что надо определить на основании данных о структуре графа.

    Структура лапласиана


    Подобным же образом (на 4 подматрицы) можно разбить лапласиан графа $L$:

    $ L = \begin{pmatrix} L^{aa} & -C^{at} \\ -C^{ta} & L^{tt} \end{pmatrix} \quad(4.1.2) $

    $C^{at}=-L^{at}$ — матрица связей (смежности) между внутренними вершинами графа $t$ и его базисом $a$.

    $L^{tt}$ — минор лапласиана, связи внутренних вершин. На диагонали данной матрицы находятся значения общей проводимости узла (суммарный вес его ребер), остальные элементы — величина связи узлов между собой. Данная матрица обычно обратима. Ее обращение называется фундаментальной матрицей:

    $F_{tt}=/L^{tt} \quad(4.2)$

    Термин «фундаментальная» взят из теории марковских цепей с поглощением. В таких цепях роль базовых играют узлы, из которых нет возврата (поглощающие). Пример использования данной матрицы приводился в статье о способе ранжирования объектов по степени их удаленности от заданных.

    Предполагается, что одна из матриц (минор лапласиана $L^{tt}$ или фундаментальная матрица $F_{tt}$) известны. Согласно (4.2) можно выразить одну из другой.

    Основные тождества


    Дистанционный и лапласовский метрические тензоры взаимно обратны (см. 1.8 из первой статьи).

    $ Dm \cdot Lm = I \quad(4.3)$

    Для нахождения тождеств, связывающих между собой перечисленные выше матрицы, надо блочные матрицы (4.1.1) и (4.1.2) подставить в (4.3) (лапласиан предварительно окаймить вектором). В итоге получаем следующие соотношения.
    Связь лапласовского $Lm^{aa}$ и дистанционного $Dm_{aa}$ метрических тензоров базиса:

    $Lm^{aa} Dm_{aa} =I^{a}_{a} \quad(4.4.1)$

    (4.4.1) позволяет вычислить один тензор на основании другого. Если $Dm_{aa}$ неизвестен, то скорее всего можно найти сначала $Lm^{aa}$ на основании тождества (4.4.6).

    Для определения матрицы взаимных норм $N_{tt}$ внутренних вершин $t$ относительно базиса $a$ нужно знать би- или ди-координаты вершин (см. также вторую статью серии, 2.4):

    $N_{tt} = Di_{ta} Lm^{aa} Di_{at} = Bi_{t}^{a} Dm_{aa} Bi^{a}_{t} \quad(4.4.2)$

    Здесь $Bi^{a}_{t}=[M2_t; B^{a}_{t}]$ — би-координаты вершин. Состоят из скалярной компоненты (полустепени вершины) $M2$ и барицентрических координат $B^{a}_{t}$ (векторная часть). $Di_{ta}=[1_t; D2_{ta}]$ — ди-координаты вершин.

    Если известна матрица связей между внутренними узлами графа и его базисом $C^{at}$, а также фундаментальная матрица $F_{tt}$, то можно рассчитать барицентрические координаты узлов:

    $B^{a}_{t}=C^{at} F_{tt} \quad(4.4.3)$

    Матрицу барицентрических координат $B^{a}_{t}$ называют также матрицей влияния. Действительно, ее значения отражают влияние базовых вершин на остальные (в задаче Дирихле — влияние значений граничных узлов на внутренние).

    Би- и ди-координаты узлов взаимны. Выражаются через метрический тензор базиса:

    $Di_{at}=Dm_{aa} Bi^{a}_{t} \quad(4.4.4)$
    $Bi^{a}_{t}=Lm^{aa}Di_{at} \quad(4.4.5)$

    Следующее важное тождество связывает между собой фундаментальную матрицу, матрицу взаимных норм и полудистанции между вершинами:

    $F_{tt} + N_{tt} = D2_{tt} \quad(4.5)$

    Формула (4.5) позволяет вычислять дистанции между вершинами (точками) вне базисного пространства. С данным выражением мы уже встречались во 2-й части при определении взаимной нормы между точками, только вместо фундаментальной матрицы там использовано скалярное произведение точек относительно базиса.

    Если базис задан не в виде дистанционной матрицы, а в виде связей, то для определения лапласиана базиса $La$ пригодится следующее тождество:

    $La = L^{aa} - B^{a}_{t} C^{ta} = L^{aa} - C^{at} F_{tt} C^{ta} \quad(4.4.6)$

    Здесь $L^{aa}$ — минор исходного лапласиана на базисных вершинах. $La$ — лапласиан, подматрица ЛМТ базиса. На основании данного лапласиана можно найти ДМТ базиса $Dm_{aa}$.

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

    $ u(L) = -Det(Lm^{aa})/Det(F_{tt}) \quad(4.4.7)$

    Фундаментальная матрица и скалярное произведение относительно базиса


    Сравнивая соотношение (4.5) с выражением для взаимных норм (2.6) видим, что значения фундаментальной матрицы можно выразить через скалярное произведение вершин относительно базиса:

    $F_{ij} = D_{ii',jj'} = D_{ij,a} = D2_{ij} + D2_{i'j'} - D2_{ij'} - D2_{i'j} \quad(4.6.1)$

    Штрихами отмечены проекции вершин на базовое пространство. Через $D_{ij,a}$ обозначено скалярное произведение векторов в пространстве $a$. $D_{ii',jj'}$ — это скалярное произведение векторов $\vec{ii'}$ и $\vec{jj'}$.



    Вектор задается как направление из точки на ее проекцию в пространстве базиса. Это близко к определению скалярного произведения координат точек в обычных системах координат (на векторном базисе), только вместо одной точки начала координат здесь указывается пространство.

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

    Если точки $i$ и $j$ совпадают, то значение фундаментальной матрицы равно дистанции от точки до базового пространства или согласно (2.5) отрицательной норме точки:

    $F_{ii}=D_{ai} = -N_{i} \quad(4.6.2)$ — значения диагональных элементов фундаментальной матрицы.

    Дистанции между точками вне пространства базиса


    Если вершины не принадлежат базовому пространству (принадлежат надпространству), то возможно две ситуации:

    1. Вершины принадлежат одному и тому же (над)пространству. В этом случае вершины и их проекции на базовое пространство лежат в одной плоскости.
    2. Вершины принадлежат разным (над)пространствам (показано на рисунке выше).

    В первой ситуации направление векторов $\vec{ai}$ и $\vec{aj}$ коллинеарно, поэтому скалярное произведение совпадает с произведением расстояний от вершин до базового пространства:

    $F_{ij}= \sqrt{N_{i}N_{j}} \quad(4.6.3)$

    Знак квадратного корня положителен, если вершины находятся по одну сторону пространства (векторы направлены в одну сторону) и отрицателен в обратном случае. Данная формула уже приводилась во 2-й статье серии — (2.7). Формула (4.6.3) описывает частный (хотя и важный) случай. Общей формулой определения дистанции между точками (вершинами) вне базиса является тождество (4.5):

    $D_{ij} = -2(F_{ij} + N_{ij}) \quad(4.5')$

    Матрица степеней вершин


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

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

    $M_{t} = M_{t'} - N_{t} \quad(4.7)$

    Степень проекции точки можно вычислить через билинейную форму (2.9.2), поскольку нам известна как дистанционная матрица базиса $D2_{aa}$, так и барицентрические координаты точек (4.4.3). Значения норм точек согласно (4.6.2) можно взять из диагональных элементов фундаментальной матрицы. Собирая все вместе, получаем выражение для матрицы взаимных степеней вершин:

    $M_{tt} = B_{t}^{a} \space D2_{aa} \space B^{a}_{t} + F_{tt} \quad(4.8)$

    Диагональные значения данной матрицы $Diag(M_{tt})$ — это степени вершин. Для получения значений искомого вектора скалярных компонент би-координат вершин графа значения степеней необходимо разделить на (-2): $M2=-M/2$.

    Таким образом би-координаты внутренних вершин определены. На основании би-координат можно вычислить ди-координаты по формуле (4.4.4), получить матрицу взаимных норм (4.4.2).

    Задача построения системы координат выполнена.

    Пример построения системы координат (довольно объемный)

    Граф из 6 вершин с базисом из 3-х


    Обратимся к графу, представленному на КДПВ. На нем выделено три базовых вершины — 1, 2 и 5. Требуется определить координаты оставшихся внутренних) вершин — 3, 4 и 6.

    Вершины базиса могли быть любыми, в том числе не связанными между собой. Хороший базис — это вершины с наибольшей связностью (в нашем графе — это вершины 2, 4, 5). При таком базисе оставшиеся вершины слабо связаны между собой. Минор лапласиана и фундаментальная матрица диагональны (связей нет) и все упрощается. Но нам интересен общий случай, при котором между внутренними вершинами есть связи.

    Исходный граф — для проверки


    Лапласиан:
    \begin{array}{c | c c c с c c}
    L & 1 & 2 & 3 & 4 & 5 & 6 \\
    \hline
    1 & 2 & -1 & 0 & 0 & -1 & 0 \\
    2 & -1 & 3 & -1 & 0 & -1 & 0 \\
    3 & 0 & -1 & 2 & -1 & 0 & 0 \\
    4 & 0 & 0 & -1 & 3 & -1 & -1 \\
    5 & -1 & -1 & 0 & -1 & 3 & 0 \\
    6 & 0 & 0 & 0 & -1 & 0 & 1 \\
    \end{array}
    Соответствующая матрица дистанций:
    \begin{array}{c | c c c с c c}
    D & 1 & 2 & 3 & 4 & 5 & 6 \\
    \hline
    1 & 0 & 0.(63) & 1.(18) & 1.(18) & 0.(63) & 2.(18) \\
    2 & 0.(63) & 0 & 0.(72) & 0.(90) & 0.(54) & 1.(90) \\
    3 & 1.(18) & 0.(72) & 0 & 0.(72) & 0.909 & 1.(72) \\
    4 & 1.(18) & 0.(90) & 0.(72) & 0 & 0.(72) & 1.00 \\
    5 & 0.(63) & 0.(54) & 0.(90) & 0.(72) & 0 & 1.(72) \\
    6 & 2.(18) & 1.(90) & 1.(72) & 1.00 & 1.(72) & 0 \\
    \end{array}

    Входные данные


    Дистанционный метрический тензор базиса $Dm_{aa}$ будет иметь вид (данные взяты из общей дистанционной матрицы графа и поделены на -2):
    \begin{array}{c | c c c с}
    Dm_{aa} & 0 & 1 & 2 & 5 \\
    \hline
    0 & 0 & 1 & 1 & 1 \\
    1 & 1 & 0 & -0.3(18) & -0.3(18) \\
    2 & 1 & -0.3(18) & 0 & -0.(27) \\
    5 & 1 & -0.3(18) & -0.(27) & 0 \\
    \end{array}
    Матрица смежности (связей с базисом) $C^{at}$ в нашем примере имеет вид:
    \begin{array}{c | c c c}
    C^{at} & 3 & 4 & 6 \\
    \hline
    1 & 0 & 0 & 0 \\
    2 & 1 & 0 & 0 \\
    5 & 0 & 1 & 0 \\
    \end{array}
    Видим, что 3-я вершина связана со 2-й вершиной базиса, а 4-я с 5-й. 6-я вершина с базисом не связана.
    Минор лапласиана внутренних связей $L^{tt}$ будет таким:
    \begin{array}{c | c c c}
    L^{tt} & 3 & 4 & 6 \\
    \hline
    3 & 2 & -1 & 0 \\
    4 & -1 & 3 & -1 \\
    6 & 0 & -1 & 1 \\
    \end{array}
    Исходная триада $Dm_{aa},C^{at},L^{tt}$ — задана. На основании данных матриц можно восстановить все параметры исходного графа.

    Восстанавливаем граф


    Обращая минор лапласиана $L^{tt}$, получаем значения фундаментальной матрицы $F_{tt}$ (4.2):
    \begin{array}{c | c c c}
    F_{tt} & 3 & 4 & 6 \\
    \hline
    3 & 2/3 & 1/3 & 1/3 \\
    4 & 1/3 & 2/3 & 2/3 \\
    6 & 1/3 & 2/3 & 5/3 \\
    \end{array}
    Барицентрические координаты внутренних вершин $B^{a}_{t}$ получаем по формуле (4.4.3):
    \begin{array}{c | c c c}
    B^{a}_{t} & 3 & 4 & 6 \\
    \hline
    1 & 0 & 0 & 0 \\
    2 & 2/3 & 1/3 & 1/3 \\
    5 & 1/3 & 2/3 & 2/3 \\
    \end{array}
    Видим, что барицентрические координаты вершины 6 совпадают с барицентрическими координатами точки 4. Это характерно для всех узлов, которые соединены только с одной вершиной. Геометрически это означает, что проекции точек 6 и 4 на пространство базиса совпадают.

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

    Матрица взаимных степеней $M_{tt}$ рассчитывается на основании барицентрических координат и фундаментальной матрицы (4.8):
    \begin{array}{c | c c c}
    M_{tt} & 3 & 4 & 6 \\
    \hline
    3 & 0.(54) & 0.(18) & 0.(18) \\
    4 & 0.(18) & 0.(54) & 0.(54) \\
    6 & 0.(18) & 0.(54) & 1.(54) \\
    \end{array}
    Теперь можно построить би-координаты точек $Bi^{a}_{t}$ — скалярная компонента равна диагональным значениям матрицы степеней, деленным на (-2):
    \begin{array}{c | c c c}
    Bi^{a}_{t} & 3 & 4 & 6 \\
    \hline
    0 & -0.(27) & -0.(27) & -0.7(72) \\
    1 & 0 & 0 & 0 \\
    2 & 0.(6) & 0.(3) & 0.(3) \\
    5 & 0.(3) & 0.(6) & 0.(6) \\
    \end{array}
    Умножая матрицу би-координат на дистанционный метрический тензор (ДМТ), получаем ди-координаты $Di_{at}$ (4.4.4).
    \begin{array}{c | c c c}
    Di_{at} & 3 & 4 & 6 \\
    \hline
    0 & 1 & 1 & 1 \\
    1 & -0.5(90) & -0.5(90) & -1.(09) \\
    2 & -0.(36) & -0.(45) & -0.9(54) \\
    5 & -0.(45) & -0.(36) & -0.8(63) \\
    \end{array}
    Векторная часть ди-координат — это полудистанции от внутренних вершин до базовых. Дистанция между вершинами графа 6 и 1 согласно данной матрице должна быть равна $D_{16}=2 \cdot 1.(09) = 2.(18)$. Посмотрев на общую дистанционную матрицу, можно убедиться, что так и есть.

    Матрица взаимных норм $N_{tt}$ — это произведение взаимных координат вершин (4.4.2):
    \begin{array}{c | c c c}
    N_{tt} & 3 & 4 & 6 \\
    \hline
    3 & -0.(6) & -0.(69) & -1.1(96) \\
    4 & -0.(69) & -0.(6) & -1.1(6) \\
    6 & -1.1(96) & -1.1(6) & -1.(6) \\
    \end{array}
    Согласно данной матрице все внутренние вершины графа лежат вне базового пространства (нормы ненулевые). Осталось определить дистанции между внутренними вершинами $D_{tt}$. Используем (4.5'):
    \begin{array}{c | c c c}
    D_{tt} & 3 & 4 & 6 \\
    \hline
    3 & 0 & 0.(72) & 1.(72) \\
    4 & 0.(72) & 0 & 1.0 \\
    6 & 1.(72) & 1.0 & 0 \\
    \end{array}
    Сравниваем с исходной дистанционной матрицей $D$ и убеждаемся, что все значения совпадают.

    Маловершинные базисы


    Если базис содержит небольшое количество вершин, то часть формул обращения (4.4) может быть выражена в явном виде. Здесь рассмотрим базисы из одной и двух вершин.

    Базис из одной вершины


    Достаточно тривиален и поэтому не очень интересен. Дистанционный метрический тензор базиса не включает ни одной дистанции:

    $ Dm = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} $

    Все барицентрические координаты вершин относительно базиса равны 1 (поскольку всего одна компонента). Фундаментальная матрица совпадает с матрицей скалярных произведений векторов, где началом каждого вектора является как раз вершина базиса. В 3-й части было показано, что дистанционную матрицу на основании такой матрицы можно получить через преобразование дистанции:

    $D_{ij}=Dist(F_{ij}) = F_{ii} + F_{jj} - 2F_{ij}$

    Базис из двух вершин


    Такой базис имеет прикладное значение. Например, в рассмотренной нами ранее задаче электрометрии узлы, к которым прикладывается внешнее напряжение, — это и есть 2-вершинный базис.

    Обозначим дистанцию между базовыми вершинами $A$ и $B$ как $r=d_{AB}$. Напомним, что в электрической цепи дистанция эквивалентна сопротивлению между узлами. Тогда дистанционный метрический тензор базиса имеет вид:

    $ Dm = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & -r/2 \\ 1 & -r/2 & 0 \end{pmatrix} \quad(4.9)$

    Детерминант ДМТ: $Det(Dm)=-r$. Лапласовский тензор (ЛМТ) получаем обращением дистанционного (4.4.1):

    $ Lm = \begin{pmatrix} r/4 & 0.5 & 0.5 \\ 0.5 & /r & -/r \\ 0.5 & -/r & /r \end{pmatrix} \quad(4.10)$

    Ди-координаты вершин графа будут иметь три компоненты: скалярная (1), полудистанции $d2_A$ относительно базовой вершины $A$ и полудистанции $d2_B$ относительно базовой вершины $B$:

    $Di=[1; D2]=[1; d2_A, d2_B] \quad(4.11.1)$

    Би-координаты также имеют три компоненты. Скалярная компонента — это (геометрическая) полустепень вершины.

    $Bi=[m2; B]=[m2; b_A, b_B] \quad(4.11.2)$

    Подставляя (4.11.1) в (4.4.5) и учитывая (3.8), получаем выражения для компонент би-координат вершины P:

    $Bi_P=[-D^P_{AB}/2; D^B_{AP}/r, D^A_{BP}/r] \quad(4.12)$

    Здесь через $D^Z_{XY}=D_{ZX,ZY}$ обозначено скалярное произведение векторов, начало которых находится в вершине $Z$, а концы — в точках $X$ и $Y$.

    $D^Z_{XY}=d2_{XY} - d2_{XZ} - d2_{YZ} \quad(4.13) $

    Можно убедиться, что сумма барицентрических компонент равна 1, как и должно быть: $b_A+b_B=1$.

    Разность потенциалов графа при 2-вершинном базисе


    Барицентрическая часть координат в (4.12) представляет собой матрицу влияния — передает влияние базовых вершин на внутренние. Если, например, на базовых вершинах заданы значения потенциалов $U_a$, то потенциалы внутренних вершин $U_t$ определяются произведением заданных потенциалов на матрицу влияния:

    $U_P = B^{a}_{P} U_a \quad(4.14) $

    Пусть вектор внешних потенциалов имеет вид $U_a=[U_A, 0]$. Тогда разность потенциалов между точками P и Q графа будет равна:

    $U_P - U_Q = (B_{PA} - B_{QA}) U_A = D_{AB,PQ} U_A /r = D_{AB,PQ} J \quad(4.15) $

    При выводе использовано тождество (3.11.4) для разности скалярных произведений на 3-х вершинах. $J$ — это величина входящего потока, определяется уравнением $La U_a = J$.

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



    Подводим итоги. В данной части показано, как задать на дискретном графе систему координат. Приведены основные тождества, ключевым из которых на наш взгляд является (4.5). Приведенные соотношения справедливы, конечно, и для обычного пространства.
    Из обязательной программы осталось рассмотреть преобразование координат (смену базиса), чем и займемся в следующей статье.
    • +10
    • 4,5k
    • 5
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 5
    • 0
      Простите, что опять пристаю, где можно посмотреть определение мерности пространства? Определение размерности векторного пространства мне известно. С вашим, как обычно, сложности.
      • 0
        Промахнулся с комментом. См. ниже.
      • 0
        Приставайте на здоровье ).
        Но я хочу уточнить, про мерность какого «вашего» пространства вопрос?
        Мерность пространства не зависит же от системы координат или как? Или вы что под векторным пространством понимаете?
        Или вопрос про определение размерности пространства графа? Уточните, пжста.
        • 0
          Есть понятие — размерность векторного пространства.
          У вас понятие — мерность пространства графа. Вот я и спрашиваю — что это такое.
          • 0
            Да, теперь понятнее, спасибо.
            Думаю, что мерность пространства графа определяется рангом его лапласиана — количеством линейно независимых строк/столбцов.

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