Поступила в редакцию УДК 519.1 ПОТОКИ В СЕТЯХ С МЕНЯЮЩЕЙСЯ ДЛИТЕЛЬНОСТЬЮ ПРОХОЖДЕНИЯ © 2011 г. В.А. Скороходов Южный федеральный университет, ул. <...> Мильчакова, 8а, г. Ростов н/Д, 344090 Southern Federal University, Milchakov St., 8a, Rostov-on-Don, 344090 Рассмотрены графы с меняющейся длительностью прохождения по дугам. <...> Сформулирована и изучена задача нахождения максимального потока на таких графах. <...> Сформулированы и доказаны теоремы о соответствии путей исходного и вспомогательного графов. <...> Введены понятия отношения влияния для дуг, обобщенных сетей со связанными дугами и степени влияния цепей в них. <...> Graphs with varying transit times through the arcs are considered. <...> Concepts of the influence relation for arcs, of the generalized networks with the bound arcs and of the degree of path influence in the generalized networks with bound arcs are entered. <...> The upper estimation of the maximum flow in networks with varying transit times through the arcs is offered. <...> Графы с зависимостью длительности прохождения дуг от времени Пусть G ( , , )fUXT – орграф такой, что для каждой его дуги указан вес – длительность (количество тактов) прохождения по ней. <...> Будем считать, что длительность каждой дуги может меняться со временем и описывается функцией c u c u t Определение 1. <...> Рассмотрим задачу нахождения кратчайшего (по длительности прохождения) пути на графе TG с заданным условием. <...> Ее существенной особенностью является то, что, кроме нахождения самого кратчайшего пути (последовательности дуг [1]), необходимо найти еще и время начала движения по нему, поскольку кратчайшие пути могут меняться в зависимости от начальных мо2 g t x = Γ(2 1 − 2 и 2 2 0 можно )(I + заключить, 1−2 2 g t )( )x . что 2( ) ЕСТЕСТВЕННЫЕ НАУКИ. <...> № 1 перехода, равную единице (как и для классического случая), и каждому пути вспомогательного графа соответствует путь (с точностью до момента начала движения) на исходном графе. <...> Каждой вершине исходного графа TG ставится в соответствие <...>