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

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

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

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

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

Определение системы координат

Задачу построения системы координат (СК) на графе можно сформулировать следующим образом.

  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}$ — матрица связей (смежности) между внутренними вершинами графа $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^{a}_{t}; B^{a}_{t}]$ — би-координаты вершин. Состоят из скалярной компоненты (полустепени вершины) $M2^{a}_{t}$ и барицентрических координат $B^{a}_{t}$ (векторная часть). $Di_{ta}=[1; 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) позволяет вычислять дистанции между вершинами (точками) вне базисного пространства.

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

$ La=L^{aa} - C^{ta} B^{a}_{t}=L^{aa} - C^{ta}F_{tt}C^{at} 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), можно выразить значения фундаментальной матрицы через скалярное произведение векторов. Значения матрицы взаимных норм $N_{tt}$ даются выражением (2.7). Подставляя его в (4.5) получаем выражение элемента фундаментальной матрицы $F_{ij}$ через полудистанции:

$F_{ij}=D2_{ij} - D2_{i'j'} - D2_{i'i} - D2_{jj'}=D2_{ij} + D2_{i'j'} - D2_{ij'} - D2_{i'j} quad(4.6.1)$

Штрихами отмечены проекции вершин на базовое пространство. Формула (4.6.1) представляет собой скалярное произведение векторов $vec{i'i}$ и $vec{j'j}$. С учетом определений (3.8), (3.10) из предыдущей статьи получаем:

$F_{ij}=D_{i'i,i'j}=D_{j'i,j'j}=D_{ii',jj'}=D_{ij,a} quad(4.6.2)$
Геометрия данных 4. Пространство графа - 57

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

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

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

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

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

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

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

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

Знак квадратного корня положителен, если вершины находятся по одну сторону пространства (векторы направлены в одну сторону) и отрицателен в обратном случае. Данная «магическая» формула была приведена во 2-й статье серии — (2.6). Видим, что особой магии нет, формула (2.6) описывает частный (хотя и важный) случай. Общей формулой определения дистанции между точками (вершинами) вне базиса является тождество (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.3) можно взять из диагональных элементов фундаментальной матрицы. Собирая все вместе, получаем выражение для матрицы взаимных степеней вершин:

$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). Приведенные соотношения справедливы, конечно, и для обычного пространства.

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

Автор: dmagin

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js