Разработка алгоритмов моделирования и построения информационных сетей методом структурных образований Журавлев Рихсибой

Содержание к диссертации

Введение

Глава 1. Топологические задачи и модели объектов технической кибернетики и теории информации

Глава 2. Определители структурных образований 35

Глава 3. Методы и алгоритмы решения топологических задач с помощью структурных образований 66

Глава 4. Алгоритмы анализа и построенш информационных сетей и с применением струютвык образований

Заключение

Литература

• Топологические задачи и модели объектов технической кибернетики и теории информации
• Определители структурных образований
• Методы и алгоритмы решения топологических задач с помощью структурных образований
• Алгоритмы анализа и построенш информационных сетей и с применением струютвык образований

Введение к работе

Решениями ХХУІ съезда КПСС намечены серьезные и широкомасштабные задачи по развитию науки и ускорению технического прогресса. В частности, предусматривается на основе использования достижений науки и техники совершенствование вычислительной техники, ее элементной базы и математического обеспечения, средств и сие -тем сбора, передачи и обработки информации, и продолжить формирование единой автоматизированной сети связи страны на базе новей -ших систем передачи информации /I/.

Основу современных информавдонных и управляющих систем сое -тавляют электрические и радиоэлектронные схемы и структуры. Совершенствование этих систем сопровождается возрастанием уровня интеграции используемых в них микроэлектронных схем и структур, что приводит к увеличению оложности как самих цепей, структур, так и их функций. Это сильно усложняет моделирование таких схем и структур. Бри анализе и синтезе их резко возрастает время моделирования (а следовательно, и время проектирования), время подготовки задачи к решению даже с применением систем (или подсистем) авто -матизированного проектирования.

Эффективность работы управляющих и информационных систем в равной степени зависит от надежного акционирования применяемых в них радиоэлектронных схем и структур, с одной стороны, выбора соответствующих алгоритмов процедур распределения управляющей информации и управления процессами в системе в целом, с другой стороны.

Решение вышеуказанных задач во многом зависит от уровня методов моделирования и проектирования как радиоэлектронных схем и структур, так и структур самих информационных сетей и цепей, и

требует разработки новых и постоянное совершенствование существующих подходов, методов и алгоритмов реализации задач моделирования и проектирования.

В нашей стране и за рубежом ведутся интенсивные исследования по созданию общей теории и методов автоматизированного проектирования, в частности рациональных методов описания, анализа и син -теза радиоэлектронных структур и схем, информационных сетей и цепей, и их элементов. К современным моделям и математическим аппаратам, ориентированным на использование ЭВМ, предъявляются требования высокой степени формализации, минимальности количества ис -пользуемых математических символов и приспособленности операций алгебры к операторам языка или к выполняемым машинным операциям.

Решению таких задач посвящены работы Анисимова Б.В.» Кални -болотского Ю.М., Петренко А.И., Сигорского В.П., Пухова Г.Е.,Тро-хименко а.К., Белова Б.И., Норенкова И. Д., Нагорного Л .а., Ильи -на В.Н., Гуревича И.В., Ланнэ А.А., Бондаренко В.М., Хасанова П.Ф., Королева Ю.В., Юрина О.Н., Баталова Б.В., Казеннова Г.Г., Абрайтиса Л.Б., Мелихова А.Н., Матюхина Н.Н., Кабулова В.К., Глу-шковаВ.М., Брюнйна В.Н,, Лазарева В.Г., Поспелова Д.А., Сифорова В.И., Толчан А.Я., Рогинского В.Н., Давыдова Г.Б., Харкевича А.Д., Бусленко МЛ., Журавлева Ю.Н., Ченцова В.М. и многих других ав -торов.

Несмотря на широкое распространение матричного аппарата, алгебр графов и различных теоретико-множественных моделей, они недостаточно учитывают особенности выполнения операций апгорит -мических языков и машинного представления данных. Как результат этого, программы решения многих задач в области технической кибернетики и теории информации получаются довольно сложными и требуют больших вычислительных затрат. Это особенно становится ощутимым при решении задач по синтезу и анализу топологических свойств объектов.

В этой связи актуальной является разработка новых моделей и аппаратов для решения топологических задач в области технической кибернетики и теории информации, равносильных матричным и графовым математическим аппаратам и достаточно приспособленных для машинной реализации. Одним из возможных путей решения этой задачи является разработка систем операций и проиедур, применимых непосредственно к структурам данных о моделируемом объекте.

