dmagin (dmagin) wrote,
dmagin
dmagin

Category:

Маленькое открытие - расчет потенциалов по матрице Кирхгофа

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

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

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

Удивительно и другое - я нигде не могу найти упоминания о таком факте. Ни в одном учебнике, ни в монографиях. Да и в теории марковских цепей ничего такого не увидел. Странно. Нужна помощь специалистов.

Я подозреваю, что сам Кирхгоф мог знать об этом факте. Но то ли об этом забыли со временем, то ли сей факт не считается важным - не могу понять.
Единственное, в чем уверен - что данный способ расчета очень важен и интересен. В разных аспектах.
Tags: Графы, Матрица Кирхгофа
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments