Устройство для моделирования ориентированных графов

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 119) (11) 15 ц С 06 С 7/48 О ОПИСАНИЕ ИЗОБРЕТЕНИ видетельст АВТОРСК(56) Автор У 7523621 Авторс Ф 299853, 1В. 86. Бюл лексеев ичкин ула33(088.8)ское свидекл. С 06 Сое свидетекл. С 06 С о СССР1978.СССР1969. льс 7/1 ьств 7/48 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯОРИЕНТИРОВАННЫХ ГРАФОВ(57) Изобретение относится к аналоговой технике и может быть использовано при решении задач определения характеристик систем, отображаемых графами. Цель изобретениясостоит в расширении функциональныхвозможностей за счет определения ргов вершин и числа путей в графе. Устройство .содержит модели дуг 1 ивершин 2, источник 3 регулируемогонапряжения, блок 4 индикации и переключатель 5. Модель 1 содержит операционный усилитель 6, выпрямительный элемент 7, замыкающий контакт 8,масштабные 9, 10 и переменный 11 резисторы, размыкающий контакт 12.Модель 2 содержит операционный усилитель 13, многополюсный двухпозиционный переключатель 14, масштабные резисторы 15. Задавая с помощьюрезисторов 11 напряжения, пропорциональные длительностям работ, с помощью блока 4 определяют протяженность частных и обшего критическихпутей. Приписывая дугам длину, равную 1, определяют ранг вершин, а осуществляя необходимые коммутации спомощью переключателей определяютчисло путей в графе. 2 ил.(57) Изобретение относится к аналоговой вычислительной технике и,может быть использовано при решениизадач определения характеристиксистем, отображаемых графами.Цель изобретения - расширениефункциональных возможностей путемопределения рангов вершин и числапутей в графе.,На Фиг. 1 изображена Функциональная схема предлагаемого устройства;на Фиг. 2-5 - графы применительнок которым иллюстрируются возможностиустройства,Устройство содержит модели дуг 1и вершин 2 источник 3 регулируемого напряжения, блок 4 индикации,выполненный в виде вольтметра, переключатель 5,Модель 1 содержит операционныйусилитель 6, выпрямительный элемент 7, замыкающий контакт 8, первыймасштабный резистор 9, вторые масштабные резисторы 10 и переменныерезисторы 11, размйкающий контакт 12,Модель 2 содержит операционный усилитель 13, многополюсный двухпозиционный переключатель 14, масштабныерезисторы 15.В работе устройства можно выделить три этапа.Первый этап - моделирование критического пути. Напряжение от источника 3 подается через контакты 12на резисторы 11 всех моделей дуг,Резисторы 11 включены по схеме потенциометра и позволяют установитьнапряжения, пропорциональные длительностям работ, Установка производится по шкале потенциометра иможет контролироваться и уточнятьсяс помощью блока 4, подключаемого кмоделям 1 посредством переключателя 5. Операционные усилители 6 моделей 1 работают в режиме суммирования входных напряжений, напряженияна выходе их пропорциональны раннимсрокам окончания работ. Выходы моделей 1 входящих в вершину, соединены каждая со своим входом модели 2этой вершины и через замкнутые контакты переключателя 14 и масштабныерезисторы 15 подключены к входу операционного усилителя 13. Выпрямительные элементы 7 осуществляют выбормаксимума напряжения" на выходах моделей 1, входящих в вершину, операционный усилитель 13 модели 2 восстанав 15 2 О 25 ЗО 35 4 О 45 5 О 55 ливает полярность напряжения в устройстве и подает его на входы моделей 1, выходящих из этой вершины.Протяженность частных и общего критических путей определяются с помощьюблока 4, подключаемого к выходам моделей 2 через переключатель 5, Дляиндикации дуг, лежащих на критическом пути, можно использовать любоеиз известных устройств, напримерсветодиод в качестве выпрямительногоэлемента 7. Источник 3 позволяет задавать уровень напряжения на входах моделей 1 так, чтобы последнийна критическом пути операционныйусилитель 6 не вошел в режим насыщения,Второй этап - определение ранговвершин. Если всем дугам рассматриваемого графа приписать длину, равную 1, то ранг вершины равен максимальному пути от начала графа до этойвершины, Напряжение 0 источника 3,выставляемое с помощью блока 4, впервом положении переключателя 5 ив нулевых положениях всех резисторов 11 подано на входы всех моделей1 и соответствует единичной длине их.Напряжение на выходе модели 2 1-й,вершины графа, при том же состоянииэлементов устройства, что и на первом этапе, равно К Б , где К - рангп1-й вершины, и определяется вольтметром 4, подключаемым к модели 23-й вершины при помощи переключателя 5.Третий этап - определение числапутей в ориентированном графе. Вовсех моделях 1 и 2 замыкают контакты8 и переключают переключатель 14.В моделях 1 всех дуг, кроме выходящих из начальной вершины графа, производят размыкание контакта 12. Врезультате все модели дуг, кромеуказанных, переводятся в режим инвертора, а все модели вершин - в режимсуммирования входных напряжений.Напряжение Б источника 3 поданона входы моделей 1 дуг выходящихиз начальной вершины графа. Количество путей Ы, ведущих в 3-ю вершинуграфа, равйо отношению напряженийБ на выходе модели 2 3-й вершины иЦ, т.е. И =Б; И, замеряемых при помощи блока 4 и переключателя .5.Устройство позволяет определятьи число К; путей, проходящих черезлпанную дугу Й, , В этом случае510 15 К 1 =ММ, где М; - число путей, ведущих из начальной вершины в вершину х графа. Числа М; и М(где М число путей, ведущих в конечную вершину из вершины 3) определяются ука - занным выше способом, причем при определении М источник 3 подключается лишь к одному из свободных входов модели 2 3-й вершины графа.Устройство позволяет определять ошибки, допущенные при построении производственной сети, а именно контуры и тупики 1 первого рода. Пусть, например, имеем ориентированный граф, изображенный на фиг. 2. Если 0 - начальная вершина графа, то на выходах моделей других его вершин, при работе устройства в режиме определения рангов вершин, будут напряжения: 1, 2, 3 вершины, образующие контур напряжения насыщения операционных усилителей; 4-я вершина - тупик первого рода - нулевое.Обеспечивается также возможность определения критического пути в гра-.фе при помощи устройств: для определения кратчайшего пути и наоборот.Пусть, например, имеем граф, изображенный на фиг. 3, с указанными длинами дуг и рангами вершин (ранги указаны в квадратах) и устройство дляопределения кратчайшего пути в графе. Требуется определить критическийпуть в графе. Посредством преобразованияе;=(г,-г,) г-с, (1)перейдем от графа на фиг. 3 с длинами дуг г к графу на фиг. 4 с дли нами дуг 1; . В выражении (1) г,г; - ранги вершин 3 и 1, а г = максГг.;=5(2)При помощи имеющегося устройства определяют кратчайший путь в графе на фиг. 4. Им будет путь 0-1-2-3-4 с Т =8. Нетрудно заметить, что этот же путь 0-1-2-3-4 является критическим для графа на фиг. 3. Величину Т определяем на основе обратного (1) преобразования Т =(г -г )-г Тмин 45-8=12 что соответствует прямому расчету Т . Пусть теперь требуется при помощи устройства для определения критического пути определить крат 25 30 35 40 45 50 55 чайший путь в графе на фиг. 3. Посредством преобразования (1) перейдем от графа на фиг. 3 с длинами дуг г; к графу на фиг, 5 с длинами дуг 1 . В отличие от первого случая здесьГ(,)При помощи имеющегося устройства определяем критический путь 0-2-4 с Т =17, Этот же путь 0-2-4 являетсяФкратчайшим для графа на фиг. 3, а Т =(г -г )- г-Т =20-17=3мин 4 О 3(р3 что соответствует результату прямого расчета. Формула изобретения Устройство для моделирования ориентированных графов, содержащее источник регулируемого напряжения и модели вершин и дуг, соединенные согласно топологии графа, причем модель каждой вершины содержит операционный усилитель, а модель каждой дуги - три масштабных и переменный резисторы и операционный усилитель, выход которого через последова. тельно соединенные выпрямительный элемент и первый масштабный резистор соединен со своим входом, подвижный контакт переменного резистора через второй масштабный резистор соединен с входом операционного усилителя, первый вывод третьего масштабного резистора подключен к входу операционного усилителя, а второй вывод третьего масштабного резистора соединен с выходом операционного усилителя модели вершины, из которой исходит дуга, отличающееся тем, что, с целью расширения функциональных возможностей путем определения рангов вершин и числа путей в графе, в него введены блок индика 4 ции и переключатель, в каждую модель вершины - многополюсный двухпозиционный переключатель и масштабные резисторы, а в каждую модель дуги - размыкающий контакт и замыкающий контакт, включенный параллельно выпрямительному элементу, в модели вершины размыкающие контакты многополюсного двухпозиционного переключателя соединены с первым выводомг.Я г,Х Составитель А. Шеренковр Г, Волкова Техред О.Ващишина Корректор ейи ак 8419/53ВНЙИ Тираж 709 ПодпиГосударственного комитета СССРлам изобретений и открытийсква, Ж, Раушская наб., д. а о 035 Филиал ППП "Патент", г. Ужгород, ул. Проектная 3 12035 масштабного резистора, второй вывод которого подключен к входу операционного усилителя, замыкающие контакты переключателя через соответствующие масштабные резисторы соединены с входом операционного усилителя, выход операционного усилителя каждой модели дуги подключен к подвижному контакту многополюсного двухпозиционного переключателя 1 О модели соответствующей вершины, а подвижный кбнтакт переменного резистора каждой модели дуги - к соответствующему неподвижному контакту 48 Ьпереключателя, подвижный контакткоторого соединен с входом блока индикации, первый вывод источника регулируемого напряжения соединен сшиной нулевого потенциала, второйвывод через размыкающий контакт подключен к первому выводу переменногорезистора каждый модели дуги, второйвывод которого соединен с шиной нулевого потенциала, а выход операционного усилителя каждой модели вершины подключен к соответствующемунеподвижному контакту переключателя,