dmagin (dmagin) wrote,
dmagin
dmagin

Category:

Расчет резистивной матрицы в направленном графе

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

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

Отсюда вытекает, что правильное определение резистенса - через определители миноров матрицы лапласиана -

Rij = Lm(i,j) / Lm(i,i) (1)

Здесь Lm(i,j), Lm(i,i) - миноры 2-го и 1-го порядка соответственно.

По формуле (1) можно считать расстояния как для направленного, так и для ненаправленного графа. Но прямой расчет по данной формуле будет (очень) медленным - много миноров/определителей.

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

Rij = Gii + Gjj - Gij - Gij (2)

Все здорово. Тем более, что можно и в обратную сторону посчитать (от резистенсов к смежности).

Проблема же в том, что для направленных графов (расстояний) формула (2) не работает. Ну, во-первых, структура формулы (2) такова, что она возвращает всегда симметричную матрицу (Rij = Rji).
Но и разные попытки модификации формулы - придания ей несимметричности - тоже не работают - то есть не дают значения, которые бы совпадали со значениями, полученными по формуле (1).

И вот загадка - как же можно быстро посчитать резистивную матрицу для направленных графов? Гугление результатов не дало - народ работают исключительно с симметричными резистивными расстояниями. Печаль.
Tags: Графы, Линейная алгебра
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments