23 мая 2011 г. УДК 519.1 ПОТОКИ В СЕТЯХ С НЕСТАНДАРТНОЙ ДОСТИЖИМОСТЬЮ © 2012 г. Я.М. Ерусалимский Южный федеральный университет, ул. <...> Показано, что классическое определение потока в сети не учитывает тот факт, что допустимыми на таких сетях являются не все пути. <...> Введенные в работе определения позволяют корректно определить поток в таких сетях, максимальный поток и пропускную способность сетей с нестандартной достижимостью. <...> Найден предел последовательности пропускных способностей семейства, когда высота барьеров неограниченно возрастает. <...> Problems about streams in networks with non-standard connectedness are considered. <...> The definitions entered in work allow defining correctly a stream in such networks, the maximum stream and throughput of networks with non-standard connectedness. <...> The family of networks with barrier connectedness is considered. <...> Нестандартная достижимость на графах предполагает, что допустимыми к рассмотрению являются не все пути, а только удовлетворяющие определенному условию (оно называется типом или видом нестандартной достижимости). <...> Как правило, тип нестандартной достижимости возникает после того, как задано некоторое разбиение множества дуг графа, а ограничения на достижимость формулируются с помощью (в терминах) этого разбиения. <...> Первые работы в этой области принадлежат Я.М. Ерусалимскому и Е.О. Басанговой [1–4]. <...> Характерной особенностью для всех типов нестандартной достижимости оказалась неприменимость напрямую известных алгоритмов решения задач о кратчайших путях, случайных блужданиях и максимальных потоках. <...> Графы с нестандартной достижимостью – первый известный пример, когда мультиграфы (графы с кратными дугами) приходится рассматривать по существу, когда задача, исходно поставленная на мультиграфе, не может быть сведена к задаче на обычном графе заменой кратных дуг кратчайшей из них в задаче о кратчайших путях или дугой с суммарной пропускной способностью в потоковых задачах. <...> Это связано с тем, что кратные дуги могут быть разных типов. <...> Во всех рассмотренных случаях «идеология» оказалась одной и той же – построение <...>