Целью настоящей работы является разработка методов и алгоритмов решения задач топологического анализа информационных сетей (ЙС), цепей (ИЦ) и радиоэлектронных схем и структур (РЭС), основанных на использовании операций над структурами данных о моделируемом объекте.

В диссертации ставятся и решаются следующие задачи:

1. Разработка модели логической структуры данных и определение совокупностей операций и процедур над ними, ориентированных для решения задач топологического анализа сложных информационных сетей, цепей и РЭС.

2. Разработка регулярных алгоритмов определения всевозмож -ных путей между двумя заданными вершинами графов, множества пу -тей, проходящих через приоритетную дугу и всех маршрутов между заданными узлами ЙС, содержащих выбранную линию связи Разработка регулярных алгоритмов составления списка все -возможных и минимальных (максимальных) покрывающих деревьев, включающих приоритетное ребро (или дугу). МЁ РЗМ-Исследованш. В работе применялись главным образом методы и основные положения общей теории математического модели -ровашш, линейной алгебры, теорий сетей, графов, множеств и структур данных.

Научные положения и результаты, выносимые на защиту:

1. Разработаны топологические модели информационных сетей и цепей РЭС, ЙЦ и графов в виде структурных образований» представляющих собой разновидности файлов. Они позволяют в компактной и единой форме связать данные (или сведения) как о топологии, так и о параметрах состояний исследуемого объекта (ИС, их элементов, РЭС и т.п.).

2. Предложена система операций и процедур над структурнши образованиями, которые могут быть использованы для целей исследования линейных систем различной природы.

3. Предложены методы и алгоритмы топологического анализа информационных сетей, цепей и РЭС, оперирующие непосредственно массивами данных об объекте.

4. Разработаны методы и алгоритмы определения оптимального покрывающего дерева неориентированного графа, использующие более простые операции и процедуры по сравнению с известными. Предло -жены методики определения множества путей и деревьев, включающих заданную (приоритетную) дугу или ребро.

5. Составлены алгоритмы определения всевозможных маршрутов между оконечными узлами КС, множества маршрутов, проходящих че -рез заданную линию связи, и построения минимальной по стоимости линий связи структуры ИС типа "дерева".

Научная новизна работы заключается в разработке системы операций и процедур над структурами данных о графах, методов решения топологических задач моделирования информационных сетей, цепей и РЭС, алгоритмов нахождения всевозможных путей и деревьев в графах на основе преобразований над структурными образованиями.

Практическая значимость работы проявляется в возможности совершенствования известных и разработки новцх инженерных методов анализа, преобразования цепей РЭС и ИЦ, моделирования ЙС и надежности функционирования РЭС с неисправностями.

Научные результаты диссертационной работы нашяи практическое применение в научно-исследовательских работах, проводимых в ТашШ им.Абу Райхана Берунй, й внедрена в алектромеханическом заводе г.Ташкента.

Результаты диссертации доложены на: Республиканской научно-технической конференции "Автоматизация с црименением электротехнических устройств и автоматизированное управление производственными процессами в отраслях народного хозяйства" (г.Ташкент,1978); Республиканской конференции молодых ученых и специалистов (г.Самарканд ,1978); Республиканской научно-технической конференции молодых ученых и специалистов, посвященной 50-летию ТашПИ (г.Тал -кент,І980); П Всесоюзной межвузовской научно-технической конфе -ренции "Математическое, алгоритшческое и техническое обеспече -ние АСУ ТП"; П Всесоюзном семинаре "ЙЯетода синтеза и планирова -ния развития структур сложных систем" (г.Ташкент, 1981); Ш Все -союзном совещании "Штоды и программы решения оптимизационных задач на графах и сетях" (гг.Ташкент,Новосибирск,1984); ежегодных научно-технических конференциях профессорско-преподавательского состава ТашПИ (г.Ташкент,1977-1984).

Диссертационная работа состоит из введения, четырех глав, заключения, приложении, списка использованной литературы и акта о внедрении результатов.

B neggog главе рассматриваются топологические задачи технической кибернетики и теории информации, взаимосвязанность задач анализа и синтеза информационных сетей и топологическая поста

новка задач исследования функциональной надежности РЭС. Описываются структурные образования - структура данных для машинного решения топологических задач.

Во.второй главе излагаются элементы теории» операции алгебры структурных образований и процедуры образования символьных выражений числовых характеристик структурных образований.

