16.04.2019 09:21
dmagin 7 2600 Источник
«До того, как вы постигнете это, оно кажется чудом. Но после в нем нет ничего особенного.»

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



1. Постановка задачи. Я живу на одном, ну а ты на другом.


Небольшой городок разделен (например, рекой, хотя в контексте вершин более подходит ущелье) на два района (части) $A$ и $B$. Сообщение между районами осуществляется по единственной дороге (мосту), имеющей две полосы: в сторону от $A$ к $B$ и обратно. В связи с ростом населения встал вопрос об увеличении пропускной способности дороги. Денег как обычно в обрез и хватает только на одну полосу в одном направлении. Понятно, что даже одна полоса сблизит районы, но вот вопрос — насколько именно? Вы — городской сумасшедший математик, и именно вас пригласили для того, чтобы получить обоснованный ответ.
Насколько будут ближе районы, если построить еще одну полосу в одном направлении?

Формулировка для продвинутых


Вместо кёнигсбергских мостов можно использовать чуть более строгий язык теории графов. Итак, есть направленный граф с двумя вершинами (узлами) $A$ и $B$. Величина связи (проводимость, пропускная способность) в прямом и обратном направлении изначально равны. Вопрос — насколько изменится расстояние между узлами, если проводимость в одном из направлений увеличить вдвое?

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

Ответ для тех, кто торопится
Да, я собирался дать здесь быстрый ответ, но передумал. Зачем лишать читателя удовольствия от самостоятельных размышлений? Возможно, вы предложите что-то более путное, чем автор. В любом случае можно сразу пролистать в конец статьи. Сорри ).

Мера близости и пьяные блуждания


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

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

Резистивное расстояние эквивалентно понятию эффективного сопротивления, если речь идет об электрической сети. Поэтому на электрическом языке задачу можно сформулировать так. Между двумя узлами встречно включены два диода равных проводимостей. Как изменится сопротивление между данными точками, если добавить еще один диод? (Извиняюсь, если электрический язык подвел и я ерунду тут написал).

Также эффективное сопротивление можно трактовать на марковском языке вероятностей пьяных случайных блужданий (желающим углубиться в тему — гуглить «Random walks and electric networks»).

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

Вообще, термин «резистивное расстояние» тоже не выглядит удачным. Он подразумевает, что речь идет о каком-то необычном неизвестном науке расстоянии. На самом деле резистивное расстояние — это обычное евклидово расстояние. Но в аффинном пространстве. Мы используем эту его особенность далее.

А в чем, собственно, проблема?


Если мы знаем, что такое «резистивное расстояние», то почему не можем его «просто взять и посчитать» для заданного графа?

Хм. В принципе легко. Если речь о ненаправленном графе. Если бы город построил полосы в обоих направлениях, то резистивное расстояние уменьшилось бы ровно вдвое. Поскольку сопротивление обратно пропорционально проводимости, а проводимость (пропускная способность) увеличилась в два раза. А если бы добавил по две полосы в каждом направлении, то расстояние уменьшилось бы в 3 раза. Тут все достаточно тривиально. (И наверное, кто-то здесь уже может догадаться об общем виде решения. А мы едем дальше).

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

(Это мой тезис — возможно, кто-то сможет переубедить меня). «Нет» — тут означает, что его нет в учебниках, вики, и в головах (точнее — есть много разных способов от разных авторов, которые требуют разных допущений и определений). Сам-то способ есть (хотя и не такой уж простой). В данной статье мы как раз его и описываем.

Само определение расстояния при наличии направленных связей требует уточнения, если речь идет о направленном графе (некоммутативной метрике, извиняюсь). Можно говорить о расстоянии от $A$ до $B$, а можно от $B$ до $A$. И скорее всего данные расстояния не всегда равны. Про какие именно расстояния идет речь в задаче?

Евклидово расстояние рулит


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

$ S(A, B) = |A - B|^2 = (A - B)^2 = (A - B) \cdot (A - B) = S(B, A) \quad(1) $

