Квазиметрики на графах

В статье рассмотрены свойства квазиметрики среднего времени первого прохода (обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова), построенной на основе нескольких графовых моделей, в том числе на базе простого цикла, простого пути и их ориентированных аналогов.
Во введении представлена история вопроса, дан обзор основных идей и результатов работы.
Во втором разделе собраны основные понятия теории цепей Маркова – последовательностей случайных событий с конечным или счетным числом исходов, характеризующихся
тем, что распределение вероятностей параметров процесса в следующий момент времени зависит только от параметров процесса в предыдущий момент. Даны базовые определения,
необходимые для рассмотрения роли графовых моделей в представлении и исследовании эргодических однородных цепей Маркова. Марковская цепь может быть изображена в виде ориентированного взвешенного графа переходов, вершины которого соответствуют состояниям цепи, а дуги – переходам между ними. С другой стороны, любой связный граф (ориентированный граф) может служить базой для построения модели простейшей цепи Маркова: если вершина 𝑖 имеет степень (полустепень исхода) 𝑘, то все выходящие из нее ребра (дуги) превращаются в дуги с весами 1/𝑘 . Дано определение среднего времени первого
прохода для однородной эргодической цепи Маркова. Проанализирован алгоритм нахождения среднего времени первого прохода с помощью использования сходящихся деревьев ориентированного графа, связанного с матрицей перехода эргодической однородной цепи Маркова. Матрица среднего времени первого прохода рассмотрена как квазиметрика 𝑚 среднего времени первого прохода на множестве вершин 𝑉 = {1, 2, ..., 𝑛} ориентированного графа, соответствующего матрице перехода эргодической однородной цепи Маркова: 𝑚(𝑖, 𝑗) – ожидаемое количество шагов (дуг) для случайного блуждания на орграфе Γ,
начинающегося с 𝑖, для достижения 𝑗 в первый раз. Эта квазиметрика обладает рядом важных теоретических и прикладных свойств.
В третьем разделе рассмотрены вопросы построения и исследования квазиметрики среднего времени первого прохода для неориентированного цикла 𝐶𝑛, 𝑛 ≥ 3. Рассмотрены примеры построения квазиметрики среднего времени первого прохода для неориентированного цикла для малых значений 𝑛. Приведены иллюстрации ”графовой“ процедуры построения матрицы 𝑀. Проанализированы свойства получающиеся при этом обобщенных метрических структур.
В четвертом разделе аналогичные рассуждения проведены для квазиметрики среднего времени первого прохода для неориентированного пути 𝑃𝑛, 𝑛 ≥ 2.
В пятом разделе рассмотрены вопросы построения и исследования квазиметрики среднего времени первого прохода для ориентированного цикла 𝐶𝑛, 𝑛 ≥ 3. Рассмотрены примеры построения квазиметрики среднего времени первого прохода для ориентированного цикла для малых значений 𝑛. Приведены иллюстрации ”графовой“ процедуры построения матрицы 𝑀. Проанализированы свойства получающихся при этом обобщенных метрических структур.
В шестом разделе аналогичные рассуждения проведены для квазиметрики среднего времени первого прохода для ориентированного пути 𝑃𝑛, 𝑛 ≥ 2.
В заключении подведены итоги работы и намечены возможные пути дальнейших исследований.

1. Деза М.М., Деза Е.И., Дютур Сикирич М. Полиэдральные конструкции, связанные с квази-метриками // Чебышевский сборник. 2015. Том 16, выпуск 2. С. 79 – 92.

2. Деза Е.И., Мханна Б. О специальных свойствах некоторых квазиметрик // Чебышевский сборник. 2020. Том 21, выпуск 1. С. 145 – 164.

3. Потапов В.Н. Теория информации. Кодирование дискретных вероятностных источников. - Новосибирск: НГУ, 1999.

4. Чеботарев П.Ю., Агаев Р.П. Матричная теорема о лесах и лапласовские матрицы орграфов. - М.: LAP LAMBERT Academic publishing, 2011.

5. Шеннон К. Работы по теории информации и кибернетике. - М.: ИЛ, 1963.

6. Catral M., Neumann M., Xu H. Proximity in group inverses of M-matrices and inverses of diagonally dominant M-matrices // Linear Algebra and its Applications. 2005. Vol. 409. P. 32 – 50.

7. Chebotarev P. Spanning forest and the Golden ratio // Discrete Applied Mathematics. 2008. Vol. 156. P. 813 – 821.

8. Chebotarev P. Studying new classes of graph metrics / in F. Nielsen and F. Barbaresco, editors, Proceedings of the SEE Conference ”Geometric Science of Information“ (GSI-2013) // Lecture Notes in Computer Science. 2013. LNCS 8085. P. 207 – 214.

9. Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix // Linear Algebra and its Applications. 2002. Vol. 356. P. 253 – 274.

10. Chebotarev P., Deza E. Hitting time quasi-metric and its forest representation // Optimization Letters. 2020. Vol. 14. P. 291 – 307.

11. Chebotarev P.Y., Shamis E.V. On proximity measures for graph vertices // Automation and Remote Control. 1998. Vol. 59. P. 1443 – 1459.

12. Deza E., Deza M., Dutour Sikiri´c M. Generalizations of Finite Metrics and Cuts. - World Scientific, 2016.

13. Deza M., Deza E. Cones of partial metrics // Contributions to Discrete Mathematics. 2011. Vol. 6. P. 26 – 47.

14. Deza M. M., Deza E. Encyclopedia of Distances. - Springer: Berlin-Heidelberg, 2016.

15. Deza M., Deza E., Vidali J. Cones of weighted and partial metrics / in Proceedings of the Internat. Conference on Algebra 2010 // Advances in Algebraic Structures. 2012. P. 177 – 197.

16. Kirkland S.J., Neumann M. Group inverses of M-matrices and their applications. - CRC Press, 2012.

17. Klein D., Zhu H. Distances and volumina for graphs // Journal of Mathematical Chemistry. 1998. Vol. 23. P. 179 – 195.

18. Leighton T., Rivest R.L. The Markov chain tree theorem // Computer Science Technical Report MIT/LCS/TM-249, Laboratory of Computer Science, MIT, Cambridge, Mass. 1983.

19. Leighton T., Rivest R.L. Estimating a probability using finite memory // IEEE Transactions on Information Theory. 1986. Vol. 32. P. 733 – 742.

20. Wilson W. On quasi-metric spaces // American Journal of Mathematics. 1931. Vol. 53. P. 675–684.