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

 

Изобретение относится к аналоговой технике и может быть использовано при решении задач определения характеристик систем, отображаемых графами. Цель изобретения состоит в расширении функциональных возможностей за счет определения рангов вершин и числа путей в графе. Устройство содержит модели дуг 1 и вершин 2, источник 3 регулируемого напряжения, блок 4 индикации и переключатель 5. Модель 1 содержит операционный усилитель 6, вьтрямительный элемент 7, замыкающий контакт 8, масштабные 9, 10 и переменньА 11 резисторы , размыкающий контакт 12. Модель 2 содержит операционный усилитель 13, многрполюсный двухпозиционный переключатель 14, масштабные резисторы 15. Задавая с помощью резисторов 11 напряжения, пропорциональные длительностям работ, с помощью блока 4 определяют протяженность частных ч общего критических путей. Приписывгш дугам длину, равную 1, определяют ранг вершин, а осуществляя необходимые коммутации с помощью переключателей определяют число путей в графе. 2 ил,. § (Л с: .JJ

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) 1 11 ф G 06 G 7/48

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Устройство .содержит модели дуг 1 и вершин 2, источник 3 регулируемого напряжения, блок 4 индикации и переключатель 5. Модель 1 содержит операционный усилитель 6, выпрямительный элемент 7, замыкающий контакт 8, масштабные 9, 10 и переменный 11 ре зисторы, размыкающий контакт 12.

Модель 2 содержит операционный усилитель 13, многополюсный двухпозиционный переключатель 14, масштабные резисторы 15. Задавая с помощью резисторов 11 напряжения, пропорциональные длительностям работ, с помощью блока 4 определяют протяженность частных и обшего критических путей. Приписывая дугам длину, равную 1, определяют ранг вершин, а осуществляя необходимые коммутации с помощью переключателей определяют число путей в графе. 2 ил. (21) 3738400/24-24 (22) 04.05.84 (46) 07.01.86. Бюл. У 1 (72) О.Г. Алексеев, В.В. Спичкин и Н.И. Ячкула (53) 681.333(088.8) (56) Авторское свидетельство СССР

N- 752362, кл. G 06 G 7/122, 1978.

Авторское свидетельство СССР