В_третьей_главе рассматриваются процедуры над структурными образованиями, предназначенные для решения задач топологического анализа и построения информационных сетей, для определения показателей функциональной надежности РЭС и других задач, сформули -рованных на языке графов.

„В четвертрй главе рассматриваются алгоритмы и методы анализа и построения информационных сетей и цепей, основанные на ис -пользовании процедур, изложенных в предыдущих главах.

В приложениях приведены алгоритмы выполнения операций из алгебры структурных образований и примеры (приложение I), некоторые доказательства теорем (приложение 2), элементы теории информационных цепей (приложение 3), блок-схемы алгоритмов анализа и построения ИС и ИЦ с применением структурных образований (приложение 4), акт о внедрении результатов диссертации (приложение 5), а также тексты программ: нахождения всевозможных путей - PR0& (П6.І); анализа цепей (информационных и РЭС) - АРСІ (П6.2); на -хождения минимального дерева в графах систем - XMD (П6.3).

Топологические задачи и модели объектов технической кибернетики и теории информации

Под топологическими задачами будем понимать задачи, сфорлф"-лированнне на языке графов. К ним относятся те задачи, постановка которых основывается на использовании таких понятий из теории графов, как узел (вершина), ветвь (ребро), путь, маршрут, дерево, цикл, контур и др.

Граф /9,35,43,88/, в виде пары из множеств вершин и отношения, заданного на множестве вершин является наиболее подходящей структурной (топологичеакой) моделью системы, представляющей собой множество взаимосвязанных частей. Этим объясняется саше широкое применение графов в качестве моделей различных объектов, рассматриваемых в технической кибернетике и теории информации.

В зависимости от преследуемых целей, от уровня црименения аппарата графов на стадии постановки, решения топологических задач и интерпретации результатов решения, можно указать на два главных направления црименения графовых моделей.

Первое направление преследует цели адекватного отображения известной информации о моделируемом объекте для описания и формулировки задач. Данный класс моделей не позволяет непосредственно получить подробных сведений об исследуемом объекте, но облегчает составление математических (аналитических, других графовых моделей), анализ которых может дать новые сведения об объекте, которые нельзя или нецелесообразно шлучить непосредственно из исходной графовой модели.

Второе направление применений графовых моделей преследует цель долучить новые сведения об объекте при поющи формальных преобразований и операций над; графами. Графы (графоиды), относящиеся к данному направлению применения, можно называть алгебрами графов, в отличие от чисто графовых моделей, относящихся к первому случаю. Следует подчеркнуть t что любой вид графовой мэде-ли становится алгеброй графов, если задать в множестве графов определенную систему операций. Поэтому деление классов графовых моделей на две группы является чисто условным и определяется уров -нем их использования при решении тех или иных задач.

Многие разделы теоретической и технической кибернетики, связанные с применением ЭВМ, особенно теория автоматов, теория информационных цроцессов, исследования операций, теория кодирования, теория игр, нашли естественную формулировку своих задач и методов их решения на языке теории графов /44,58/- Вместе с тем быстро расширяется область применений в разнообразных практических вопросах. Сюда относятся транспортные задачи, календарное планирование промышленного производства, сетевые методы планирования и управления, проблемы построения информационных сетей и систем и исследования цроцессов передачи информации, выбор оптимальных потоков и маршрутов в сетях, методы построения и преобразования электрических цепей, способы построения и цреобразования переключа -тельных схем и многие другие. Мэтоды теории графов основываются на систематизации ряда идей и рриемов комбинаторно-логического характера и направлены на поиск оптимальных решений различных задач дискретной математики.

Описание потоков информации в процессах обработки и управления с помощью графов является одним из наиболее разработанных методов. С помощью графов достигается нагладность функционирования систем обработки информации и управления; применение графов поз воляет оптимизировать работу управления и каналов связи; имеется возможность также представить динамику управления и движения информации, которая ускользает при пользовании другими методами /35,44,94/.

В настоящее время имеется много примеров использования графовых моделей при описании и анализе информационных процессов. Они различаются по характеру описываемых объектов, по способу отображения информации о моделируемом объекте посредством вершин и ребер, способом присвоения весов последним.