Данное определение не зависит от порядка элементов — это коммутативное расстояние, близость (точнее дальность) элементов. Точка в выражении означает операцию скалярного произведения (пространство метрическое). Соответственно, выражение (1) можно раскрыть:

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

Здесь $A^2 = A \cdot A$, $B^2 = B \cdot B$ — нормы элементов. Когда речь идет за графы, то нормы элементов как правило равны нулю. В исходной задаче про нормы ничего не сказано, поэтому можно принять их нулевыми (подробнее про то, что означают нормы элементов в аффинном пространстве есть тут. А если еще более подробно, то тут). Тогда выражение для искомого расстояния принимает вид:

$ S(A, B) = - (A \cdot B + B \cdot A) = s_{AB} + s_{BA} \quad(3) $

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

Попутно формула (3) показывает, что наша общая (коммутативная) мера близости между элементами $A$ и $B$ является суммой двух направленных расстояний:

$s_{AB} = - A \cdot B$ — направленное расстояние от $A$ до $B$,
$s_{BA} = - B \cdot A$ — направленное расстояние от $B$ до $A$.

2. Решение. Долгая дорога в дюнах


Гул затих. Веселье кончилось. Дальше идут унылые подробности описания сути метода расчета скалярного произведения между узлами направленного графа. Это та часть, которую я не знаю, как рассказать «по-простому на пальцах». Но именно здесь самое важное в статье. То, ради чего стоило тратить на нее время.

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

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

Аффинное метрическое пространство (ненаправленный граф)


Что важно. Сначала общеизвестное.

1. Аффинность пространства означает, что понятия вектор и элемент в пространстве отличаются. Вектор — это разность элементов. Это казалось бы несущественная особенность, приводит к существенным последствиям, если в пространстве определена метрика.

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

3. Характеристикой связности графа является матрица смежности. Но для метрических (и прочих) свойств более важен лапласиан графа (матрица Кирхгофа) $L$.

4. Лапласиан графа — это почти метрический тензор. «Почти» — тут означает, что он неполон. Лапласиан является вырожденной матрицей и потому не обратим. А стандартный метрический тензор вполне себе обратим.

Теперь менее известное.

5. Различие между элементами и векторами в метрическом аффинном пространстве приводит к существованию в нем нуль-вектора $\mathbb z$. Скалярное произведение элементов с нуль-вектором в коммутативном (симметричном) пространстве равно единице (в некоммутативном зависит от направления умножения). Без нуль-вектора пространство графа не является полным! Это важно.

6. Дуальным по отношению к нуль-вектору является ортогональный центр базиса $Z$. Это такой элемент, который ортогонален всем остальным элементам базиса (кроме нуль-вектора). Напомним, что ортогональность элементов означает, что их скалярное произведение равно нулю. Ортоцентром треугольника является описанная окружность. Да, в полном аффинном пространстве элемент с ненулевой нормой — это не точка, а n-мерная сфера.

7. Лапласиан графа в совокупности с координатами ортогонального центра становится полным (полноценным метрическим тензором). Другими словами полный лапласиан $Lm$ — это обычный лапласиан графа $L$, но окаймленный барицентрическими координатами ортогонального центра.

8. Обращение полного лапласиана позволяет получить полный грамиан $Gm$ — матрицу скалярных произведений элементов базиса (в нашем случае — вершин графа). Данный грамиан также является полноценным метрическим тензором пространства.

9. Окаймлением полного грамиана является кортеж из единиц (скалярные произведения элементов базиса и нуль-вектора). В углу — ноль, это норма самого нуль-вектора.
Известная матрица Кэли-Менгера — это почти правильный грамиан.

В итоге приходим к тому, что согласно п.8 задача определения скалярных произведений (а, значит, и расстояний) между узлами графа сводится к определению исходного метрического тензора базиса $Gm$.
Нужен метод построения полного грамиана графа $Gm$ по заданному (неполному) лапласиану $L$.

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

