№ 5 УДК 519.1 ГРАФЫ С ЗАВИСИМОСТЬЮ НЕКОТОРЫХ ХАРАКТЕРИСТИК ОТ ВРЕМЕНИ: ДОСТИЖИМОСТЬ, СЛУЧАЙНЫЕ ПРОЦЕССЫ © 2012 г. В.А. Скороходов, А.С. Чеботарева Южный федеральный университет, ул. <...> Мильчакова, 8, г. Ростов-на-Дону, 344090 Southern Federal University, Milchakov St., 8, Rostov-on-Don, 344090 Рассмотрены графы с меняющейся нестандартной достижимостью. <...> Основные наборы (характеристический и путевой) таких графов зависят от дискретного времени. <...> Сформулированы и изучены задачи о достижимости и о случайных блужданиях частицы по вершинам графа с меняющейся нестандартной достижимостью. <...> Сформулирована и доказана теорема о соответствии путей исходного и вспомогательного графов. <...> Рассмотрена задача о случайных блужданиях частицы по вершинам графа с меняющимися длительностями дуг. <...> Для ее решения предложено построение нескольких матриц вероятностей для вспомогательного графа. <...> Сформулированы и доказаны теоремы о связи вероятностей перехода на исходном и вспомогательном графах. <...> Graphs with varying nonstandard reachability are considered. <...> For such graphs the main sets (characteristic set and path set) depend by the discrete time. <...> The problem of reachability and the problem of casual walk of a particle on graphs with varying nonstandard reachability are formulated and studied. <...> Theorem on compliance of ways on source and auxiliary graphs is formulated and proofed. <...> Графы с меняющейся нестандартной достижимостью Рассмотрим граф G ( ) ( , , )fUXtφ T tb e Zt ];[ u t i κu :T m → = Ч[0; ]Z + с нестандартной достижимостью φ [1], у которого для каждой дуги u U∈ заданы 2 характеристические функции: {0;1 } времени. <...> 0, в противном случае. j Ориентированный граф такого вида будем называть графом с меняющейся нестандартной достижимостью. <...> На таких графах рассмотрим 2 классические задачи: о кратчайших путях и о случайных блужданиях частицы по вершинам графа. <...> Задача о кратчайших путях Рассмотрим задачу нахождения кратчайшего пути на графе с меняющейся нестандартной достижимостью. <...> Отметим тот факт, что для графов с меняющейся нестандартной достижимостью, как и в других случаях зависимости дуг от времени, в задаче нахождения кратчайшего пути <...>