В табл.І.І.а приведены модели, наиболее приспособленные для моделирования объектов теории информационных процессов: информа -ционно-поисковых сетей и систем (модели Ш 1,3,9); информацион -ных систем общего вида (модели »2,5,6,8,9); информационных процессов общего вида (модели Ш 2,4; 6,8,9); информационных систем и процессов, удовлетворяющих условиям линейности (модель № 7); алгоритмов обработки информации (модели Ш 5,6); математических объектов в виде систем линейных уравнений (модель 18) и совокупности физических явлений, эффектов и законов (модель 9).

Над любым из приведенных в табл.І.І.а графовых моделей можно производить теоретико-множественные операции, рассмотренные для абстрактных графов. А для некоторых из них (например, для сиг -нальшх графов) разработаны специфичные операции, позволяющие решить задачи анализа и синтеза объектов, которые нельзя решить при ограничивании лишь теоретико-множественными операциями.

Определители структурных образований

Алгоритмы решения задач с помощью структурных образований составляются на основе преобразованші и операций, заданных в множестве структурных образований. В принципе, можно формализовать различные алгебры структурных образований, принимая за основу какую-либо из алгебр, разработанных для "ручных" расчетов.Таковыми могут быть известные алгебры матриц /16/, диаматриц /89/,сигнальных графов /60/ и другие. При этом между носителями и операциями для исходной и разрабатываемой алгебр должно иметь место некоторое соответствие. В случае,когда соответствие - взаимно-однозначное, соответствующие алгебры становятся равносильными по кругу решаемых задач. Что касается эффективности решения тех или иных задач, то сложность алгоритмов при пользовании одной из алгебр может стать больше, чем при пользовании другой, равносильной первой алгеброй.

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

Такая ситуация имело место, например, при разработке алгебры диаматриц и теории диаопределителей /89/, полученных из алгебры матриц и теории определителей на основе соответствия, названного в /89/ диаопреобразованиями. В теории диаопределителей были разработаны эффективные алгоритмы составления символьных выраже -ний системных Функций электрических схем, которые так эффективно не решались на основе теорем теории определителей.

В настоящей работе и в /26,27/ над структурными образованиями определены все операнда, имеющие соответствующие интерпретации в алгебрах матриц и диаматриц. Для решения топологических задач введены две группы понятий для многочленов от элементов структурных образований, первая из которых является изоморфной понятиям теории диаопределителей /89/, ж изложена в настоящей главе,а вторая (гл.З) - пока не имеет своих аналогов, но в некоторой мере соответствует группе понятий, используемых в прикладной теории графов. Учитывая это обстоятельство две разновидности структурных образований, для которых естественную интерпретацию имеют соответствующие им группы понятий о многочленах, в работе названы соответственно Д-образованием (гл.2) и Г-образованием (гл.З).

Как отмечалось в предыдущем параграфе, структурные образования могут быть составлены непосредственно по графу, матрице или некоторой модели объекта, части которой имеют не более чем 2 точки (полюсы) соприкосновения друг с другом.

Разделение СО на два вида является условным и имеет цель разграничить круг понятий, используемых при решении задач. Структурное образование, составленное изложенным в 1.4 способом может являться Д-образованием или Г-образованием, в зависимости от того, к какой группе, моделей относится исходный граф или матрица. Так например, если граф,по которому составляется СО, является информационным графом, графом потока информации, моделью схемы информационной сети, то следует рассматривать составленное СО как Г-образование, т.к. для этих случаев решение многих задач сводится к отысканию путей в графах с заданными свойствами. Если исходная модель является схемой или диаматрицей параметров информационной /23,24/ или электрической цепи /27/ или же схемы радиоэлектронной структуры, то целесообразно состав ленное СО назвать Д-образовашем. Для этих случаев решение многих задач сводится к отысканию деревьев в топологических структурах, которым наиболее подходит группа понятий о многочленах над элементами СО, изложенная во второй главе.

Составленное СО, для дальнейшего оперирования им иногда приходится подвергать к некоторым преобразованиям. Ниже описываются два из таких преобразований: 1 и d -преобразования. Первое из них применяется для получения Д-образования по СО, составленному по исходной матрице параметров информашонной или электронной цепи. Второе применяется для имштации изменения направлений дуг в исходной графовой модели.

Методы и алгоритмы решения топологических задач с помощью структурных образований