$\mathbb z \cdot A = A \cdot \mathbb z = 1 $

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

Некоммутативное аффинное пространство (направленный граф)


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

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

$ A \cdot B \ne B \cdot A $

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

$\mathbb z \cdot A \ne A \cdot \mathbb z $

Однако известных величин тоже много.

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

Осталось подставить все известные и неизвестные в тождество, связывающее лапласиан и грамиан:

$ Lm \ Gm = I $

Здесь $I$ — это тождественная матрица. В этом тождестве смысл перехода от неполного лапласиана к полному.

Заткнулись и считаем


Перейдем от слов к делу. Вот как выглядит лапласиан $L$ для графа из двух узлов:

$ L = \begin{bmatrix} c_1 & -c_1 \\ c_2 & -c_2 \end{bmatrix} $

Для простоты мы обозначили связи цифрами: $c_1 = c_{AB}, c_2 = c_{BA}$. Предполагается, что значения связей известны — через них мы будем выражать все остальные величины.

Полный лапласиан $Lm$ включает в себя координаты ортоцентра $[rz, az, bz]$:

$ Lm = \begin{bmatrix} rz & az & bz \\ az & c_1 & -c_1 \\ bz & c_2 & -c_2 \end{bmatrix} $

Здесь $rz$ — норма ортоцентра (в симметричном случае интерпретируется как квадрат радиуса), $az$ и $bz$ — коэффициенты разложения ортоцентра по базису $A, B$ (барицентрические веса).

Полный грамиан $Gm$ выглядит примерно так:

$ Gm = \begin{bmatrix} 0 & za & zb \\ 1 & 0 & g_1 \\ 1 & g_2 & 0 \end{bmatrix} $

Здесь кортежи $[za, zb]$ и $[1, 1]$ отражают дуальные координаты нуль-вектора. Данные координаты являются аннуляторами лапласиана (при умножении на лапласиан дают нулевой вектор — не путать с нуль-вектором!).

Для решения задачи нам надо найти сумму значений грамиана: $-(g_1 + g_2)$.

Считаем количество неизвестных: $rz, az, bz, za, zb, g_1, g_2$ — всего 7 (да-да, — чтобы выяснить значение одного несчастного расстояния, нам надо рассчитать еще семь дополнительных величин). На входе есть две известных связи — $c_1 $ и $c_2$. Тождество $Lm \ Gm = I$ даст 9 уравнений. Итого 7+2 = 9, — все сходится (удивительно). Осталось просто решить систему уравнений.

Для графа из двух узлов решение (все неизвестные) можно выразить в явном виде. Приведем конечные выражения для интересующих нас величин. Введем понятие общей геометрической связности — это величина, обратная норме ортогонального центра $gc = 1/rz$. Ее размерность совпадает с размерностью связей графа. Для графа из двух узлов (и двух связей) геометрическая связность имеет симпатичное выражение:

$gc = 1/rz = (\sqrt{c_1} + \sqrt{c_2})^2$

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

$ g_1 = -gc \sqrt{c_2}, \quad g_2 = -gc \sqrt{c_1} $

Можно перевести скалярные произведения $g$ в направленные расстояния $s$ (3):

$ s_{BA} = gc \sqrt{c_{AB}}; \quad s_{BA} = gc \sqrt{c_{AB}}$

Искомое коммутативное расстояние между узлами определяется суммой:

$ S(A,B) = s_{BA} + s_{AB} = 1/ \sqrt{c_{AB} c_{BA}} \quad (4) $

Бабушка приехала


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

Можно нагрузить школьный учебник еще одной бесполезной формулой.

Если связи равны, то результат совпадает с резистивным расстоянием в ненаправленных графах:

$ S_{c, c}(A,B) = 1/c \quad (4.1) $

Посчитаем, что там с нашим городком. Если проложить вторую полосу, то связь в одном направлении увеличится в два раза. Соответственно, новое расстояние $S_{1, 2}(A,B)$ можно выразить в терминах исходного:

