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

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



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


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


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

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


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

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

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

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

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

    Если граф представляет собой электрическую цепь, то точкой является совокупность потенциалов на узлах сети. Лапласианом электрической цепи является матрица, состоящая из проводимостей ребер. Умножение данной матрицы на электрические потенциалы узлов дает ток в узлах. Соответственно, потенциалы в узлах $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} = N_{ii',jj'} = N_{ij,a} = D2_{ij} + D2_{i'j'} - D2_{ij'} - D2_{i'j} \quad(4.6.1)$

    Штрихами отмечены проекции вершин на базовое пространство. $N_{ii',jj'}$ — это скалярное произведение пар $(i,i')$ и $(j,j')$.
    Через $N_{ij,a}$ обозначено скалярное произведение нормалей вершин $i, j$ к пространству $a$.



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

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

    Если точки $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=[-N^P_{AB}/2; N^B_{AP}/r, N^A_{BP}/r] \quad(4.12)$

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

    $N^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 = N_{AB,PQ} U_A /r = N_{AB,PQ} J \quad(4.15) $

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

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



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

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

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

        Самое читаемое