Как известно, решение задач проектирования информационных сетей, цепей и РЭС /3,4,5,6,8,11,18,12,21,22,23,33,34,36,37,39, 45,51,54,56,57,58,60,61,63,64,65,67,70,71,74,78,96,97,98,101,102/ тесно связаны с методами теории графов. Аппарат СО позволяет разработать эффективные методы и алгоритмы решения топологических задач. В связи с этим в настоящей главе рассматриваются вопросы применения СО к решению таких задач, как определение всевозмож -шх путей в графах, отыскание путей через дугу с приоритетом, нахождение всевозможных ориентированных деревьев и т.д.

Методы решения этих задач используются при моделировании неисправностей РЭС и систем, определении показателей функционаяьной надежности РЗС, проектировании топологии информационной сети с заг данными структурными и надежностными характеристиками, определе -нии пропускных способностей линий связи и т.д.

Пусть рассматривается произвольно заданный граф lHr,UJ , где И -множество вершин, Q - множество дуг, с входными и выходным вершинами (полюсами) Рвх и гвЬХ , в котором требуется найти все пути, направленные от Не к г$щ . Такому графу,соблюдая известные правила,однозначно сопоставляется некоторое структурное образование ( 1.4). Согласно этим правилам те дуги графа, которые направлены от геых к любым другим вершинам, не образуют путей в выбранном направлении, и поэтому, естественно, не вклга -чаются в СО. Дуги графа, инцидентные таким парам вершин, одна из которых есть вершина rg x » а другой вершиной является любая вершина, отличная от Рвых , однозначно сопоставляются од - 67 нопаяюсным фигурам СО. Такие дуги входят в вершину Реых Вершину РЙЬх графа принимаем за корневую (или базисную) вершину. Для простоты и наглядности дуги графа обозначаем следующим образом: если дуга исходит из вершины гк и входит в вершину r t t то эту дугу обозначим через г Кс , гдеР1}РкЄ 0,1,2,...,П[ для графа сП+1 вершинами.

Принимаем полюс Р за входной полюс для оставшихся одно- и двухполюсных фигур. Если при этом окажется, что полюс, встречающийся на первом месте в I -образах фигуры, по числовому значению больше, чем полюс, стоящий на втором месте, то производят взаимную замену между этими полюсами, а также и между значениями из верхней и нижней строк этой двухполюсной фигуры.

Введенные понятия переименованного независимого минора и минора с измененным входным полюсом дают возможность сформулировать следующие теоремы, позволяющие разложить множество путей II по двухполюсным фигурам ГО. Теорема 3.3. божество путей II -образования мощности П /2 с входным полюсом Hex определяется объединением значения однополюсной фигуры гвх и композиций зависимых от rex значения двухполюсных ФИГУР PW Р. ( Р; Рвх ) С р.р ры с измененным входным полюсом II "

Сфори/дглированные теоремы имеют важное значение при нахождении выражения множества цутей. Они позволяют представить множество путей ГО мощности П не более чем через П -I миноров ГО мощ -пости П -I. Циклическое применение любой из теорем к полученным минорам дает возможность составить упрощенное выражение множества путей /30,31 /.

Рассмотрим г-образование мощности П =1. Это ГО представляет собой однополюсную фигуру и геометрически ему соответствует дуга между вершинами rg и гвых - Множество путей такого ГО цредставляет собой единственный путь, определяемый значением этой однополюсной фигуры.

Алгоритмы анализа и построенш информационных сетей и с применением струютвык образований

Разработанные алгоритмы и методы структурных образований удобно применять при решении задач анализа и синтеза сетей, в частности, при оценке показателей качества ИС и при нахождении на -чальных структур синтезируемой ИС. Например, при определении: а) предельной производительности ИС на произвольном направлении обмена -ПП1Р., г- ; б) реального времени доставки сообщений на заданном направлении обмена -ИВдІД ,М ; в) реальной живучести ИС /19,22,45,57/; г) надежности связи от узла 1\ к узлу Pj ; д) путевого разложения квазипотока в потоковом графе; е) показателей множества путей между двумя произвольными узлами P и Pj ж) анализе и синтезе структуры детерминированной сети /19,22/; з) приближенном анализе сети с коммутацией сообщений с применени ем методики оценочного анализа при неадаптивной и адаптивной про цедурах выбора пути; приближенном синтезе структуры сети с ком мутацией сообщений /19,22,57/ требуется нахождение всевозможных путей между узлами г\ и Pj

Кроме того, при решении перечисленных задач требуется также нахождение подмножества всех путей между двумя узлами к1 и Pj , проходящих через заданное ребро йет - линию связи.