$ S_{1, 2}(A,B) = 1/ \sqrt{2 c_{AB} c_{BA}} = 1/\sqrt{2} S_{1, 1}(A,B) $

Расстояние между районами уменьшится в $\sqrt{2}$ раз. Это же было очевидно, да?

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



На этом все. Спасибо за внимательность ).

Приложение. Явные выражения для остальных элементов матриц нашего графа
Координаты ортоцентра:
$az = \sqrt{c_1 gc}, \quad bz \sqrt{c_2 gc} $

Скалярные произведения базиса и нуль-вектора (аннулятор лапласиана):
$za = \sqrt{c_2 /c_1} \quad zb = \sqrt{c_1 /c_2} $

Комментарии (7)


  1. koropovskiy
    16.04.2019 14:15
    #20033130
    +2

    Простите, если совсем не в тему напишу.

    Понятно, что даже одна полоса сблизит районы

    Почему это подается аксиомой? Что является признаком близости?

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

    Мне из этого видится вывод, что Евклидовая близость никак не ответит на вопросы «как изменится пропускная способность между районами», «несет ли новое ребро экономическую выгоду»


    1. valexey
      16.04.2019 15:19
      #20033504
      +2

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

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

      IMHO

      PS. Вот тут есть симулятор пропускной способности полосы: traffic-simulation.de/ring.html


    1. dmagin Автор
      17.04.2019 09:54
      #20036570

      Почему это подается аксиомой? Что является признаком близости?

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


  1. malkovsky
    16.04.2019 16:47
    #20033926
    +3

    Итак, есть направленный граф с двумя вершинами (узлами)

    Серьезно, вы применяете аппарат теории графов для графа из двух вершин?
    Насколько будут ближе районы, если построить еще одну полосу в одном направлении?

    [trolling] А что, добавление новой дороги меняет положение районов в пространстве? Напоминает мне старый подкол «Что тяжелее: килограмм ваты или килограмм гвоздей?»[/trolling]
    А если серьезно
    Вопрос — насколько изменится расстояние между узлами, если проводимость в одном из направлений увеличить вдвое?

    Связь «расстояния» и «пропускной» способности у вас нигде не задается, поэтому все, что написано в статье — это просто набор алгебраических преобразований без какого-либо смысла.

    З.Ы. Если словосочетания network flows, wardrop equilibria ничего вам не говорят, то скорее всего в тематике пропускных способностей на графах вы новичок.


    1. dmagin Автор
      17.04.2019 10:03
      #20036626

      Серьезно, вы применяете аппарат теории графов для графа из двух вершин?

      ) Извиняюсь, конечно. А на какое количество вершин рассчитан этот аппарат?
      … все, что написано в статье — это просто набор алгебраических преобразований без какого-либо смысла.

      … скорее всего в тематике пропускных способностей на графах вы новичок.

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


  1. youngmysteriouslight
    19.04.2019 18:24
    #20050026

    В последнее время играю в OpenTTD. По моему опыту, если пропускная способность A-B недостаточна для нужд потока, а пропускная способность B-A больше A-B, то в конечном счёте по пути B-A за единицу времени будет проходить тот же поток, что и через A-B. Если, конечно, в городе B нет завода по производству транспорта и работает закон сохранения транспорта, а также нет аварий и поломок.
    Для учёта аварий резистивное расстояние тоже не подходит. Честно говоря, не могу представить бытовую интерпретацию резистивного расстояния для задачи о пропускной способности дорог.


    1. dmagin Автор
      19.04.2019 19:09
      #20050248

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

      Вообще поскольку в статье приведен пример орграфа на основе дорог, то народ стал думать в основном в сторону транспорта и потоков. Это вполне нормально, и уверен, что там можно обнаружить правильные интерпретации, если чуть копнуть. Обнаружится какое-нибудь «время средней достижимости».

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