N- 299853, кл. G 06 G 7/48, 1969. (54S УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ОРИЕНТИРОВАННЫХ ГРАФОВ (57) Изобретение относится к аналоговой технике и может быть использовано при решении задач определения характеристик систем, отображаемых графами. Цель изобретения состоит в расширении функциональных возможностей за счет определения рангов вершин и числа путей в графе. ( ф.

4.

Р " - - - " г

ОПИСАНИЕ ИЗОБРЕТЕНИЛ /

$g;,

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

1203548 (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 восстанав5

2О

4О

5О

55 ливает полярность напряжения в устройстве и подает его «а входы моделей 1, выходящих из этой вершины.

Протяженность частных и общего критических путей определяются с помощью блока 4, подключаемого к выходам моделей 2 через переключатель 5. Для индикации дуг, лежащих на критическом пути, можно использовать любое из известных устройств, например светодиод в качестве выпрямительного элемента 7. Источник 3 позволяет задавать уровень напряжения на входах моделей 1 так, чтобы последний на критическом пути операционный усилитель 6 не вошел в режим насыщения.

Второй этап — определение рангов вершин. Если всем дугам рассматриваемого графа приписать длину, равную 1, то ранг вершины равен максимальному пути от начала графа до этой вершины. Напряжение 0 источника 3, выставляемое с помощью блока 4, в первом положении переключателя 5 и в нулевых положениях всех резисторов 11 подано на входы всех моделей

1 и соответствует единичной длине их.

Напряжение на выходе модели 2 j-й, вершины графа, при том же состоянии элементов устройства, что и на первом этапе, равно К U, где К вЂ” ранг п J

j-й вершины, и определяется вольт— метром 4, подключаемым к модели 2

j-й вершины при помощи переключателя 5.

Третий этап — определение числа путей в ориентированном графе. Во всех моделях 1 и 2 замыкают контакты

8 и переключают переключатель 14.

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

Напряжение U источника 3 подано на входы моделей 1 дуг„ выходящих из начальной вершины графа. Количество путей N, ведущих в j-ю вершину графа, равйо отношению напряжений

U на выходе модели 2 j-й вершины и

U» т.е. N>=U>/U„, замеряемых при помощи блока 4 и переключателя -5.

Устройство позволяет определять и число К; путей, проходящих через лпанную дугу d . В этом случае

3 1203548 4

t0

К1 =N„M, где N; — число путей, ведущих из начальной вершины в вершину i графа. Числа Ni и М (где Mj число путей, ведущих в конечную вершину из вершины j) определяются ука— занным выше способом, причем при определении М источник 3 подключает) ся лишь к одному из свободных входов модели 2 j-й вершины графа.

Устройство позволяет определять ошибки, допущенные при построении производственной сети, а именно контуры и тупики 1 первого рода. Пусть, например, имеем ориентированный граф, изображенный на фиг. 2. Если 0 — начальная вершина графа, то на выходах моделей других его вершин, при работе устройства в режиме определения рангов вершин, будут напряжения:

1, 2, 3 вершины, образующие контур напряжения насыщения операционных усилителей; 4-я вершина — тупик первого рода — нулевое.

Обеспечивается также возможность определения критического пути в гра-. фе при помощи устройств: для определения кратчайшего пути и наоборот.

Пусть, например, имеем граф, изображенный на фиг. 3, с указанными длинами дуг и рангами вершин (ранги указаны в квадратах) и устройство для определения кратчайшего пути в графе. Требуется определить критический путь в графе. Посредством преобразования (t;„=(r, -r, ) t*-t;;, (1) перейдем от графа на фиг. 3 с длинами дуг t" к графу на фиг. 4 с дли(! нами дуг t; . В выражении (1) r>, 11 г; — ранги вершин 1 и i, а

t* = макс Г ; j =5. (2) (. Г

При помощи имеющегося устройства определяют кратчайший путь в графе на фиг. 4. Им будет путь 0-1 -2-3-4 с T»„ =8. Нетрудно заметить, что этот же путь 0-1-2-3-4 является критическим для графа на фиг. 3. Величину Т(определяем на основе обратного (1) преобразования

T„ =(г -r )- t*-T„„„=4 5-8=12, что соответствует прямому расчету

Т„ . Пусть теперь требуется при помощи устройства для определения критического пути определить крат25

55 чайший путь в графе на фиг. 3. Посредством преобразования (1) перейдем от графа на фиг. 3 с длинами дуг t I к графу на фиг. 5 с длинами дуг t . ° . В отличие от первого слу(( чая здесь

Г =макс — -(-1- = 5.

r -г () 1 (При помощи имеющегося устройства определяем критический путь 0-2-4 с

Т =17. Этот же путь 0-2-4 является

Ф кратчайшим для графа на фиг. 3, а

ei o

Т =(r -r )- t*-T =20-17=3

М((((4 0 Кр

Г что соответствует результату прямого расчета.

Фoрмулаиз обретения

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

Составитель А. Шеренков

Редактор Г. Волкова Техред О.Ващишина Корректор И. Эрдейи

Заказ 8419/53 Тираж 709 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

S 12035 масштабного резистора, второй вывод которого подключен к входу операционного усилителя, замыкающие контакты переключателя через соответствующие масштабные резисторы соединены с входом операционного усилителя, выход операционного усилителя каждой модели дуги подключен к подвижному контакту многополюсного двухпозиционного переключателя 10 модели соответствующей вершины, а подвижный кбнтакт переменного резистора каждой модели дуги — к соответствующему неподвижному контакту

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