Геометрия данных 1. Симплексы и графы

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



    Введение


    Это первая статья серии, посвященной описанию свойств базисов пространств на основе элементов (а не векторов). Базис определяет систему координат — описание элементов пространства в виде набора чисел, характеризующих положение элемента относительно базиса.

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

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

    План и содержание серии


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

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

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

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

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

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

    Поехали!

    Дистанционная матрица


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

    Иногда вместо квадрата расстояния используют термин «квадранс», но поскольку он редко употребляем, то мы чаще будем употреблять более благозвучный термин «дистанция». Квадрат расстояния между элементами $A$ и $B$ будем обозначать как: $q(A,B) \equiv q_{AB}$. Если речь идет о дистанциях между элементами множества, то скаляр превращается в матрицу: $Q_{ab}$, строчные индексы обозначают множество. Кортеж дистанций от заданного элемента множества до остальных состоит из набора скалярных дистанций:

    $q_{Pa}=[q_{PA}, q_{PB},...] \quad(1.1)$

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

    Дистанции между вершинами симплекса задают дистанционную матрицу $Q$. На рисунке показан прямоугольный треугольник (2-мерный симплекс) с катетами 3, 4 и гипотенузой 5. Его матрица дистанций имеет вид:

    $\begin{array}{c | c c c} Q & A & B & C \\ \hline A & 0 & 9 & 16 \\ B & 9 & 0 & 25 \\ C & 16 & 25 & 0 \\ \end{array}$

    Для электрической цепи сопротивлений дистанция равна эффективному сопротивлению между узлами сети. А поскольку любая электросеть — это граф, то матрицу дистанций в теории графов называют матрицей резистивных расстояний (resistance distance matrix). Итак, понятие дистанции универсально — может использоваться как для привычного геометрического пространства, так и для пространства графа. Это означает также, что каждому невырожденному симплексу соответствует некий граф и наоборот.

    Окаймление матриц


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

    Однако еще в 19-м веке A.Cayley (Кэли) обнаружил, что если окаймить дистанционную матрицу кортежем из единиц, то определитель полученной матрицы будет пропорционален квадрату объема симплекса. Окаймленную единицами матрицу дистанций называют матрицей Кэли-Менгера.

    Определим операцию окаймления $Edge$ симметричных матриц $M$ кортежем $\mathbf{v}$ и скаляром $c$:

    $ Edge(M,\mathbf{v},c)=\begin{pmatrix} c&v_j\\ v_i&M\\ \end{pmatrix}\quad(1.2)$

    Если матрица $A=Edge(B,..)$ является окаймлением матрицы $B$, то $B$ является подматрицей $A$ и называется главным (угловым) минором $A$.

    Об использовании индексов
    Верхнее и/или нижнее положение индексов рядом с тензором определяет тип тензора. Если тензоры 1-го ранга различаются только положением индексов ($v_i$ и $v^j$, например), то они образуют взаимную пару.

    Согласно правилам произведения тензоров скалярное произведение (свертка, результат — скаляр) — это два одинаковых индекса на разной высоте ($a^i b_i$), точечное произведение (результат — кортеж) — одинаковые индексы на одной высоте ($a_i b_i$ или $a^i b^i$), внешнее произведение (результат — матрица, диада) — два разных индекса ($a^i b_j$ или $a_i b_j$).

    Заглавная буква в индексе измерения означает, что речь идет о фиксированном значении в данном измерении — элементе ($v_A$ — значение кортежа $v$ элемента $A$).

    Там, где природа объекта ясна из контекста, индексы в обозначении будем опускать.

    Дистанционный метрический тензор (ДМТ) — грамиан базиса


    Математики (J.C.Gower) также заметили, что удобнее оперировать не с самими дистанциями между элементами, а с отрицательными полудистанциями $-q_{AB}/2$.
    Это объясняется тем, что отрицательные полудистанции отражают скалярное произведение элементов, как следует из раскрытия формулы для квадрата расстояния (дистанции) между элементами:

    $q(A,B) = (A - B)^2 = A^2 - 2 A \cdot B + B^2$

    Отсюда получаем связь матрицы дистанций $Q$ и матрицы скалярных произведений $G$:

    $G = (\mathbf{n} \ \mathbf{1} + \mathbf{1} \ \mathbf{n} - Q)/2 \quad(1.3)$

    Здесь $\mathbf{n} = diag(G)$ — нормы элементов, диагональ матрицы скалярных произведений. В тензорной форме:

    $G_{ij} = (n_i 1_j + 1_i n_j - Q_{ij})/2$

    Не менее важна обратная формула — позволяет получать дистанционную матрицу на основе грамианов:

    $Q_{ij} = diag(G)_i 1_j + 1_i diag(G)_j - 2 G_{ij} \quad(1.3.1)$

    К множеству обычных элементов пространства добавим необычный. А именно — вектор нормали пространствa $\mathbf{z}$. Пространством нормали является ортогональное дополнение к пространству элементов. Скалярное произведение нормали с элементами обычного пространства равно единице, а с самим собой — ноль.

    $\mathbf{z} \cdot A = 1, \quad \mathbf{z} \cdot \mathbf{z} = 0 \quad(1.4)$

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

    Теперь мы готовы к определению метрического тензора. Дистанционный метрический тензор $Gm$ является набором скалярных произведений между элементами мажорного множества:

    $ Gm= Edge(G,\mathbf{1},0)=\begin{pmatrix} 0&1_j\\ 1_i&G_{ij}\\ \end{pmatrix}\quad(1.5) $

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

    Для нашего симплекса из трех вершин (прямоугольный треугольник) дистанционный метрический тензор будет иметь вид:

    $\begin{array}{c | c c c c} Gm & * & A & B & C \\ \hline * & 0 & 1 & 1 & 1 \\ A & 1 & 0 & -4.5 & -8 \\ B & 1 & -4.5 & 0 & -12.5 \\ C & 1 & -8 & -12.5 & 0 \\ \end{array}$

    Отметим, что размерность дистанционного тензора на два больше размерности обычного векторного тензора при описании пространства одной и той же мерности. То есть данный тензор содержит больше информации.

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

    $Gm_{ij} \equiv Gm $

    Геометрические свойства ДМТ


    Определитель метрического тензора $Gm$ связан с объемом симплекса $vol$. Точная формула:

    $(m! \ vol)^2=-det(Gm)\quad(1.6)$

    где $m=l-1$ — мерность пространства, задаваемого симплексом из $l$ вершин.

    Вычислим площадь нашего треугольника. Имеем $m=2, det(Gm(A,B,C))=-144$. Тогда $2 \ vol=\sqrt{144}=12$, откуда $vol=6$. Конечно, данную площадь можно было получить и просто перемножением длин катетов $vol=3 \cdot 4/2$.

    Другая полезная характеристика, содержащаяся в ДМТ, — это значение квадрата радиуса описанной сферы вокруг вершин симплекса. Данная $m$-мерная сфера играет важную роль в базисе, будем называть ее сферой базиса и обозначать как $Z$. Базисная сфера — это просто элемент пространства. Квадрат ее радиуса $rs$ — это норма данного элемента. Норма сферы базиса равна отношению определителей углового минорного и мажорного грамианов базиса:

    $rs = n(Z) = det(G)/det(Gm) \quad(1.7)$

    В нашем треугольнике норма сферы будет равна: $rs=-900/-144=6.25$.

    Лапласовский метрический тензор (ЛМТ) — лапласиан базиса


    Для метрического тензора всегда существует обратный, который называется также взаимным. Обращение дистанционного метрического тензора назовем лапласовским метрическим тензором $Lm$ — ЛМТ. Связь тензоров:

    $Lm \cdot Gm = I\quad(1.8)$, где $I$ — единичная матрица.

    Почему обратный дистанционный метрический тензор стал лапласовским? Потому что его главным угловым минором (подматрицей) является лапласиан $L$. Та самая матрица, которой описывают узлы и связи в графе, ее называют также матрицей Кирхгофа. Можно сказать, что формула (1.8) связывает свойства симплексов и графов. Каждому лапласиану соответствует грамиан и наоборот. Такая взаимность позволяет сопоставлять геометрические характеристики симплексов с параметрами графов.

    Лапласовский метрический тензор обозначаем верхними индексами: $Lm \equiv Lm^{ij}$.

    Структура ЛМТ


    Лапласовский метрический тензор — это мажорный лапласиан, окаймление обычного (минорного) лапласиана. Окаймление отражает параметры сферы базиса (1.7):

    $Lm=Edge(L,\mathbf{s},rs)=\begin{pmatrix} rs & s^j\\ s^i & L^{ij}\\ \end{pmatrix}\quad(1.9)$

    Скаляр $rs$ — это норма базисной сферы (в терминах графа — его обратная связность), $s^i = b(Z)$барицентрические координаты базисной сферы. Барицентрические координаты — это весовые координаты элемента относительно базовых (реперов) — вершин симплекса или графа. Сумма весов равна единице — условие нормировки барицентрических компонент.

    Барицентрические координаты центра описанной окружности прямоугольного треугольника всегда одинаковы
    И равны $\mathbf{s}=[s_A, s_B, s_C]=[0, 0.5, 0.5]$.

    Это означает, что центр O уравновешивается равными массами элементов B и C.

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


    Минорные тождества


    Раскрывая умножение метрических тензоров (1.8) по правилам произведения блочных матриц,

    $ \begin{pmatrix} 0 & 1_j\\1_i & G_{ij}\end{pmatrix} \cdot \begin{pmatrix} rs & s^k \\ s^j & L^{jk}\end{pmatrix} = \begin{pmatrix} 1_j s^j & 1_j L^{jk} \\ 1_i rs + G_{ij} s^j & 1_i s^k + G_{ij} L^{jk} \end{pmatrix}= \begin{pmatrix} 1 & 0^k\\ 0_i & I_{i}^{k} \end{pmatrix} \quad(1.10)$

    получаем 4-м основных тождества.
    Сумма компонент барицентрических координат центра сферы равна 1:

    $ 1_j s^j = 1 \quad(1.10.1)$

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

    $ 1_j L^{jk} = 0^k \quad(1.10.2)$:

    Свойство равноудаленности базовых вершин (симплекса или графа) от центра сферы:

    $ G_{ij} s^j = -1_i rs $

    Наконец, связь минорных грамиана и лапласиана:

    $ G_{ij} L^{jk} = I_{i}^{k} - 1_i s^k \quad(1.10.4)$

    Матрицы вида $I_{i}^{k} - 1_i s^k$, где $s$ — некий барицентрический вектор, называют матрицами трансляции. Они могут быть использованы, например, для переноса начала координат некого набора данных $X$ в точку, определяемую барицентрическими координатами $s$. Данные матрицы являются проекторами.

    Построение дистанционной матрицы по лапласиану
    Если имеем дело с графом, то для построения дистанционной матрицы на основании матрицы смежности $C$ можно использовать следующий алгоритм. Для матрицы смежности строим лапласиан:

    $L = Diag(C \cdot \mathbf{1}) - C \quad(1.11.1)$

    Здесь $Diag()$ — преобразование кортежа в диагональную матрицу.
    Определитель лапласиана равен нулю, поэтому его нельзя просто обратить. Надо либо удалить из него какой-то узел, либо дополнить (окаймить) каким-либо вектором.
    Окаймляем лапласиан вектором из единиц и обращаем полученную матрицу. Главным минором (подматрицей) результата обращения будет матрица Грина $Gr$.

    $\begin{pmatrix} 0 & 1^j\\1^i & L^{ij}\end{pmatrix}^{-1} = \begin{pmatrix} 0 & /l_j\\ /l_i & Gr_{ij}\end{pmatrix} \quad(1.11.2)$

    $l$ — количество вершин базиса.
    Матрица Грина является грамианом — матрицей скалярных произведений векторов, направленных из центра координат (здесь это центроид базиса) к элементам. Для получения дистанционной матрицы из грамиана следует использовать формулу (1.3.1).
    Пусть $Gr \equiv (A - C) \cdot (B - C)$, где $C$ — центр. Тогда формула (1.3.1) принимает следующий вид:

    $Q = (A - C)^2 + (B - C)^2 - 2 (A - C) \cdot (B - C) = (A - B)^2 $



    Геометрия лапласиана


    Сопоставим геометрические параметры симплекса с характеристиками лапласиана.

    Объем симплекса и потенциал лапласиана


    Матричная теорема о деревьях связывает количество остовных деревьев графа с определителем минора лапласиана. В предыдущих статьях данная величина именовалась скалярным потенциалом лапласиана $u$:

    $u(L)=det'(L)=-det(Lm)=-det(Gm)^{-1}=(m! \ vol)^{-2}\quad(1.12)$

    Здесь через $det'(L)$ обозначен псевдодетерминант, то есть детерминант от минора лапласиана (поскольку сам лапласиан — вырожденная матрица). $m=l-1$ — мерность пространства, на единицу меньше количества элементов базиса.

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

    Элементы лапласиана


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

    Вид лапласиана для нашего примера:

    $ L(A,B,C)={1 \over 144} \begin{pmatrix} 25&-16&-9\\ -16&16&0\\ -9&0&9\\ \end{pmatrix}$

    Здесь проводимость (вес связи) между узлами A и B равна 16/144, между узлами A и C 9/144, а между узлами B и C связи вообще нет.

    Теперь выясним геометрический смысл элементов лапласиана. Каждой вершине симплекса можно сопоставить соответствующую противоположную грань. Под противоположной понимается грань симплекса, которая не касается заданного узла. Очевидно, что в общем случае такая грань является многомерной. В нашем треугольнике — это сторона (отрезок), противоположная вершине. В тетраэдре — треугольник. Опуская из заданной вершины перпендикуляр на противоположную грань, получаем высоту вершины симплекса. Произведение высоты вершины $h_i$ на площадь противоположной грани $f_i$ дает объем симплекса $vol$, умноженного на мерность его пространства $m$:

    $h_i f_i = m \ vol \quad(1.13)$

    Элементы лапласиана симплекса можно выразить через высоты вершин. Диагональные элементы лапласиана обратно пропорциональны высотам:

    $L^{ii} = 1 / h_i^2 \quad(1.14.1)$

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

    Недиагональные элементы пропорциональны косинусу угла между гранями симплекса $cos(i,j)$:

    $L^{ij} = -cos(i,j) / (h_i h_j) \quad(1.14.2)$

    Прямой угол между гранями симплекса эквивалентен отсутствию связи между соответствующими узлами в графе.

    Из соотношений (1.12), (1.13) и (1.14.1) можно получить геометрический смысл отношения следа лапласиана $tr(L)$ к его скалярному потенциалу $tr(L)$. Эта величина связана с суммой квадратов площадей граней симплекса:

    $tr(L)/u(L) = (m-1)!^2 \sum {f_i^2} \quad(1.13.1)$

    Здесь $m-1$ — мерность грани.

    Сфера базиса и связность графа


    Норма сферы базиса $rs$ является естественной характеристикой симплекса. Соответственно данный параметр должен иметь интерпретацию в инвариантах графа.

    Величина, обратная норме сферы, называется кривизной. Кривизна базиса является подходящей характеристикой общей связности графа. Назовем данную связность сферической и обозначим традиционно как $k$. Тогда

    $k=1/rs \quad(1.15)$

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

    Значения сферической связности в различных топологиях графа
    Для полного графа (все узлы связаны со всеми) с одной и той же силой связи $c$ выражение для связности в зависимости от количества узлов $l$ имеет следующий вид:

    $k_{max}(l)=c \ l^2/(l-1) \quad(1.16.1)$

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

    Формула (1.16.1) выражает максимальное значение связности для заданного количества узлов. Минимальной является связность деревьев — графов без циклов с одной компонентой связности. К деревьям относятся, например, разомкнутая цепочка и звезда. Выражение для минимальной связности имеет вид:

    $k_{min}(l)=4c/(l-1) \quad(1.16.2)$

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

    $k_{closed}(l)=12 \ l \ c / (l^2-1) \quad(1.16.3)$

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

    Если норма сферы базиса характеризует связность графа, то барицентрические координаты сферы показывают относительную удаленность узлов графа. Величина удаленности узла обратно пропорциональна его связности. Чем менее связан с остальным графом — тем больше значение его удаленности. Поэтому барицентрические координаты центра сферы $\vec{s}$ будем также называть вектором удаленности.

    Пример значений параметров для графа


    Рассчитаем параметры популярного в Википедии графа.



    Данный граф эквивалентен 6-вершинному симплексу в 5-мерном пространстве. Кружки с цифрами — это пронумерованные узлы графа. Силу связи между узлами (значение веса ребер) принимаем за единицу.

    Сферическая связность данного графа равна 1.663 — это средняя связность на один узел. Можно сравнить ее с максимальной (7.2) и минимальной (0.8) связностью для графа из 6 узлов. Индекс симметричности — 0.773.

    Вектор удаленности узлов (барицентрический вектор центра сферы): [0.364, 0.045, 0.273, -0.227, 0.045, 0.500]. Видим, что чем больше узел имеет связей, тем меньше значение его удаленности и наоборот. Интересно отрицательное значение удаленности 4-го узла. Это единственной узел графа, при удалении которого граф распадается на две несвязанные компоненты. Возможно, что отрицательную удаленность имеют ключевые узлы графа.
    ___
    Подводим итоги. Определены взаимные метрические тензоры на элементах пространства, грамиан и лапласиан мажорного базиса. Показана связь симплексов и графов. В следующей статье покажем, как задавать координаты элементов в базисе.
    Share post

    Comments 23

      +3
      Какая-то голая теория. Как это применить на практике? Где примеры для реальных кейсов?
        +3
        «Примеры для реальных кейсов»
        В цитатник.
        +5
        Пока похоже на фричество, много умных слов, пугающих не математиков. Векторного пространства нет, сопряженного ему векторного пространства нет, а тензор — вдруг есть. Странно всё это. Посмотрим что дальше будет.
          0
          Да, не переключайтесь)
          0
          Я вот немножко математик, но меня эти слова всё равно пугают)

          Хотел ответить сюда, промахнулся.
            0
            Все мы немножко математики ). А что именно смущает?
              0
              У меня мозг выключается где-то в районе лапласовского метрического тензора. Не моя область.
                +1
                Оказывается, я с удовольствием читаю ваши статьи на Хабре ). У вас легкий и понятный слог,- не всем так дано ). Уверен, что при необходимости вы во всем сможете разобраться.
            0
            Мне не понятно: в чем тайный смысл – приводить ссылки на англоязычные страницы описания терминов при наличии русскоязычных? (ну кроме матрицы сопротивлений и определителя Кэли-Менгера)
              0
              Хороший вопрос, я над ним тоже размышлял. Всё-таки математика в английском варианте представлена гораздо полнее. Поэтому без ссылок на англо-язычные статьи все равно не обойтись. А если есть русскоязычный аналог, то всегда можно переключиться.

              0
              Если элементы имеют независимые числовые характеристики (компоненты), то дистанция между ними может быть определена как сумма разностей дистанций компонент

              Я бы заподозрил, что это толстый троллинг, но вроде здесь такое не принято. Но если это написано всерьёз, то это просто неграмотная белиберда.

                0
                Почему неграмотная-то? Грамотная белиберда. Всерьез, конечно.
                  0
                  Если всерьез, то либо квадратов разностей либо модулей разностей.
                  Только вот все это мало интересно, потому как метрика на графе у вас одна — resistance distance, о чем неплохо было бы написать.
                  Так же очень интересует случай, когда дистанция не метрика и, если такового нет, — называть вещи своими именами.
                    0
                    либо квадратов разностей либо модулей разностей.

                    Что вы пытаетесь корректно сформулировать? Теорему Пифагора? Дистанция — это квадрат разности.
                    Остальные замечания тоже пока не понял. Надо указать, какие вообще бывают метрики? Дать ссылку на монографию Дезов «Энциклопедический словарь расстояний»? По-моему, это все умничание и уход от основной темы.
                      0
                      Не стоит начинать полемику с повышенных тонов, мы с вами на брудершафт не пили. Вы местами очень небрежны с формулировками, это превращает желание разобраться в ад.
                      Поэтому, если вам не трудно, сформулируйте строгое определение дистанции, которое покрывает те примеры, которые мы видим в первом абзаце, посвещенном дистанционной матрице.
                        0
                        Я приветствую ваше желание разобраться, но не понимаю пока, в чем проблема.
                        Дистанция — это квадрат расстояния. Недостаточно строго или что? Деза использует термин «квадранс», но мне не нравится. Или непонятно само понятие расстояния?
                          0
                          Да, к сожалению, теперь придется перейти к строгому определению расстояния.
                            0
                            Кому перейти? Мне? Почему к сожалению?
                            Открываем Википедию и читаем: «Расстоя́ние, в широком смысле, степень удалённости объектов друг от друга.»
                              0
                              И как должен выглядеть квадрат «степени удаленности объектов друг от друга»?
                              В словаре, который вы рекомендовали есть определние расстояния.
                              По этому поводу больше вопросов не имею.
                                0
                                Хорошо. Надеюсь, что вопросы и замечания ещё будут. )
                  0
                  Возможно стоило написать какие требования для понимания этой статьи нужны, т.к. я ничего не понял. Ну и описать какая вообще проблема решается — зачем и почему и для кого вообще это написано? Целевая аудитория какая?

                  Хотя вижу что это уже указали.
                    0
                    Дмитрий, охрененная статья, спасибо, жаль что многовато негатива в комментах. Дмитрий, в моём нынешнем проекте граф направленный и дистанции от вершины к вершине зависят от предыдущей вершины в траектории. Это ещё не вся беда — топология моего графа (вплоть до самого множества вершин и ребёр) меняется с течением времени. Есть ли какой-то аппарат для введения изменяющейся во времени системы координат для подобных графов подобно тому, что вы описали? (желательно с упором на вероятностный подход)
                      +1
                      Спасибо за добрые слова, но критика полезна — помогает держаться в тонусе ).

                      Я не слышал про системы координат для направленных графов, но и не могу уверенно сказать, что таких нет или не может быть. Судя по описанию, вам надо окунуться в теорию марковских цепей (если еще не). Там как раз и направленные графы, и вероятностный подход. Я не специалист, поэтому могу посоветовать только полистать вот этот учебник (есть в сети на русском) — Кельберт М. Я., Сухов Ю. М., Марковские цепи как отправная точка теории случайных процессов и их приложения (2009).
                      Для более предметного обсуждения нужно больше конкретики.

                    Only users with full accounts can post comments. Log in, please.