При проектировании распределенных неиерархических сетей небольших размеров и централизованных сетей в качестве начальных структур могут рассматриваться структуры типа "дерево","звезда" и полный граф /19,45,56,57,59,87,97,102,103,111/. Для определе -ния структуры типа "дерево" требуется нахождение минимального по - no суммарной длине ребер соответствующего графа ИС.

Структура ИС с а узлами может быть задана в виде графа - множество вершин?соответ ствующих узлам ИС, 0. ==10.- j } множество ребер, соответствую щих трактам передачи данных (линиям связи). Граф ИС, а следова -тельно, саму ИС, удобно описать с помощью структурных образова -ний. При этом появляется возможность описать тракты передачи данных, узлы коммутации и обработки со своими характеристиками-покат-: зателями связей. Взаимосвязи меаду узлами отображаются с помощью фигур (точечных образов и векторных значений). В этом случае набору показателей тракта передачи данных (ТЦД) соответствует вектор значений фигур СО. Для ориентированных ИС показатели связей задаются векторными значениями обеих строк - верхней и нижней строк, каждый из которых задает показатели связи одного из направлений. Неориентированные ИС описываются структурным образованием, состоящим только из одной строки векторных значенні! и строки I -образов Фигур. Любую ИС можно формально описать двумя структурными образованиями - однополюсно-фигурным СО, описывающим узлы (коммутации и обработки), и двухполюсно-фигурным СО, описывающим ТЕД (линии связи) между узлами ИС.

Если рассматривается только какой-то один показатель элементов ИС, то в строке значении вместо вектора будет записано значение, соответствующее рассматриваемому показателю, в символьной или числовой форме. Если этот показатель характеризует длины ли -ний связи, то получим СО длин линий связи ИС; если он характери -зует пропускную способность линий связи ИС, то получим СО пропу -скных способностей линий связи и т.д.

В приведенных СО С - пропускная способность узла Р. ; R(i)- кроссировочная способность; \(і) вероятность отказа; ц(0 стоимость (приведенные затраты) узла; Щ( ) - помехи в уз-L Ц" Яшт LJ пропускная способность; г[: -надежность (вероятность надежной работы данного ребра); Ц- -стоимость линии связи между двумя смежными узлами г , Р: ;Хп.-L\ -- время передачи сообщения по линии между (двумя смежными) узлами Р., г. ;tv і время задержки сообщения на узле r»t

Аналогичным образом можно записать СО для характеристики путей и их множеств ИС, например, СО кратчайших путей между всеми парами узлов re , гк ; CO пропускных способностей между всевозможными парами узлов rg , гк ;надекностей множества путей между всеми парши узлов rj , гк и т.п.

В связи с этим разработка алгоритмов, имеющих высокоформали-зованный характер и ориентированных на машинную реализацию, представляет несомненно большой практический интерес. Применение та -ких алгоритмов при моделировании ИС на ЭВМ для решения указанных задач анализа и синтеза приведет к ускорению процесса моделирования.

Нижеприводимые алгоритмы целесообразно применять и при анализе распределенных структур. Они наиболее эффективны при анализе больших ЙС. Распределенные структуры являются наиболее сложными для анализа /58,65,97/. Для больших ИС характерно, что имею -щая минимальную конфигурацию в начальный период функционирования ИС в дальнейшем развивается в плане реализации первоначально поставленных задач путем добавления новых узлов и связей, способ -ствующих повышению степени связности ИС, Кроме того, в процессе эксплуатации возникают новые цели и задачи, предвидеть которые заранее невозможно. Следовательно, при построении структуры и маршрутов между узлами ИС встают задачи выделения всевозможных маршрутов (путей) в ИС и определения множества маршрутов, проходящих через заданную между двумя узлами линию связи ИС.

Далее приводятся: алгоритм нахождения всех возможных маршрутов (путей) между оконечными узлами ИС, включающий в себя алгоритм определения всевозможных путей между двумя произвольными узлами сети \ , 11 ; алгоритм нахождения множества путей между двумя узлами Ht и Fj сети, проходящих через заданную линию связи; алгоритм нахождения минимальной структуры типа "дерево" -основанные на методах структурных образований. Приводимые в последующих параграфах 4.1.I. и 4.1.2. алгоритмы предназначены для применения при моделировании ЙС с иелью оценки показателей качества функционирования ИС.