Чебышевский сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сб., 2021, том 22, выпуск 2, страницы 48–75 (Mi cheb1022)  

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

Е. И. Деза, Б. Мханна

Московский педагогический государственный университет (г. Москва)

Аннотация: В статье рассмотрены свойства квазиметрики среднего времени первого прохода (обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова), построенной на основе нескольких графовых моделей, в том числе на базе простого цикла, простого пути и их ориентированных аналогов.
Во введении представлена история вопроса, дан обзор основных идей и результатов работы.
Во втором разделе собраны основные понятия теории цепей Маркова – последовательностей случайных событий с конечным или счетным числом исходов, характеризующихся тем, что распределение вероятностей параметров процесса в следующий момент времени зависит только от параметров процесса в предыдущий момент. Даны базовые определения, необходимые для рассмотрения роли графовых моделей в представлении и исследовании эргодических однородных цепей Маркова. Марковская цепь может быть изображена в виде ориентированного взвешенного графа переходов, вершины которого соответствуют состояниям цепи, а дуги – переходам между ними. С другой стороны, любой связный граф (ориентированный граф) может служить базой для построения модели простейшей цепи Маркова: если вершина $i$ имеет степень (полустепень исхода) $k$, то все выходящие из нее ребра (дуги) превращаются в дуги с весами $\frac{1}{k}$. Дано определение среднего времени первого прохода для однородной эргодической цепи Маркова. Проанализирован алгоритм нахождения среднего времени первого прохода с помощью использования сходящихся деревьев ориентированного графа, связанного с матрицей перехода эргодической однородной цепи Маркова. Матрица среднего времени первого прохода рассмотрена как квазиметрика $m$ среднего времени первого прохода на множестве вершин $V=\{1, 2, ..., n\}$ ориентированного графа, соответствующего матрице перехода эргодической однородной цепи Маркова: $m(i,j)$ – ожидаемое количество шагов (дуг) для случайного блуждания на орграфе $\Gamma$, начинающегося с $i$, для достижения $j$ в первый раз. Эта квазиметрика обладает рядом важных теоретических и прикладных свойств.
В третьем разделе рассмотрены вопросы построения и исследования квазиметрики среднего времени первого прохода для неориентированного цикла $C_n$, $n\geq 3$. Рассмотрены примеры построения квазиметрики среднего времени первого прохода для неориентированного цикла для малых значений $n$. Приведены иллюстрации "графовой“ процедуры построения матрицы $M$. Проанализированы свойства получающиеся при этом обобщенных метрических структур.
В четвертом разделе аналогичные рассуждения проведены для квазиметрики среднего времени первого прохода для неориентированного пути $P_n$, $n\geq 2$.
В пятом разделе рассмотрены вопросы построения и исследования квазиметрики среднего времени первого прохода для ориентированного цикла $\overrightarrow{C_{n}}$, $n\geq 3$. Рассмотрены примеры построения квазиметрики среднего времени первого прохода для ориентированного цикла для малых значений $n$. Приведены иллюстрации ”графовой" процедуры построения матрицы $M$. Проанализированы свойства получающихся при этом обобщенных метрических структур.
В шестом разделе аналогичные рассуждения проведены для квазиметрики среднего времени первого прохода для ориентированного пути $\overrightarrow{P_{n}}$, $n\geq 2$.
В заключении подведены итоги работы и намечены возможные пути дальнейших исследований.

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

DOI: https://doi.org/10.22405/2226-8383-2018-22-2-48-75

Полный текст: PDF файл (996 kB)

Тип публикации: Статья
УДК: 519.1

Образец цитирования: Е. И. Деза, Б. Мханна, “Квазиметрики на графах”, Чебышевский сб., 22:2 (2021), 48–75

Цитирование в формате AMSBIB
\RBibitem{DezMha21}
\by Е.~И.~Деза, Б.~Мханна
\paper Квазиметрики на графах
\jour Чебышевский сб.
\yr 2021
\vol 22
\issue 2
\pages 48--75
\mathnet{http://mi.mathnet.ru/cheb1022}
\crossref{https://doi.org/10.22405/2226-8383-2018-22-2-48-75}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/cheb1022
  • http://mi.mathnet.ru/rus/cheb/v22/i2/p48

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:20
    Полный текст:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021